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