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

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 void back_edge(Edge e, const Graph& g) { std::cout << source(e, g) << " -- " << target(e, g) << "\n"; } };

int main(int,char*[]) {

typedef std::pair 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 > graph_t; typedef graph_traits::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