Search code examples
javajgraphthamiltonian-cyclehamiltonian-path

Finding Hamiltonian path and Hamiltonian cycle

I have a SimpleGraph in JGraphT and want to know if there is

  1. a Hamiltonian path

  2. a Hamiltonian cycle

And if one exists I'd also like to get it.

I only found TwoApproxMetricTSP and HamiltonianCycle.

But both require complete graphs.

One obvious solution is to add edges to my graph and make it a weighted graph with the weight of the added edges so high that they won't get used in the path.

But that would add lots of edges, which I'd like to avoid.

Is there a better way to get a Hamiltonian path/cycle without implementing an algorithm on my own?

Solution

  • The decision problem "does the graph contain a hamiltonian cycle (HC)" is NP-Complete. JGraphT does not include algorithms which work with incomplete graphs, so the only solution is to make the graph complete by adding edges with a large enough weight. Then, a HC exists if and only if you find a tour without any of the expensive edges you added. Notice that in the next release (1.1.1) there's a new exact algorithm (see master branch, Held Karp dynamic programming approach). This algorithm does not scale beyond 32 vertices. If you have a large graph, my recommendation would be to use TwoApproxMetricTSP. If you really need to solve (reasonable sized) graphs, you will have to resort to Linear Programming. Also have a look at the TSP solver Concorde. For most TSP applications, I would implement a dedicated, highly efficient data structure, e.g. store edges/neighbors in an array of integers.