org.jgrapht.alg
Class HamiltonianCycle

java.lang.Object
  extended by org.jgrapht.alg.HamiltonianCycle

public class HamiltonianCycle
extends java.lang.Object

This class will deal with finding the optimal or approximately optimal minimum tour (hamiltonian cycle) or commonly known as the Traveling Salesman Problem.

Author:
Andrew Newell

Constructor Summary
HamiltonianCycle()
           
 
Method Summary
static
<V,E> java.util.List<V>
getApproximateOptimalForCompleteGraph(SimpleWeightedGraph<V,E> g)
          This method will return an approximate minimal traveling salesman tour (hamiltonian cycle).
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

HamiltonianCycle

public HamiltonianCycle()
Method Detail

getApproximateOptimalForCompleteGraph

public static <V,E> java.util.List<V> getApproximateOptimalForCompleteGraph(SimpleWeightedGraph<V,E> g)
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)
Type Parameters:
V -
E -
Parameters:
g - is the graph to find the optimal tour for.
Returns:
The optimal tour as a list of vertices.