[jgrapht-users] Question on HamiltonianCycle From: Brian Feeny - 2012-12-21 05:14:56 ```I am relatively new to JGraphT and I am trying to get a solution for a HamiltonianCycle. I have the following graph loaded: All Vertices [5, 4, 3, 2, 1, 0] All Edges (5 : 4) (5 : 3) (4 : 3) (4 : 2) (3 : 2) (3 : 1) (2 : 1) (0 : 5) (0 : 4) (0 : 3) (0 : 2) (0 : 1) I realize this is not a complete graph, but it is a graph for which there should be a cycle that can be computed. My object however is null: List output = HamiltonianCycle.getApproximateOptimalForCompleteGraph(g); is there any reason the above should not work? I can't make the graph 100% complete, as it involves too many points (100k+), and it would not be computationally feasible to compute a complete graph, but I still need to find a HamiltonianCycle. Thank you for any help. Brian ```
 Re: [jgrapht-users] Question on HamiltonianCycle From: H.N. de Ridder - 2012-12-21 16:30:53 ```On Fri, Dec 21, 2012 at 10:11:42AM -0500, Brian Feeny wrote: Do you need a optimal solution or will an approximation (like the getApproximateOptimalForCompleteGraph function computes) do? If your graphs satisfy the triangle inequality, a simple minimum spanning tree can be used to generate a factor 2 approximation. See e.g. Approximation Algorithms by Vazirani. Ernst > > I will look at making my own type of function which may work for my data set. I cannot just add heavily weighted edges, > as this still creates complexity. The issue with 100,000+ points isn't just in the calculation of the distances, but in the size > of all the edges, which causes every operation to slow. > > I am going to study the source code for the HamiltonianClass and see if I can just do something like iterate through all vertices, > selecting a best path, until I have traversed all vertices. The issue that lies in there, is that its very possible to eliminate vertices in > such a way that you now have no edges which may be needed to complete the path. Now this is why I see the algorithm included > works, because no matter what, there will always be a path between any two vertices, so it should not be able to fail on a complete graph. > > Something I write, may in fact be able to fail on an incomplete graph, but all I am concerned about is it not failing on my graph. > > My vertices have minimum of paths to two other vertices, and in some case many more (20+). > > If anyone knows of an algorithm for Hamiltonian Path that can solve for less than complete graphs, please let me know, as it would be useful > for me. > > Brian > > On Dec 21, 2012, at 8:23 AM, "H.N. de Ridder" wrote: > > > On Fri, Dec 21, 2012 at 12:14:46AM -0500, Brian Feeny wrote: > > > > Hello Brian, > > > >> I am relatively new to JGraphT and I am trying to get a solution for a HamiltonianCycle. > >> > >> I realize this is not a complete graph, but it is a graph for which there should be a cycle that can be computed. My object however is null: > >> > >> List output = HamiltonianCycle.getApproximateOptimalForCompleteGraph(g); > >> > >> is there any reason the above should not work? I can't make the graph 100% complete, as it involves too many points (100k+), and it would not be computationally feasible to compute a complete graph, but I still need > >> to find a HamiltonianCycle. Thank you for any help. > > > > The reason it doesn't work is that your graph isn't a complete graph (which > > has an edge between every pair of vertices). The documentation for the > > method says: > > > > This method will return an approximate minimal traveling salesman tour > > (hamiltonian cycle). This algorithm requires that the graph be complete and > > the triangle inequality exists (if x,y,z are vertices then d(x,y)+d(y,z) > > > > In fact, when you check the code, you'll see that one of the first things > > this method does, is check whether the input graph is complete and, if not, > > return null. > > > > So you can do one of two things: Write a less specific (approximation) > > algorithm for the Hamitonian Cycle problem (and maybe donate it to the > > JGraphT project), or maybe add (very heavy) edges to your graph until it is > > complete and then use getApproximateOptimalForCompleteGraph. I didn't think > > this one through though, so you'll have to verify yourself whether it can be > > made to work. -- Information System on Graph Classes and their Inclusions (ISGCI) http://www.graphclasses.org ```