Boost Graph Library: possible to combine Bundled P

问题:

I'm using this typedef for my BGL graph type, Graph, using struct VertexProperty as a bundled vertex property:

struct VertexProperty {
    BeamType beam;
    size_t index;
};

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

Before a recent change in my project, I'd been using the VertexProperty::index to construct a 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 from above). My recent change re-purposed VertexProperty::index to store a vertex index number read in from a file, rather than automatically generated by my code. My code had previously been creating these indices as 0-based consecutive indices, incremented for each new vertex added to graph_. With the change, I wish to no longer assume the indices are consecutive or that they will remain smaller than graph_.size() - 1; I just don't want to put that constraint on users. However, I continued to use Vertex::index as the property for the two_bit_color_map, and this led to a run-time assertion failure 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 I have VertexProperty::index values that go higher than or equal to graph_.size(); is my conclusion correct that this is what is causing the assertion failure? I can't find in the BGL docs if there is any such constraint on the index property used with make_two_bit_color_map.

So, my main quesion is: Is it possible to use both interior properties, specifically property<vertex_index_t, int> and bundled vertex properties with a BGL graph, or am I stuck with one or the other? (I'd like to avoid implementing the consecutive indices again with a new member in VertexProperty). I imagine this might look something like this, though probably with other exact syntax:

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

回答1:

I think you are chasing a wrong problem.

Majority of BGL search algorithms needs a mapping "index" --> "vertex" where index varies in interval [0, num_vertices(g)). For example, DFS, BFS, connectivity component, A*, etc. need to init each vertex to "white" color first. Instead, they essentially use a vector of size num_vertices(g).

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

So your task, AFAICT, is to make sure you can enumerate your vertices correctly, in a continuous way. Quite often one needs a combination of vector with some extra hash- or STL map for this purpose.

In any case, as you fix this index mapping issue you will likely end up with some class which implements the mapping. Then your next step will be to teach Boost that this is your vertex-index property.

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

Alternatively, you can do it in more elaborate but also more flexible way described below. This flexibility can translate into more efficient code.

Since usually this property is read-only, you add a 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 
};
}

Next, your class MyMappingClass could be a fully-compliant BGL property map, meaning it would 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;     
};

Besides, to work with such BGL-compliant property map one has to provide two different "get" functions: first is how to "get" property map from your graph (may be unnecessary or trivial if you make the class MyMappingClass a property of the graph).

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

This second function can have a prototype similar to following:

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

(Note, according to BGL, MyMappingClass should be a light-weight and copy constructable).