:

## 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);
"'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

﻿