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

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