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

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-07-25 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 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