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

From: Elisha Berns (e.berns_at_[hidden])
Date: 2005-07-08 14:00:10

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);

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?  But I thought the constructor for filter_graph will call the
predicate function for every edge without having to do a
depth_first_search???  

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?

Anyways, those last two steps don't make sense yet.

Thanks for a clarification.

Yours,

Elisha

> > What test is there to determine whether an edge is a back-edge that
can
> > be used inside a filter predicate of the filter_graph?
> 
> You can use the (vertex) color map to determine if an edge is a back
> edge. You can store a copy of the color map in the edge filter
> predicate, and pass the same color map to depth_first_search; then you
> filter out any edges whose targets are gray.
> 
> 	Doug
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users