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

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

Hi Doug,

Thanks for the reply, however long it took.  I realize you must be
swamped with questions and work.  The reply is still very useful.  The
only thing that I haven't determined yet is whether the results will be
different for the two methods: 1) a straight depth_first_search that
just ignores any back edges (and doesn't throw not_a_dag) and 2) using a
filtered graph approach.  But I'll test it all and see.

Forgive my seeming thick on this matter, but still, there is some
mystery to me as to why the filtered graph approach will work at all.
So I just want to get clear on who does what to whom here, and why.

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).
3) Construct an edge filter that will eliminate edges that have 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?  And then the filtered_graph eliminates the gray edge?
Something's missing, but I can't quite articulate it.

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!

But this way, I don't get where the vertices get 'colored' and how they
then get 'eliminated'.

Thanks for your patience and clarity here.

Yours,

Elisha
 
> 
> Hello,
> 
> My apologies for the long delay in replying; I hope it's still useful
:(
> 
> On Jul 8, 2005, at 2:00 PM, Elisha Berns wrote:
> > Thanks again for a reply.  Excuse my confusion and lack of
> > understanding, but I don't yet understand what you explain below:
> >
> > "You can store a copy of the color map in the edge filter predicate"
> >
> > I think I get this, is this what you mean (here are the definitions
for
> > this part):
> >
> > typedef adjacency_list
> > <
> > 	vecS, vecS, directedS,
> > 	property< vertex_color_t, default_color_type,
> > 		property< vertex_type_t, VertexType > >
> >> Graph;
> >
> > typedef property_map<Graph, vertex_color_t>::type VertexColorMap;
> >
> > template <typename Graph, typename VertexColorMap>
> > struct valid_edge {
> > 	valid_edge() { }
> > 	valid_edge(Graph& graph, VertexColorMap color_map)
> > 		: m_graph(graph),	m_color_map(color_map) { }
> > 	template <typename Edge>
> > 	bool operator()(const Edge& e) const
> > 	{
> > 		return ( Color::gray() != get(m_color_map, target(e,
> > m_graph)) );
> > 	}
> > 	VertexColorMap m_color_map;
> > 	Graph& m_graph;
> > };
> >
> > And the code to setup the above:
> >
> > valid_edge<Graph, VertexColorMap>
> > filter(m_graph, get(vertex_color, m_graph));
> >
> > filtered_graph<Graph, valid_edge<Graph, VertexColorMap> >
> > fg(m_graph, filter);
> 
> Yes, that's exactly what I meant.
> 
> > But the next part of what you write isn't clear:
> >
> > "pass the same color map to depth_first_search; then you filter out
any
> > edges whose targets are gray"
> >
> > So which graph gets sorted with depth_first_search?  The filter
graph I
> > presume?
> 
> Yes, the filtered_graph.
> 
> >   But I thought the constructor for filter_graph will call the
> > predicate function for every edge without having to do a
> > depth_first_search???
> 
> When depth_first_search asks the filtered_graph to list the edges it
> knows about, filtered_graph will first ask the predicate which edges
it
> should make visible.
> 
> > Also, if the predicate has only a copy of the vertex color map then
how
> > are the results from depth_first_search going to be reflected in the
> > predicate object?
> 
> Even though you have multiple copies of the color map returned by
> get(vertex_color, m_graph) (one in the edge predicate and one that's
> passed to depth_first_search), they all refer to the same information,
> e.g., the color value stored on the vertices of the graph nodes.
> 
> 	Doug
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users