// find all Hamilton paths in an undirected graph starting at vertex x // compiled with gcc 3.2 under DOS: gcc hampath.c -O2 -o hampath.exe // report problems with other compilers or comments to sterten@aol.com #define nmax 1000 // can be extended for big graphs #include FILE *file; int U[nmax],endvertex[nmax],n,i,y,j,v,w,x; int I[nmax],V[nmax],D[nmax],A[nmax][nmax],E[nmax][nmax],C[nmax],Nodes[nmax]; void hampath(); void hampath2(); int main(int argc,char* argv[]){ if(argc<3){printf("usage: hampath file x\n\n"); printf("reads a graph from file and counts all Hamilton paths starting at vertex x\n"); exit(1);} //now read the graph: if((file=fopen(argv[1],"rb"))==NULL){printf("file-error");exit(1);} n=0;fm1:x=fgetc(file);if(x==48 || x==49)n++;if(feof(file)==0)goto fm1; fclose(file); i=n;n=0;fm2:if(n>nmax*nmax){printf("graph not correct\n");exit(1);} n++;if(n*n!=i)goto fm2; file=fopen(argv[1],"rb"); for(i=1;i<=n;i++)for(j=1;j<=n;j++){ fm3:x=fgetc(file);if(x!=48 && x!=49)goto fm3;A[i][j]=x-48;}fclose(file); for(i=1;i<=n;i++){D[i]=0;for(j=1;j<=n;j++){if(A[i][j]){D[i]++;E[i][D[i]]=j;}}} sscanf(argv[2],"%i",&x); //graph read. Now find all Hamilton paths: //hampath();// simple but slow hampath2();// fast, but not yet optimized //and now print the nodes of the searchtree: for(i=0;i<=n;i++)printf("%i ",Nodes[i]);printf("\n"); } // end of main() void hampath(){ // this is the simple method without checking the free neighbors constraint // it took about 29min for the graph below with x=5 // for details see hampath2() for(i=1;i<=n;i++){Nodes[i]=0;U[i]=0;}i=0;V[i]=x;v=x;U[x]=1; m1:i++;I[i]=0;if(i>=n)goto m3; m2:I[i]++;if(I[i]>D[v])goto m4; w=E[v][I[i]]; if(U[w])goto m2; Nodes[i]++;U[w]=1;V[i]=w;v=w;goto m1; m3://for(j=0;j<=i;j++)printf("%i ",V[j]);printf("\n"); // print solution m4:i--;if(i>0){U[v]=0;v=V[i-1];goto m2;} } // end of hampath() void hampath2(){ // much faster than hampath() // given an undirected graph G with vertices {1,..,n} and edges // E[v][1..D[v]] for vertex v, D[v] is the number of neighbors of v. // Counts all Hamilton paths starting at vertex x. // For undirected graphs some small changes are necessary. // This is not yet optimized, only to make the algorithm clear. // // i:move number (starts at 0, ends at n-1) , or level // endvertex[i] : endvertex fixed at move i ? // V[i] : vertex visited at move i // U[v] : vertex v already visited ? // C[v] : number of unvisited neighbors of vertex v // Nodes[i] : nodes in the search tree // Nodes[n-1] : solutions // I[i] : enumerates neighbors of V[i-1] , runs from 1 to D[V[i-1]] // w,y : neighbors of v for(i=0;i<=n;i++)Nodes[i]=0;endvertex[0]=0; for(i=1;i<=n;i++){U[i]=0;C[i]=D[i];}i=0;V[i]=x;v=x;U[x]=1; m1:i++;I[i]=0;if(i>=n)goto m4; // here we might include a pre-test for the number of neighbors y // with C[y]>2, so we needn't do the test below for each w. // I tried the lines below, but this gave no significant speed increase // for the sample graph. However for larger graphs it might help. // if(endvertex[i-1]==0)goto m2; // D2[v]=D[v];u=0;c=0; // for(j=1;j<=D[v];j++){y=E[v][j];if(U[y]==0 && C[y]==2){u=j;c=c+3-C[y];}} // if(c>1)goto m4; // if(c==1){I[i]=u-1;D2[v]=u;C2[i]=c;} // and replacing D[v] with D2[v] in line m2:... m2:I[i]++;if(I[i]>D[v])goto m5; w=E[v][I[i]];if(U[w])goto m2; // if w was already visited then next neighbor // now test whether a forbidden vertex with less than 2 neighbors // is left and endvertex is fixed. // Also test whether no two forbidden vertices with less than 2 neighbors // are left and endvertex is nonfixed. // Also update endvertex and free neighbors. // endvertex[i]=endvertex[i-1];j=1; m3:y=E[v][j];if(U[y]==0){ if(C[y]<2)goto m2; if(C[y]==2 && y!=w && endvertex[i]>0)goto m2; if(C[y]==2 && y!=w)endvertex[i]++;} // for bipartite graphs like knight's graphs we would only allow // endvertices with the correct parity here j++;if(j<=D[v])goto m3; for(j=1;j<=D[v];j++)C[E[v][j]]--; // test and updates done. // // Here is the place to include some other // tests, if we only want specific Hamilton paths. // For magic knight's tours we would test here if the partial sums // in the row or column exceed the bounds for allowed values Nodes[i]++;U[w]=1;V[i]=w;v=w;goto m1; // next move m4://for(j=0;j<=i;j++)printf("%i ",V[j]);printf("\n"); // print solution m5:i--;if(i>0){U[v]=0;v=V[i-1];for(j=1;j<=D[v];j++)C[E[v][j]]++;goto m2;} // take back the last move and try the next neighbor at previous level } //end of hampath2() // I used the graph below for testing. It's the 6*6 knight's graph. // It took 1.7s with 2500MHz to find the 289050 Hamilton paths // starting at vertex x=5. /* 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 */