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

22 Sep 2005


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

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

Simon Buchan