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

From: Andrea Olgiati (Andrea.Olgiati_at_[hidden])
Date: 2005-09-23 03:04:13

Giulio,

Here's an idea. You say you want to list all the vertices that make up
any one of the (potentially very numerours) cycles that originate on a
vertex X. If  _any_ cycle will do, how about the shortest? You can use
Dijkstra. From
http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html: "Also
you can record the shortest paths tree in a predecessor map: for each
vertex u in V, p[u] will be the predecessor of u in the shortest paths
tree (unless p[u] = u, in which case u is either the source or a vertex
unreachable from the source)."

I don't think Dijkstra will work on a path that looks like V->X->Y->U->V
(ie, a cycle). But, to get around this, you do know that U->V is an
edge, so you can compute the shortest path between V and U, and know
that there's an edge between U and V.

HTH,
Andrea

--
Andrea Olgiati - Elixent - Castlemead, Lwr Castle St., Bristol BS1 3AG,
UK
andrea.olgiati_at_[hidden]                             ++44 (0)117
9175612 
  
> -----Original Message-----
> From: boost-users-bounces_at_[hidden] 
> [mailto:boost-users-bounces_at_[hidden]] On Behalf Of 
> Giulio Veronesi
> Sent: 22 September 2005 11:05
> Cc: boost-users_at_[hidden]
> Subject: Re: [Boost-users] [BGL] detect cycles in a directed graph
> 
> Thanks Vladimir.
> 
> I'm not sure that I've followed well your description. Here 
> is my test implementation... but it doesn't work.
> 
> Please, could you help me to discover the problem?
> 
> Thanks in advance,
> Giulio
> 
> 
> typedef adjacency_list<vecS, vecS, directedS,
> 		       no_property, no_property> MyGraph;
> 
> typedef graph_traits<MyGraph>::vertex_descriptor Vertex;
> 
> 
> struct CycleDetector : public dfs_visitor<> {
>    CycleDetector(std::vector<Vertex> p,
> 		std::vector<Vertex>& _cycle) :
>      m_predecessor(p), cycle(_cycle)  { }
> 
>    template <class Edge, class Graph>
>    void back_edge(Edge e, Graph& g)
>    {
>      Vertex t = target(e, g);
>      Vertex c = source(e, g);
> 	
>      cycle.push_back(c);
>      do {
>        c = m_predecessor[c];
>        cycle.push_back(c);
>      } while(c != t);
>    }
> 
> protected:
>    std::vector<Vertex>& cycle;
>    std::vector<Vertex> m_predecessor;
> };
> 
> int main(int,char*[])
> {
> 
>    typedef std::pair<int,int> Edge;
>    std::vector<Edge> edges;
>    edges.push_back(Edge(0,1));
>    edges.push_back(Edge(1,2));
>    edges.push_back(Edge(2,3));
>    edges.push_back(Edge(3,1));
>    edges.push_back(Edge(3,4));
>    edges.push_back(Edge(4,0));
> 
>    MyGraph g(edges.begin(), edges.end(), 5);
> 
>    std::vector<Vertex> cycle;
>    std::vector<Vertex> p(num_vertices(g));
>    CycleDetector vis(p, cycle);
>    depth_first_search(g, visitor(vis));
> 
>    for (int i=0; i<cycle.size(); i++)
>      std::cout << cycle[i] << ", ";
>    std::cout << std::endl;
> 
>    return 0;
> }
> 
> 
> Vladimir Prus ha scritto:
> >>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
> 
>