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, 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
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...
Thanks Vladimir. I'm not sure that I've followed well your description. Here is my test implementation... but it doesn't work. Please, could you help me to discover the problem? Thanks in advance, Giulio typedef adjacency_list<vecS, vecS, directedS, no_property, no_property> MyGraph; typedef graph_traits<MyGraph>::vertex_descriptor Vertex; struct CycleDetector : public dfs_visitor<> { CycleDetector(std::vector<Vertex> p, std::vector<Vertex>& _cycle) : m_predecessor(p), cycle(_cycle) { } template <class Edge, class Graph> void back_edge(Edge e, Graph& g) { Vertex t = target(e, g); Vertex c = source(e, g); cycle.push_back(c); do { c = m_predecessor[c]; cycle.push_back(c); } while(c != t); } protected: std::vector<Vertex>& cycle; std::vector<Vertex> m_predecessor; }; int main(int,char*[]) { typedef std::pair<int,int> Edge; std::vector<Edge> edges; edges.push_back(Edge(0,1)); edges.push_back(Edge(1,2)); edges.push_back(Edge(2,3)); edges.push_back(Edge(3,1)); edges.push_back(Edge(3,4)); edges.push_back(Edge(4,0)); MyGraph g(edges.begin(), edges.end(), 5); std::vector<Vertex> cycle; std::vector<Vertex> p(num_vertices(g)); CycleDetector vis(p, cycle); depth_first_search(g, visitor(vis)); for (int i=0; i<cycle.size(); i++) std::cout << cycle[i] << ", "; std::cout << std::endl; return 0; } Vladimir Prus ha scritto:
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
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 <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
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
participants (4)
-
Elisha Berns -
Giulio Veronesi -
Simon Buchan -
Vladimir Prus