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

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