Hamiltonian Cycles

Recently, Markiyan Hirnyk asked how to find all Hamiltonian cycles in a graph using Maple.

Here is a procedure using Ham Cycle unix tool (which is GPLed) in Windows.

First, one has to download it from the link above and put in his/her cygwin home directory, /cyg/home/Alec for me. Then start cygwin shell, extract the downloaded archive and cd to the extracted directory,

tar xvzf ham*
cd ham*

Then edit the Makefile changing -fast to -O3, for example, using nano,

nano Makefile

Then produce the executables,

make clean
make release

Now, in Maple, create the following procedure, with making appropriate changes in temp and ssystem call, using the correct paths on your system,

HamiltonianCycles:=proc(g)
    local m,n,temp,fd,i,s;
    n:=GraphTheory:-NumberOfVertices(g);
    temp:="/Users/Alec/AppData/Local/Temp/hctemp";
    fd:=open(temp,WRITE);
    fprintf(fd, cat("$\n&Graph\nG\n%d",
        "\n%{}d"$n-1,"  0\n"), n,  
        seq(<-i,op(select(`>`,op([4,3,i,2],g),i))>,
            i=1..n-1));
    close(fd);
    s:=ssystem(cat("/cyg/bin/bash --login -c ",  
        "'hamiltonianCycles/hc_list_cycles ",
        "/cygdrive/c", temp, "'"))[2][28..-2];
    m:=nops([StringTools:-SearchAll("<",s)]);
    sscanf(s,cat("%{",m,",",n,";d(<>)}dm"))[] 
end;

Now, Hamiltonian cycles can be produced as in the following example,

use GraphTheory in  
    g:=CartesianProduct(CycleGraph(3),PathGraph(2));
    DrawGraph(subsop(3 = [$1 .. NumberOfVertices(g)], g), 
        style = spring) 
end;

HamiltonianCycles(g);

                     [5    6    2    4    3    1]
                     [                          ]
                     [5    3    4    6    2    1]
                     [                          ]
                     [3    5    6    4    2    1]

The vertices can be identified using

Equate(op(3, g), [$1 .. 6]);

     ["1:1" = 1, "1:2" = 2, "2:1" = 3, "2:2" = 4, "3:1" = 5, "3:2" = 6]

The difference with Mathematica is that this procedure lists undirected Hamiltonian cycles, while Mathematica produces directed ones - in both possible directions, so Mathematica's output is twice longer,

Needs["Combinatorica`"];
g = GraphProduct[Cycle[3], Path[2]];
HamiltonianCycle[g, All]

    {{1, 2, 3, 6, 5, 4, 1}, {1, 2, 5, 4, 6, 3, 1}, 
     {1, 3, 2, 5, 6, 4, 1}, {1, 3, 6, 4, 5, 2, 1}, 
     {1, 4, 5, 6, 3, 2, 1}, {1, 4, 6, 5, 2, 3, 1}} 

GraphPlot[g, VertexLabeling -> True]

Alec Mihailovs