Re: [Boost-users] [BGL] detect cycles in a directed graph

From: Elisha Berns (e.berns_at_[hidden])
Date: 2005-09-22 17:22:51

Hi,

I need to understand and implement this algorithm also (finding the path
of vertices that comprise a cycle).

What isn't clear here is how the predecessor map gets initialized with
valid vertices?  I see that there is a built-in property-map for
predecessor values, but not where it gets set or initialized.  If you
need to call put(...) for every vertex that raises another issue: if a
vertex has multiple in-edges what is its proper predecessor, if there is
one at all in that scenario?

Elisha

> On Thursday 22 September 2005 10:50, Giulio Veronesi wrote:
> 
> [replying to list, no need to keep this off-list]
> 
> > Vladimir Prus ha scritto:
> > > Giulio Veronesi wrote:
> > >>assistance in the following problem: "get all the edges of a
cycle".
> > >
> > > Of which cycle?
> > >
> > > If you want to get at least one cycle in a graph that has one,
then
> you
> > > need to create a visitor that implements "back_edge" method and
use
> > > predecessor map to traverse the cycle in reverse order.
> >
> > Yes! Only one cycle. Please, could you give me a pratical example
(just
> > the pseudo code)? I've very little experience with BGL. Do you
intend
> > something like this?
> >
> > template <class Edge, class Graph>
> > void back_edge(Edge e, Graph& g) {
> >      clinks.push_back(TLink(source(e, g), target(e, g)));
> > }
> >
> > where:
> >
> > typedef std::pair<int,int> TLink;
> > vector<TLink> clinks;
> 
> Something more like:
> 
> struct vis
> {
> 	vis(vector_property_map<int> predecessor)
>     : m_predecessor(predecessor) {}
> 
> 	template<......>
>     void back_edge(Edge e, Graph& g)
>     {
> 		vertex_descriptor t = target(e, g);
>         vertex_description c = source(e, g);
> 		vector<vertex_descriptor> cycle;
> 		cycle.push_back(c);
> 	    do {
> 			c = m_predecessor[c];
> 			cycle.push_back(c);
> 		} while(c != t);
>     }
> };
> 
> On construction, you need to pass the same vector_property_map both to
the
> visitor and the depth_first_search algorithm.
> 
> Yes, this is untested code, sorry :-(
> 
> - Volodya
> 
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users