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

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,

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

Hi, I need to understand and implement this algorithm also (finding the path of vertices that comprise a cycle). What isn't clear here is how the predecessor map gets initialized with valid vertices? I see that there is a built-in property-map for predecessor values, but not where it gets set or initialized. If you need to call put(...) for every vertex that raises another issue: if a vertex has multiple in-edges what is its proper predecessor, if there is one at all in that scenario? Elisha then the

visitor and the depth_first_search algorithm.

Yes, this is untested code, sorry :-(

- Volodya

_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users