Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project!

## [jgrapht-users] Fwd: Bug in HamiltonianCycle

 [jgrapht-users] Fwd: Bug in HamiltonianCycle From: Joris Kinable - 2014-04-24 15:15:37 Attachments: Message as HTML ```This reply was supposed to go over the mailing list. br, Joris ---------- Forwarded message ---------- From: Joris Kinable Date: Wed, Apr 23, 2014 at 1:38 PM Subject: Re: [jgrapht-users] Bug in HamiltonianCycle To: Simon Heinen Hi Simon, In your post you have several questions. Q1: Is there also a Hamiltonian cycle algorithm implementation which produces an exact solution? No there is not. HC is an NP-hard problem, meaning that it is very difficult to solve. There are entire libraries dedicated to solving just this problem, which is way beyond jgrapht. What you might want to do is to look into Concorde (http://www.math.uwaterloo.ca/tsp/concorde.html) which currently is the fastest solver. It can solve the HC problem to optimality for very large instances in reasonable time. Q2: Is there an implementation which yields better but not necessary optimal solutions? Currently not, but I've checked the implementation and there are fairly easy ways to improve the quality of the solutions with a reasonable increase in runtime. What you could do is take the solution produced by the Hamiltonian cycle implementation and run a local search on top of it, thereby performing a certain number of so-called 2-opt moves ( http://en.wikipedia.org/wiki/2-opt). This procedure is known to give good results in general (but obviously doesn't guarantee to find the optimal solution). What I would do is the following: 1. Use HamiltonianCycle.java to get a initial solution 2. Given the tour, find the best 2-opt move out of all possible 2-opt moves. If this move improves the solution, perform the move. If not, stop. This is very easy and fast to implement, especially if you are dealing with complete graphs. This would also make a nice extension of the HamiltonianCycle class implementation :). Q3: Is there a bug in the code? That's difficult to say from your example as there are so many data points. From the looks of it, the solution seems to satisfy the definition of a hamiltonian cycle: -every vertex has an incoming and an outgoing edge -there are no subtours e.g. it's one tour, not a collection of several tours. Check whether your solution meets these criteria. Due to the greedy nature of the algorithm the resulting tour may however be very far away from any optimal solution. In the example you showed us, performing 2-opt moves will most likely provide you with the optimal solution. Note: the HamiltonianCycle class requires that your graph is complete (check this!), see comment below. Also, to guarantee a 2-approximation, all edge weights must satisfy the triangle inequality. Note to developers: We should update the java doc of HamiltonianCycle.java. In the code I found this: * 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)wrote: > Hello jGraphT users, > I think I found a bug in the HamiltonianCycle algorithm. I wrote it > down in detail here: > > https://github.com/jgrapht/jgrapht/issues/83 > > If someone has an idea why this happens, it would be great to get some > feedback about this. > > Thanks, > Simon > > > ------------------------------------------------------------------------------ > Start Your Social Network Today - Download eXo Platform > Build your Enterprise Intranet with eXo Platform Software > Java Based Open Source Intranet - Social, Extensible, Cloud Ready > Get Started Now And Turn Your Intranet Into A Collaboration Platform > http://p.sf.net/sfu/ExoPlatform > _______________________________________________ > jgrapht-users mailing list > jgrapht-users@... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users > ```

 [jgrapht-users] Bug in HamiltonianCycle From: Simon Heinen - 2014-04-22 08:52:11 ```Hello jGraphT users, I think I found a bug in the HamiltonianCycle algorithm. I wrote it down in detail here: https://github.com/jgrapht/jgrapht/issues/83 If someone has an idea why this happens, it would be great to get some feedback about this. Thanks, Simon ```
 [jgrapht-users] Fwd: Bug in HamiltonianCycle From: Joris Kinable - 2014-04-24 15:15:37 Attachments: Message as HTML ```This reply was supposed to go over the mailing list. br, Joris ---------- Forwarded message ---------- From: Joris Kinable Date: Wed, Apr 23, 2014 at 1:38 PM Subject: Re: [jgrapht-users] Bug in HamiltonianCycle To: Simon Heinen Hi Simon, In your post you have several questions. Q1: Is there also a Hamiltonian cycle algorithm implementation which produces an exact solution? No there is not. HC is an NP-hard problem, meaning that it is very difficult to solve. There are entire libraries dedicated to solving just this problem, which is way beyond jgrapht. What you might want to do is to look into Concorde (http://www.math.uwaterloo.ca/tsp/concorde.html) which currently is the fastest solver. It can solve the HC problem to optimality for very large instances in reasonable time. Q2: Is there an implementation which yields better but not necessary optimal solutions? Currently not, but I've checked the implementation and there are fairly easy ways to improve the quality of the solutions with a reasonable increase in runtime. What you could do is take the solution produced by the Hamiltonian cycle implementation and run a local search on top of it, thereby performing a certain number of so-called 2-opt moves ( http://en.wikipedia.org/wiki/2-opt). This procedure is known to give good results in general (but obviously doesn't guarantee to find the optimal solution). What I would do is the following: 1. Use HamiltonianCycle.java to get a initial solution 2. Given the tour, find the best 2-opt move out of all possible 2-opt moves. If this move improves the solution, perform the move. If not, stop. This is very easy and fast to implement, especially if you are dealing with complete graphs. This would also make a nice extension of the HamiltonianCycle class implementation :). Q3: Is there a bug in the code? That's difficult to say from your example as there are so many data points. From the looks of it, the solution seems to satisfy the definition of a hamiltonian cycle: -every vertex has an incoming and an outgoing edge -there are no subtours e.g. it's one tour, not a collection of several tours. Check whether your solution meets these criteria. Due to the greedy nature of the algorithm the resulting tour may however be very far away from any optimal solution. In the example you showed us, performing 2-opt moves will most likely provide you with the optimal solution. Note: the HamiltonianCycle class requires that your graph is complete (check this!), see comment below. Also, to guarantee a 2-approximation, all edge weights must satisfy the triangle inequality. Note to developers: We should update the java doc of HamiltonianCycle.java. In the code I found this: * 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)wrote: > Hello jGraphT users, > I think I found a bug in the HamiltonianCycle algorithm. I wrote it > down in detail here: > > https://github.com/jgrapht/jgrapht/issues/83 > > If someone has an idea why this happens, it would be great to get some > feedback about this. > > Thanks, > Simon > > > ------------------------------------------------------------------------------ > Start Your Social Network Today - Download eXo Platform > Build your Enterprise Intranet with eXo Platform Software > Java Based Open Source Intranet - Social, Extensible, Cloud Ready > Get Started Now And Turn Your Intranet Into A Collaboration Platform > http://p.sf.net/sfu/ExoPlatform > _______________________________________________ > jgrapht-users mailing list > jgrapht-users@... > https://lists.sourceforge.net/lists/listinfo/jgrapht-users > ```