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@elixent.com ++44 (0)117 9175612

-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Giulio Veronesi Sent: 22 September 2005 11:05 Cc: boost-users@lists.boost.org 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users