From: Andrea Olgiati (Andrea.Olgiati_at_[hidden])
Date: 2005-09-23 03:04:13
Giulio,
Here's an idea. You say you want to list all the vertices that make up
any one of the (potentially very numerours) cycles that originate on a
vertex X. If _any_ cycle will do, how about the shortest? You can use
Dijkstra. From
http://www.boost.org/libs/graph/doc/dijkstra_shortest_paths.html: "Also
you can record the shortest paths tree in a predecessor map: for each
vertex u in V, p[u] will be the predecessor of u in the shortest paths
tree (unless p[u] = u, in which case u is either the source or a vertex
unreachable from the source)."
I don't think Dijkstra will work on a path that looks like V->X->Y->U->V
(ie, a cycle). But, to get around this, you do know that U->V is an
edge, so you can compute the shortest path between V and U, and know
that there's an edge between U and V.
HTH,
Andrea
--
Andrea Olgiati - Elixent - Castlemead, Lwr Castle St., Bristol BS1 3AG,
UK
andrea.olgiati_at_[hidden] ++44 (0)117
9175612
> -----Original Message-----
> From: boost-users-bounces_at_[hidden]
> [mailto:boost-users-bounces_at_[hidden]] On Behalf Of
> Giulio Veronesi
> Sent: 22 September 2005 11:05
> Cc: boost-users_at_[hidden]
> Subject: Re: [Boost-users] [BGL] detect cycles in a directed graph
>
> 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
> >
> >
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://listarchives.boost.org/mailman/listinfo.cgi/boost-users
>
>