Re: [Boost-users] BGL Question/Advice which algorithm to use

From: Elisha Berns (e.berns_at_[hidden])
Date: 2005-07-25 21:57:52

Hi Doug,

Thanks doubly for the clear explanation.  Finally the pieces are making
(more) sense here.  Just one question:

> Here's the first minor issue. At this point, we should initialize the
> color map with all white vertices.

I assume you mean to say that it is necessary to call 'put(...)' on this
property map for every vertex that is in the graph to initialize each
vertex's color to white?  Otherwise it won't happen...?

Elisha

> Hi Elisha,
> 
> On Jul 25, 2005, at 12:35 PM, Elisha Berns wrote:
> > So lets start at the top, so that hopefully you can spot immediately
> > the
> > hole in my (mis)understanding here:
> >
> > 1) Construct a graph that is mostly, predominately, a DAG.
> > 2) This graph doesn't have any valid color properties yet, because
is
> > hasn't been traversed in any way (this is the point that seemingly
is
> > hanging me up).
> 
> Here's the first minor issue. At this point, we should initialize the
> color map with all white vertices.
> 
> > 3) Construct an edge filter that will eliminate edges that have the
> > color 'gray'.
> 
> We want to eliminate edges whose target vertex has the color gray.
> 
> > 4) Construct a filtered_graph using the above edge filter and a copy
of
> > the color map from the 'original' graph that isn't quite a DAG.
> > 5) Run a depth first search on the filtered graph and voila the
> > resulting filtered graph will now be a DAG in depth first search
order.
> >
> > So where do the vertices get colored gray?  Presumably during the
> > depth_first_search operation, right?  Does that mean
depth_first_search
> > first colors the vertices, then calls the filtered_graph's edge
> > predicate?
> 
> Yes. Check out the DFS-VISIT pseudo in the documentation here:
> 
> 	http://www.boost.org/libs/graph/doc/depth_first_search.html
> 
> As soon as DFS sees a vertex "u" for the first time (so u is white),
it
> colors it gray in the property map, then visits its out-edges. The
> filtered_graph applies the filter predicate on-the-fly, so as we're
> stepping through the out-edge list of the underlying graph, it's
> filtering out any edges (u, v) such that v is colored gray.
> 
> It's like we took the loop from DFS-VISIT that looks like this:
> 
>    for each v in Adj[u]
>      // do something
> 
> and made it:
> 
>    for each v in Adj[u]
>      if color[v] != gray
>        // do something
> 
> 
> >   And then the filtered_graph eliminates the gray edge?
> > Something's missing, but I can't quite articulate it.
> 
> I'm guessing that you're expecting that the edge filter predicate is
> applied once, when the filtered_graph is constructed, instead of
lazily
> as we iterate through the out-edges for each vertex. It's very likely
> that our documentation doesn't make this abundantly clear.
> 
> > On the other hand, if you wrote that you first run a
depth_first_search
> > that ignores back edges on the graph in order to first color the
> > vertices, that would be clear to me.  And then of course you run
that
> > graph with its initialized color_map through the filtered_graph
using
> > the edge predicate that eliminates all edges with color gray.  That
> > would make perfect sense to my small mind!
> 
> We might get stuck if we did this, because all vertices in the graph
> could end up colored black by the depth_first_search and we'd do
> nothing on the second pass.
> 
> 	Doug
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users