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

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::type VertexColorMap;

template 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 filter(m_graph, get(vertex_color, m_graph));

filtered_graph > 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users