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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2005-09-22 02:00:52

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