Re: [Boost-users] [BGL] dfs on graphs with bundled-properties

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2007-03-22 09:55:16

On Wed, 2007-03-21 at 19:15 -0400, Naomi Fox wrote:
> So I define my graph class with bundled properties as so:
> 
>    struct MyV {
>       int numStars;
>    };
> 
>    struct MyE {
>       int numStars;
>    };
> 
>    typedef  adjacency_list<setS, setS, bidirectionalS, MyV, MyE>  MyGraph;
>
> Then in my main function, I make a MyGraph object and put in vertices 
> and edges, and assign property values.  That works fine.
[snip]
> Then I perform dfs on my graph
> 
>    depth_first_search(g, visitor(star_vis));

The problem in this case isn't the bundled properties, it's that
depth_first_search needs either a color map or an index map, neither of
which is available to it. I really wish we could make those error
messages make some sense, though :(

So, there are a couple of fixes. The goal is to associate each vertex
with an index, which is used to efficiently store extra data needed
inside the depth_first_search algorithm. There are two ways to do it.
The first involves putting the index into MyV, and then explicitly
passing an index map to depth_first_search:

  struct MyV {
    int numStars;
    int index;
  };

  // after you build the graph...
  int idx = 0;
  BGL_FORALL_VERTICES(v, g, Graph)
    g[v].index = idx++;

  // calling DFS
  depth_first_search(g, visitor(star_vis).
                     vertex_index_map(get(&MyV::index, g)));

Alternatively, only could use the more traditional properties approach
for the vertex index (MyV still works like it always did!), like this:

  struct MyV {
    int numStars;
  }; // as you originally had written

  // Tweak the graph type to stick a vertex_index in each vertex
  typedef  adjacency_list<setS, setS, bidirectionalS, 
                          property<vertex_index, int, MyV>, MyE>
    MyGraph;

  // after you build the graph...
  int idx = 0;
  BGL_FORALL_VERTICES(v, g, Graph)
    put(vertex_index, g, v, idx++);

  // Calling DFS, as you had before:
  depth_first_search(g, visitor(star_vis));

Despite the fact that I love bundled properties for everything else, I
like the second one better because the BGL knows how to automatically
look up the vertex_index property. 

  Cheers,
  Doug