
Boost Users : 
From: Doug Gregor (dgregor_at_[hidden])
Date: 20050725 16:44:54
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 DFSVISIT 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 outedges. The
filtered_graph applies the filter predicate onthefly, so as we're
stepping through the outedge 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 DFSVISIT 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 outedges 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net