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

From: Giulio Veronesi (giulio_veronesi_at_[hidden])
Date: 2005-09-22 05:04:51

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