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

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-07-22 14:05:23

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