
Boost Users : 
Subject: Re: [Boostusers] Identify cycles in a undirected graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 20120308 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
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net