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

From: Simon Buchan (simon_at_[hidden])
Date: 2005-09-22 02:36:55

Vladimir Prus wrote:
> 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
Sorry, this has nothing to do with the problem (not that I'm
not intersted in Boost.Graph!), but you are mixing spaces
and tabs in your example (I would be surprised if this was
visible in the html front-end). Did you copy-paste this code from
an editor with a 4-space tab?
I'm not going to hate you for it or anything, just be sure you
are careful that your code looks sensible on other ppl's editors.
(PS: I'm not one of those ppl who thinks the tab key should be
crow-bar'ed off every keyboard, I use tabs to indent, and spaces
to align, and I know which is which!)
Sorry if this came across as a little... holier than thou or
something, I really just mean this as an FYI...