Boost Graph Library: Can Combine Combined Properties with Internal Properties?

Question

I use this typedef for my BGL chart type, Graph , using struct VertexProperty as a property of a bunch of vertices:

 struct VertexProperty { BeamType beam; size_t index; }; typedef typename boost::adjacency_list< boost::listS, boost::listS, boost::bidirectionalS, VertexProperty > Graph; 

Until a recent change to my project, I used VertexProperty::index to build two_bit_color_map for use with depth_first_search :

 auto colorMap = boost::make_two_bit_color_map( boost::num_vertices(graph_), get(&VertexProperty::index, graph_)); 

(the graph_ argument is a member variable of type Graph above). My last change redefined VertexProperty::index to keep the vertex index number read from the file and not automatically generated by my code. My code previously created these indexes as consecutive indexes based on 0, increasing for each new vertex added to graph_ . With the change, I no longer want to assume that the indices are consecutive or they will remain less than graph_.size() - 1 ; I just do not want to put this restriction on users. However, I continued to use Vertex::index as a property for two_bit_color_map , and this led to an assertion error at runtime with the message:

 Assertion failed! Program: D:\school\thesis\code\build\test\bin\testChain.exe File: D:\programming\lib\boost\boost_1_54_0/boost/graph/two_bit_color_map.hpp, Line 72 Expression: (std::size_t)i < pm.n 

I know that I have VertexProperty::index values ​​that are higher or equal to graph_.size() ; my conclusion is correct, what is it that causes a statement error? I cannot find in BGL docs if there is any restriction on the index property used with make_two_bit_color_map .

So, my main question is : is it possible to use both internal properties, in particular property<vertex_index_t, int> , and the associated properties of the vertices with the BGL graph, or am I sticking to one or the other? (I would like to avoid re-introducing consecutive indexes with a new member in VertexProperty ). I suppose this might look something like this, although probably with a different exact syntax:

 typedef typename boost::adjacency_list< boost::listS, boost::listS, boost::bidirectionalS, property<vertex_index_t, int, property<VertexProperty>> > Graph; 

Answer 1

I think you are pursuing the wrong problem.

Most BGL search algorithms require an “index” → “vertex” mapping, where the index changes in the interval [0, num_vertices (g)). For example, DFS, BFS, connection component, A *, etc. You must first transfer each vertex to a "white" color. Instead, they essentially use a vector of size num_vertices (g).

In BGL, this central mapping is called the vertex_index property mapping, and the algorithms simply cannot work if this property map is incorrect.

So, your AFAICT task is to make sure that you can list your vertices correctly, in continuous mode. For this purpose, a vector combination with some additional hash map or STL is often required.

In any case, as you correct this index mapping error, you are likely to get some class that implements the mapping. Then your next step will be to teach Boost that this is a vertex index property.

If your MyMappingClass behaves like an associative container (i.e. implemented as an STL or Boost unordered_map map), you can pass it to DFS-like algorithms using idiom make_assoc_property_map(mymap) , where mymap is of type MyMappingClass.

Alternatively, you can do this in more detail, but more flexibly, as described below. This flexibility can translate to more efficient code.

Since this property is usually read-only, you add code like:

 namespace boost { template<> struct property_map< MyGraph, vertex_index_t > { typedef MyMappingClass const_type; //typedef const_type type; //-- we do not define type as "vertex_index_t" map is read-only }; } 

Further, your MyMappingClass can be a fully compatible BGL property base, i.e. it will have some declarations like

 class MyMappingClass { public: typedef readable_property_map_tag category; typedef int value_type; typedef value_type reference; typedef MyGraph::vertex_descriptor key_type; }; 

In addition, in order to work with such a configuration of BGL properties, you need to provide two different “get” functions: first, how to “get” a property map from your graph (it may be unnecessary or trivial if you create a class MyMappingClass a graph property).

The second function is how to "get" the value of the property (aka "vertex_descriptor") from the given value of the property key (aka integer in the interval [0, num_vertices (g))).

This second function may have a prototype similar to the following:

 MyMappingClass::value_type //aka index get( MyMappingClass mymap, MyMappingClass::key_type key) //aka vertex_descriptor 

(Note that according to BGL, MyMappingClass should be lightweight and copied).