Page 1 of 1

Data Structures- A Look At Hamiltonian Circuits Rate Topic: -----

#1 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10647
  • View blog
  • Posts: 39,539
  • Joined: 27-December 08

Posted 21 May 2011 - 12:12 PM

The purpose of this tutorial is to introduce Hamiltonian circuits, as well as examine how to find them in both weighted and unweighted graphs.

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));
    }
}



Is This A Good Question/Topic? 4
  • +

Replies To: Data Structures- A Look At Hamiltonian Circuits

#2 v0rtex  Icon User is offline

  • Caffeine: db "Never Enough!"
  • member icon

Reputation: 223
  • View blog
  • Posts: 773
  • Joined: 02-June 10

Posted 21 May 2011 - 03:06 PM

Really nice tutorial macosxnerd101. Thanks!
Was This Post Helpful? 0
  • +
  • -

#3 smohd  Icon User is offline

  • Critical Section
  • member icon


Reputation: 1819
  • View blog
  • Posts: 4,627
  • Joined: 14-March 10

Posted 21 May 2011 - 03:20 PM

Nice tutorial man! I studied the circuit last semester in Discrete Mathematics. Nice to know how to code it! :)
Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10647
  • View blog
  • Posts: 39,539
  • Joined: 27-December 08

Posted 21 May 2011 - 08:29 PM

I'm glad everyone has enjoyed my tutorial! :)
Was This Post Helpful? 0
  • +
  • -

#5 woodenstick  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 08-July 12

Posted 08 July 2012 - 11:18 PM

Hello macosxnerd101,

Firstly, thanks for your helpful Graph Theory tutorials; they're really informative and easy to understand. However, I'm having a small problem here - I wanted to try out your code for the Held-Karp algorithm, using your Graph implementation that you linked to here. However it seems the TSPHeldKarp class uses methods of the Edge class, such as sortConnections() and iterator() that haven't actually been implemented in the code for that class. Am I missing something?

Thanks very much in advance!
Woodenstick
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10647
  • View blog
  • Posts: 39,539
  • Joined: 27-December 08

Posted 10 July 2012 - 08:57 AM

I've modified my graph implementation a couple times, and forgot to update sometimes. I've updated it to implement those methods. Connector is also Comparable, now. Sorry for the confusion!
Was This Post Helpful? 1
  • +
  • -

#7 woodenstick  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 08-July 12

Posted 10 July 2012 - 07:19 PM

View Postmacosxnerd101, on 10 July 2012 - 08:57 AM, said:

I've modified my graph implementation a couple times, and forgot to update sometimes. I've updated it to implement those methods. Connector is also Comparable, now. Sorry for the confusion!


Hey, thanks! However I think there's a slight problem. When I put all the code from your Graph implementation and from your Held-Karp algorithm into my IDE and ran it, I got an IndexOutOfBoundsException. I think I know why this happened:

Here's part of your original code from the Edge class:

    
    //add a connection not taking distances into account
    public void connectTo(Edge<E> other){
        Connector<E> c = new Connector<E>(this, other);

        //prevents adding duplicate connectors
        if(!pointers.contains(c)) pointers.add(c);

        //reference Connector in other Edge as well
        LinkedList<Connector<E>> conn = other.getConnections();
        if(!conn.contains(c)) conn.add(c);
    }

    public void connectTo(Edge<E> other, int distance){
        Connector<E> c = new Connector<E>(this, other, distance);
        if(!pointers.contains(c)) pointers.add(c);
    }



However, in the second connectTo() method (the one including the distance), shouldn't it reference the Connector in the other Edge as well? i.e., I think it should be like this:


    public void connectTo(Edge<E> other, int distance){
        Connector<E> c = new Connector<E>(this, other, distance);
        if(!pointers.contains(c)) pointers.add(c);

        //reference Connector in other Edge as well
        LinkedList<Connector<E>> conn = other.getConnections();
        if(!conn.contains(c)) conn.add(c);
    }




Is this correct? I've tried it and it looks like it's working.

Once again, thanks for all your help!

Woodenstick
Was This Post Helpful? 0
  • +
  • -

#8 woodenstick  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 08-July 12

Posted 24 July 2012 - 02:59 AM

View Postwoodenstick, on 10 July 2012 - 07:19 PM, said:

View Postmacosxnerd101, on 10 July 2012 - 08:57 AM, said:

I've modified my graph implementation a couple times, and forgot to update sometimes. I've updated it to implement those methods. Connector is also Comparable, now. Sorry for the confusion!


Hey, thanks! However I think there's a slight problem. When I put all the code from your Graph implementation and from your Held-Karp algorithm into my IDE and ran it, I got an IndexOutOfBoundsException. I think I know why this happened:

Here's part of your original code from the Edge class:

    
    //add a connection not taking distances into account
    public void connectTo(Edge<E> other){
        Connector<E> c = new Connector<E>(this, other);

        //prevents adding duplicate connectors
        if(!pointers.contains(c)) pointers.add(c);

        //reference Connector in other Edge as well
        LinkedList<Connector<E>> conn = other.getConnections();
        if(!conn.contains(c)) conn.add(c);
    }

    public void connectTo(Edge<E> other, int distance){
        Connector<E> c = new Connector<E>(this, other, distance);
        if(!pointers.contains(c)) pointers.add(c);
    }



However, in the second connectTo() method (the one including the distance), shouldn't it reference the Connector in the other Edge as well? i.e., I think it should be like this:


    public void connectTo(Edge<E> other, int distance){
        Connector<E> c = new Connector<E>(this, other, distance);
        if(!pointers.contains(c)) pointers.add(c);

        //reference Connector in other Edge as well
        LinkedList<Connector<E>> conn = other.getConnections();
        if(!conn.contains(c)) conn.add(c);
    }




Is this correct? I've tried it and it looks like it's working.

Once again, thanks for all your help!

Woodenstick


So is this correct?
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10647
  • View blog
  • Posts: 39,539
  • Joined: 27-December 08

Posted 25 July 2012 - 06:47 PM

If it works, it's probably correct. I've made some changes to my Graph class along the way, and I'm not always good about updating the changes. I have my full Hamiltonian Circuit source code somewhere, but I'd have to dig it out.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1