Enumerate *all* hamiltonian paths

Question

I know this has been asked before, but I did not find its answer in any of the posts. Can someone please suggest me an algorithm which enumerates ALL Hamiltonian paths in a graph?

A little background: I am working on a problem in which I have to enumerate each Hamiltonian path, do some analysis, and return the result. For that, I need to be able to enumerate all the possible hamiltonian paths.

Thanks.

Cynth

DId you try plain searching? BFS/DFS? How big are your graphs? – Argal

Santiago, thanks for your reply. My graphs are small (6-7 nodes). I did think about BFS and DFS, but I assume that BFS/DFS are used for searching for a specific key rather than enumerating all possible paths. How do I make BFS/DFS generate all possible cycles.. – Cynth

Regular BFS/DFS is conditioned to stop after finding the first key that matches. You just have to change that, have it walk the whole graph (if possible) and note it as solution. – Argal

Answer 1

Use BFS/DFS as suggested but don't stop at the first solution. BFS/DFS primary use (in this case) will be to find all of the solution, you need to put a condition to it to stop at the first one.

Yarndyed

Thanks. Can you please elaborate what do you mean by a 'solution'. As far as I know, running a DFS on a graph will simply give a sequence of visited nodes (e.g. A->B->C->D for a graph with vertices A,B,C,D). But it would never 'explore' ALL possible paths. Can you please elaborate? – Cynth

Both DFS and BFS will give you ALL the possible paths beginning from a specific node. From these Hamilton path are those whose lengths are exactly the same as the graph's size and each node exists exactly once. So if you have a graph with 5 nodes and there's a path of p1->p2->p3->p4->p5 it's a Hamiltonian path. Also note that you will have to start the search from each and every node. – Potpourri

Thanks SinistraD, that's very helpful! – Cynth

Answer 2

My java code: (absolutely based on recursive method)

algorithm:

+Start at 1 point connect to another point it can see(to form a path).

+remove the path and recursively find new path at newest point until connect all points of graph.

+remove the path and backtrack to initial graph if cant form Hamilton path from newest point

public class HamiltonPath {
public static void main(String[] args){
    HamiltonPath obj = new HamiltonPath();

    int[][]x = {{0,1,0,1,0},  //Represent the graphs in the adjacent matrix forms
                {1,0,0,0,1},
                {0,0,0,1,0},
                {1,0,1,0,1},
                {0,1,0,1,0}};

    int[][]y = {{0,1,0,0,0,1},
                {1,0,1,0,0,1},
                {0,1,0,1,1,0},
                {0,0,1,0,0,0},
                {0,0,1,0,0,1},
                {1,1,0,0,1,0}};

    int[][]z = {{0,1,1,0,0,1},
                {1,0,1,0,0,0},
                {1,1,0,1,0,1},
                {0,0,1,0,1,0},
                {0,0,0,1,0,1},
                {1,0,1,0,1,0}};

    obj.allHamiltonPath(y);   //list all Hamiltonian paths of graph
    //obj.HamiltonPath(z,1);  //list all Hamiltonian paths start at point 1


}

static int len;
static int[]path;
static int count = 0;    

public void allHamiltonPath(int[][]x){  //List all possible Hamilton path in the graph
    len = x.length;
    path = new int[len];
    int i;
    for(i = 0;i<len;i++){ //Go through column(of matrix)
        path[0]=i+1;
        findHamiltonpath(x,0,i,0);
    }
}

public void HamiltonPath(int[][]x, int start){ //List all possible Hamilton path with fixed starting point
    len = x.length;
    path = new int[len];
    int i;
    for(i = start-1;i<start;i++){ //Go through row(with given column)
        path[0]=i+1;
        findHamiltonpath(x,0,i,0);
    }
}

private void findHamiltonpath(int[][]M,int x,int y,int l){

    int i;
        for(i=x;i<len;i++){         //Go through row

            if(M[i][y]!=0){      //2 point connect

                if(detect(path,i+1))// if detect a point that already in the path => duplicate 
                    continue;

                l++;            //Increase path length due to 1 new point is connected 
                path[l]=i+1;    //correspond to the array that start at 0, graph that start at point 1
                if(l==len-1){//Except initial point already count =>success connect all point
                    count++;   
                    if (count ==1)
                System.out.println("Hamilton path of graph: ");
                    display(path);
                    l--;
                    continue;
                }

                M[i][y]=M[y][i]=0;  //remove the path that has been get and
                findHamiltonpath(M,0,i,l); //recursively start to find new path at new end point
                l--;                // reduce path length due to the failure to find new path         
                M[i][y] = M[y][i]=1; //and tranform back to the inital form of adjacent matrix(graph)
            }
     }path[l+1]=0;    //disconnect two point correspond the failure to find the..   
}                     //possible hamilton path at new point(ignore newest point try another one)         

public void display(int[]x){

   System.out.print(count+" : ");
    for(int i:x){
        System.out.print(i+" ");
    }
        System.out.println();   
}

private boolean detect(int[]x,int target){ //Detect duplicate point in Halmilton path 
    boolean t=false;                        
    for(int i:x){
        if(i==target){
            t = true;
            break;
        }
    }
    return t;
}  

}

Iguanodon

Answer 3

Solution in Python3:

def hamiltonians(G, vis = []):
    if not vis:
        for n in G:
            for p in hamiltonians(G, [n]):
                yield p
    else:
        dests = set(G[vis[-1]]) - set(vis)
        if not dests and len(vis) == len(G):
            yield vis
        for n in dests:
            for p in hamiltonians(G, vis + [n]):
                yield p
G = {'a' : 'bc', 'b' : 'ad', 'c' : 'b', 'd' : 'ac'}
print(list(hamiltonians(G)))

Jambalaya

Thank you. It is really very smart code. I checked it in Python with your input data and also converted it in C#. I don't understand it completely. I tried to follow this code in debugging and I see that in cycle "for p in hamiltonians(G, vis + [n]):" several times the same p is returned but in the final output all paths are different. Can you please give some explanations? – Vinia

Answer 4

A depth-first exhaustive search gives you the answer. I just finished a write-up on a Java implementation for this problem (including the code):

http://puzzledraccoon.wordpress.com/2012/06/07/how-to-cool-a-data-center/

Cobble