Boost logo

Boost Users :

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


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.


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at