
Boost Users : 
From: Doug Gregor (dgregor_at_[hidden])
Date: 20050722 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net