What Is a Hamiltonian Circuit?
A Hamiltonian Circuit is a cyclic Graph (or sub-graph) such that each vertex can only be accessed in a single path. They also contain all the vertices in the given graph. As such, all Graphs containing Hamiltonian Circuits have at least three vertices. Hamiltonian circuits are cyclic graphs with n vertices and edges. As such, each vertex in the circuit has a degree of two.
There are a number of different theorems that can be used to determine the Hamiltonicity of a graph. The two simplest theorems to look at are Dirac's Theorem and Ore's Theorem. Dirac's Theorem states that a simple graph has a Hamiltonian circuit if it has at least three vertices, all of which have a degree of at least number of vertices/2. Ore's Theorem states that for a simple graph with at least three vertices, the graph has a Hamiltonian circuit if each pair of vertices that are not adjacent have a combined degree greater than or equal to the number of vertices.
Finding Hamiltonian Circuits in Unweighted Graphs
Based on the above properties of Hamiltonian circuits, let's examine an algorithm to find these circuits in unweighted graphs. Kruskal's algorithm to find a minimum spanning tree is a good place to start because it deals with reassembling edges on a graph. Simply by applying Kruskal's algorithm with a couple checks, finding a Hamiltonian circuit in a graph becomes pretty simple. Simply reassemble the edges such that no Vertex has a degree of two, and that no circuit is created. Order the vertices based on degree, and deal with the vertices of degree two first using Kruskal's algorithm. This helps assure that at the end, no additional vertices will have a degree that isn't two. Next, deal with the vertices of degree greater than two. For each vertex, choose an edge that satisfies the above conditions. Repeat until any edge choice would violate the tree property.
Wait, the purpose of the algorithm is to find a Hamiltonian circuit though? By the time this portion of the algorithm finishes, the final result will be a singly-linked list with a head and tail node. Every other vertex will have a degree of two. Simply connect the head and tail nodes to complete the Hamiltonian circuit.
Travelling Salesman Problem
The goal in finding Hamiltonian circuits in weighted graphs is to find the circuit with the lowest total cost. This is also called the Travelling Salesman Problem, and it is considered an NP problem, meaning there is no known polynomial time solution. In this section, we will explore the Held-Karp algorithm, which is the best known solution, solving the Travelling Salesman Problem within 0.5% of the optimal solution. It has a runtime complexity of O(n2 * 2n).
The Held-Karp algorithm works by finding a Vertex such that the sum of the distances across its two lowest-cost Edges is less than that of any other Vertex. It then finds the minimum spanning tree along the remaining Vertices using Prim's algorithm, which is essentially the same as Dijkstra's algorithm except it doesn't violate the Tree property. The other constraint it places is that no Vertex can have a degree greater than two in the final Hamiltonian circuit.
My Held-Karp implementation uses my Graph implementation found here.
package datastructures;
import java.util.*;
/**
* This class solves the Travelling Salesman Problem
* for a given Graph using the Held-Karp algorithm.
* It finds the optimal Hamiltonian circuit using Prim's
* algorithm. Initially, the Edge with the sum of the two lowest
* Connections is set aside. Then, a Minimum Spanning Tree is found
* with the two points the initial Edge is connected to as the end-points.
* Once an MST has been established, the two unconnected Edges are joined,
* completing the Hamiltonian circuit.
*
* Note that this class does NOT maintain the integrity of the data in the
* given Graph. So it is recommended that a copy of the Graph is made before
* passing it to a TSPHeldKarp object.
* */
public class TSPHeldKarp {
private Graph<Integer> graph;
/**
* @param graph: The Graph for which to solve the TSP
*
* The constructor initializes the Graph instance field,
* as well as sorts the Connections in each Edge for finding
* the initial Edge to earmark.
* */
public TSPHeldKarp(Graph<Integer> graph){
this.graph = graph;
for(int i = 0; i < graph.count(); i++)
graph.get(i).sortConnections();
}
/**
* @return Map<Edge<Integer>, List<Edge<Integer>>>: The adjacency list for the
* Travelling Salesman graph.
*
* The Held-Karp algorithm starts by finding an Edge such that the sum of
* the distances between it and its two lowest-weighted Edges are less than
* the sum of the distances between every other Edge and their two
* lowest-weighted Edges. After partitioning that, it uses Prim's algorithm
* to find the MST between those two Edges.
* */
public Map<Edge<Integer>, List<Edge<Integer>>> heldKarp(){
List<Connector<Integer>> connectors = graph.get(0).getConnections();
int minCost = connectors.get(0).getDistance() + connectors.get(1).getDistance();
int minIndex = 0;
for(int i = 1; i < graph.count(); i++){
connectors = graph.get(i).getConnections();
int distance = connectors.get(0).getDistance() + connectors.get(1).getDistance();
if(distance < minCost){
minCost = distance;
minIndex = i;
}
} //end for
Edge<Integer> edge = graph.get(minIndex);
List<Connector<Integer>> conns = edge.getConnections();
return prim(edge, conns.get(0), conns.get(1));
} //end heldKarp()
/**
* @param start: The Edge that was initially selected to be partitioned out.
* @param connOne: The first Connection to start
* @param connTwo: The second Connection to start
* @return Map<Edge<Integer>, List<Edge<Integer>>>: The adjacency lists for the TSP graph
*
* This method uses Prim's algorithm to find the Minimum Spanning Tree for the
* specified sub-graph, then joins the two un-connected Edges to complete the
* Hamiltonian circuit.
* */
private Map<Edge<Integer>, List<Edge<Integer>>> prim(Edge<Integer> start,
Connector<Integer> connOne, Connector<Integer> connTwo){
//the forrest is used to assure that the Tree property won't be violated
Map<Edge<Integer>, Graph<Integer>> forrest = new HashMap<Edge<Integer>, Graph<Integer>>();
//tracks the adjacencies for each Edge
Map<Edge<Integer>, List<Edge<Integer>>> adjacencies = new HashMap<Edge<Integer>, List<Edge<Integer>>>();
//used to prevent excessive iterations in determining the
//remaining two Edges that need to be connected.
//it is initially populated with all the Edges, which are then
//removed as they have a degree of two re-established in the adjacencies Map
Set<Edge<Integer>> remaining = new HashSet<Edge<Integer>>();
//foreach Edge
for(int i = 0; i < graph.count(); i++){
Edge<Integer> edge = graph.get(i);
//initialize its distance to an Infinity marker
//for the purpose of Prim's algorithm
edge.setDistance(Integer.MAX_VALUE);
remaining.add(edge);
Graph<Integer> temp = new Graph<Integer>();
temp.addEdge(edge);
adjacencies.put(edge, new ArrayList<Edge<Integer>>());
forrest.put(edge, temp);
}
//since the start Edge isn't being evaluated in the MST, it can be removed
//from the remaining Set. It also already has a degree of 2 in the TSP graph
remaining.remove(start);
Edge<Integer> one = connOne.getOne() == start ? connOne.getTwo() : connOne.getOne();
Edge<Integer> two = connTwo.getTwo() == start ? connTwo.getOne() : connTwo.getTwo();
one.setDistance(connOne.getDistance());
two.setDistance(connTwo.getDistance());
List<Edge<Integer>> list = adjacencies.get(start);
list.add(one);
list.add(two);
list = adjacencies.get(one);
list.add(start);
list = adjacencies.get(two);
list.add(start);
Graph<Integer> graph = forrest.get(start);
graph.addEdge(one);
graph.addEdge(two);
forrest.put(one, graph);
forrest.put(two, graph);
Comparator<Connector<Integer>> compare = new Comparator<Connector<Integer>>(){
public int compare(Connector<Integer> one, Connector<Integer> two){
return one.getDistance() - two.getDistance();
}
};
//in keeping with Prim's algorithm, a PriorityQueue will manage the Connections
//between Edges so the greedy choice can be selected
PriorityQueue<Connector<Integer>> connectors = new PriorityQueue<Connector<Integer>>(10, compare);
//since there are two child Nodes for start, both of their Connections
//will be added to the PriotiyQueue, save for any Connections to start
addConnections(one, start, connectors);
addConnections(two, start, connectors);
//as long as there are Connections to evaluate, do:
while(connectors.size() > 0){
Connector<Integer> temp = connectors.poll();
//if the Connection's Edges are already adjacent, move to the next one
if(adjacencies.get(temp.getOne()).contains(temp.getTwo())){
continue;
}
//if at least one of the Connection's Edges are already full (degree of two)
//then move to the next Connection
else if(adjacencies.get(temp.getOne()).size() >= 2 || adjacencies.get(temp.getTwo()).size() >= 2){
continue;
}
Graph<Integer> graphOne = forrest.get(temp.getOne());
//if the two Edges are already in the same Graph, move to the next
//Connection as joining the Edges would violate the Tree property,
//which is undesirable until after the completion of the Prim's algorithm
//portion
if(graphOne.contains(temp.getTwo())){
continue;
}
Edge<Integer> first = temp.getOne();
Edge<Integer> second = temp.getTwo();
addConnections(second, start, connectors);
boolean swapped = false;
//for the sake of not having a ton of if statements or ternary operators,
//first and second were swapped if first had a greater distance than second.
//usually, this will mean first is still marked as infinity, but second has
//been included in the MST-in-process already.
if(first.getDistance() > second.getDistance()){
Edge<Integer> edge = first;
first = second;
second = edge;
swapped = true;
}
//now re-connect these Edges, updating the total distance to an Edge
second.setDistance(first.getDistance() + temp.getDistance());
Graph<Integer> graphTwo = forrest.get((swapped) ? first:second);
for(int i = 0; i < graphTwo.count(); i++){
Edge<Integer> edge = graphTwo.get(i);
forrest.put(edge, graphOne);
graphOne.addEdge(edge);
}
list = adjacencies.get(first);
list.add(second);
if(list.size() >= 2)
remaining.remove(first);
list = adjacencies.get(second);
list.add(first);
if(list.size() >= 2)
remaining.remove(first);
}
//finally, join the remaining two unconnected Edges if they have a Connection
//between them. Note that if they aren't able to be connected, the adjacencies Map
//will reflect this, and it is the responsibility of the component invoking the
//heldKarp() method to valdiate this.
Edge<Integer> last = (Edge<Integer>)remaining.toArray()[0];
Iterator<Connector<Integer>> iterator = last.iterator();
while(iterator.hasNext()){
Connector<Integer> conn = iterator.next();
if(remaining.contains(conn.getOne()) && remaining.contains(conn.getTwo())){
adjacencies.get(conn.getOne()).add(conn.getTwo());
adjacencies.get(conn.getTwo()).add(conn.getOne());
}
}
return adjacencies;
}
/**
* @param current: The current Edge whose Connections need to be added to the PriorityQueue
* @param exclude: The Edge whose Connections to current should not be added to the PriorityQueue
* @param conns: The PriorityQueue of Connections
* */
private void addConnections(Edge<Integer> current, Edge<Integer> exclude, PriorityQueue<Connector<Integer>> conns){
for(Connector<Integer> c:current.getConnections()){
if(c.getOne() == exclude || c.getTwo() == exclude)
continue;
c.setDistance(c.getDistance() + current.getDistance());
conns.add(c);
}
}
public static void main(String[] args){
Graph<Integer> list = new Graph<Integer>();
Edge<Integer> i = new Edge<Integer>(1, 0);
Edge<Integer> j = new Edge<Integer>(2, 0);
Edge<Integer> k = new Edge<Integer>(3, 0);
Edge<Integer> l = new Edge<Integer>(4, 0);
Edge<Integer> m = new Edge<Integer>(5, 0);
Edge<Integer> n = new Edge<Integer>(6, 0);
list.addEdge(i);
list.addEdge(j);
list.addEdge(k);
list.addEdge(l);
list.addEdge(m);
list.addEdge(n);
i.connectTo(j, 7);
i.connectTo(k, 9);
i.connectTo(n, 14);
j.connectTo(k, 10);
j.connectTo(l, 15);
k.connectTo(n, 2);
k.connectTo(l, 11);
l.connectTo(m, 6);
n.connectTo(m, 9);
TSPHeldKarp test = new TSPHeldKarp(list);
Map<Edge<Integer>, List<Edge<Integer>>> graph = test.heldKarp();
for(Edge<Integer> edge:graph.keySet())
System.out.println(edge.getElem() + ": " + graph.get(edge));
}
}
MultiQuote
| 