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

22 Sep 2005

      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 
void back_edge(Edge e, Graph& g) {
     clinks.push_back(TLink(source(e, g), target(e, g)));
}
where:
typedef std::pair 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 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