0

In the context of boost-graph, i am using undirected_dfs to find the cycles of the undirected graph. It works well and fast.

Unfortunately, undirected_dfs does not provide the cycles based on the "basic cycles".

In the example below, the 2 basic cycles found are {0,1,3,2,0} and {3,2,4,5,3}.

But the big cycle {0,1,3,5,4,2,0} is not found.

Is there an algo to find the biggest cycles of the undirected graph ?

Thanks

Remark: The graph contains less than 100 nodes. My problem is certainly small enough even for my "old" PC.

enter image description here

alvaro562003
  • 678
  • 1
  • 6
  • 27
  • 3
    Don't know boost_graph, but finding the biggest cycle also solves the hamiltonian path problem, which is NP-complete, so there is no *fast* solution. Related: http://stackoverflow.com/questions/4530120/finding-the-longest-cycle-in-a-directed-graph-using-dfs – Joseph Ireland Dec 08 '16 at 15:29
  • Thank you. I will inquire on hamiltonian path pb. I would take even a slow solution. I have less than 100 nodes. – alvaro562003 Dec 08 '16 at 15:43

0 Answers0