Re: [Boost-users] Identify cycles in a undirected graph

Subject: Re: [Boost-users] Identify cycles in a undirected graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-03-08 19:33:35

On Thu, 8 Mar 2012, ddboy40 wrote:

> Sorry for the Doble posting,
> wast'nt yet register to the mailing list.
> Cheers!
>
> hi Folks, I've played around with the following example:
>
> struct detect_loops : public boost::dfs_visitor<>
> {
> template <class Edge, class Graph>
> void back_edge(Edge e, const Graph& g) {
>    std::cout << source(e, g)
>        << " -- "
>        << target(e, g) << "\n";
> }
> };
>
> 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(4,5));
> edges.push_back(Edge(5,0));
> edges.push_back(Edge(4,0));
> edges.push_back(Edge(5,6));
> edges.push_back(Edge(2,6));
>
> typedef adjacency_list< vecS, vecS, undirectedS,
>    no_property,
>    property<edge_color_t, default_color_type> > graph_t;
> typedef graph_traits<graph_t>::vertex_descriptor vertex_t;
>
> graph_t g(edges.begin(), edges.end(), 7);
>
> std::cout << "back edges:\n";
> detect_loops vis;
> undirected_dfs(g,
> root_vertex(vertex_t(0)).visitor(vis).edge_color_map(get(edge_color, g)));
> std::cout << std::endl;
>
> return 0;
> }
>
> However, I donot know how and where to place the predeccesor recorder.
> Secondly, I actually need but all the cycles, i.e. these may not have only
> distinct verterces. i.e some vertices may occur repeated in certain circles.
> My example above has 3 distinct cycles I guess and thats wha t the the
> back_edge() gives. But, I'll like to have all the hamiltonian cycles (hope
> they call it like that ;)). Thanks in advance for the tipps.

Finding all Hamiltonian cycles will be difficult (see 
http://en.wikipedia.org/wiki/Hamiltonian_cycle_problem).  Are you sure 
that's what you want -- all cycles that go through each vertex exactly 
once?  Or do you want all cycles of any length?  Or something else?

-- Jeremiah Willcock