
Boost Users : 
From: Elisha Berns (e.berns_at_[hidden])
Date: 20050725 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 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 mailing list
> Boostusers_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boostusers
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