Search code examples
c++boostsubgraph

Graph traits of a subgraph

I have a graph and I want to change its type to subgraph to be able to divide it into more subgraphs to get a more ordinate print with graphviz. The problem is that when I add the subgraph propriety to my graph the vertex descriptor is no longer working.

Code before modification:

    #include "Node.cpp"
    #include <boost/graph/adjacency_list.hpp>
    #include <boost/property_map/property_map.hpp>
    #include <boost/graph/graph_traits.hpp>
    #include <boost/graph/subgraph.hpp>

    using namespace boost;

    typedef adjacency_list<vecS, vecS, directedS, Node, property < edge_weight_t, float > > mygraph;
    typedef graph_traits < mygraph >::vertex_descriptor vertex_descriptor;
    ...

Code after changing the graph to subgraph:

    #include "Node.cpp"
    #include <boost/graph/adjacency_list.hpp>
    #include <boost/property_map/property_map.hpp>
    #include <boost/graph/graph_traits.hpp>
    #include <boost/graph/subgraph.hpp>

    using namespace boost;

   typedef subgraph<adjacency_list<vecS, vecS, directedS, Node, property < edge_weight_t, float > > >mygraph;
   typedef graph_traits < mygraph >::vertex_descriptor vertex_descriptor;   //ERROR
   ...

What is the problem? And how can I fix it?

Solution

  • The problems isn't with the traits per se.

    The subgraph requires an edge_index property, because it stores a local mapping:

        typedef std::map<edge_index_type, edge_descriptor> LocalEdgeMap;
    LocalEdgeMap m_local_edge; // global -> local

    Because there's no edge_index_t property, the map's key type evaluates to void.

    This is documented here: http://www.boost.org/doc/libs/1_55_0b1/libs/graph/doc/subgraph.html

    The underlying graph type is required to have vertex_index and edge_index internal properties, so we add an edge index property to the adjacency list. We do not need to add a vertex index properety because that is built in to the adjacency_list. We will be building the graph and subgraphs in Figure 1, so we will need a total of six vertices

    Consider adding an edge index:

    typedef subgraph<adjacency_list<vecS, vecS, directedS, Node, property < edge_index_t, index > > >mygraph;
typedef graph_traits < mygraph >::vertex_descriptor vertex_descriptor;   // COMPILES