Combinatorica Example

Different Hamiltonian Cycles of the F60 Cubic Symmetric Graph

Based on code submitted by Ed Pegg

Initialize

First, we need to load the appropriate packages.

<< DiscreteMath`Combinatorica`

<< Parallel`Parallel`

For this particular problem, we want to use all of the available kernels.  The following code allows us to launch m kernels on n machines.  For the case presented here, we use 2 kernels on each of 8 machines.

\(multipleLaunchSlave[machToUse_, 
        slavPerKernel_] := \(Do[
node = 
              StringJoin["xserve", \ 
                ToString[
                  nodenum]]; 
Do[
LaunchSlave[
                node, \ "/usr/bin/rsh `1` /usr/local/bin/math -mathlink"], 
{#2}
], 
{nodenum, \ 1, \ #1}
] &\)[machToUse, 
        slavPerKernel]\)

multipleLaunchSlave[8, 2]

\(TableForm[
      RemoteEvaluate[{$ProcessorID, $MachineName, $SystemID, $ProcessID, $Version}], 
      TableHeadings -> {None, {"ID", "host", "OS", "process", "Mathematica Version"}}]\)

Definitions

Certain graphs have the property that any edge can be mapped to any other edge and any vertex can be mapped to any other vertex.  Pictures of the first 60 are available.  F60 is a particularly difficult case and no good embeddings were found in the literature.

F60  = 
        Table[Graph[
            Join[Drop[
                Map[{#} &, 
                  Partition[Range[60], 2, 1]], {n}], {{{5, 13}}, {{48, 
                    56}}, {{14, 23}}, {{38, 47}}, {{21, 31}}, {{30, 
                    40}}, {{25, 36}}, {{16, 28}}, {{33, 45}}, {{7, 
                    20}}, {{41, 54}}, {{9, 27}}, {{19, 37}}, {{24, 
                    42}}, {{34, 52}}, {{3, 29}}, {{32, 58}}, {{11, 
                    39}}, {{22, 50}}, {{4, 35}}, {{15, 46}}, {{26, 57}}, {{8, 
                    44}}, {{17, 53}}, {{10, 51}}, {{1, 43}}, {{18, 60}}, {{2, 
                    49}}, {{12, 59}}, {{6, 55}}, {{1, 60}}}], 
            Table[N[{{Sin[x], Cos[x]}}], {x, 0, 119  Pi/60, Pi/30}]], {n, 1, 
            59}];

We need to make sure that F60 is defined on all of the slave nodes.

ExportEnvironment[F60];

Here is one representation of the F60 graph, with a Hamiltonian cycle around the edge.

ShowGraph[F60[[7]]];

Calculations

We need to make sure that the Combinatorica package is loaded on all of the slave nodes.

RemoteEvaluate[
        Needs["DiscreteMath`Combinatorica`"]];

We use ParallelTable to calculate the Hamiltonian Cycle for the first 59 parts of F60, by removing each possible edge of the original Hamiltonian cycle.  Since the graph is symmetric, any edge can be deleted and a Hamiltonian cycle can still be found.

results = 
        ParallelTable[{$MachineName, 
            Timing[HamiltonianCycle[F60[[i]]]]}, {i, 1, 
            59}];

The maximum amount of time required per kernel was a little more than 164 seconds.

Max[Transpose[Transpose[results][[2]]][[1]]/
          Second] Second

The complete set of results can be seen below.

results

We can see the time spent on each node using the following code.

nodetimes = 
      Table[{"xserve" <> ToString[n], 
          Apply[Plus, 
              Map[First, 
                Map[First, 
                  Map[Last, Split[
                        Sort[results], (First[#1] == 
                              First[#2]) &][[n]]]]]] Second}, {n, 1, 
          8}]

The maximum amount of time spent by any one of the nodes can be found as follows.

Max[Transpose[nodetimes][[2]]/Second] Second

If this had been evaluated on a single kernel, the time required for evaluation would have been much longer

singleTime = 
        RemoteEvaluate[
          Timing[Table[{$MachineName, HamiltonianCycle[F60[[i]]]}, {i, 1, 
                59}]], First@$Slaves];

singleTime[[1]]

The speed-up seen here more than 5 times.

3007.36/571.24

Finally, we can display the results graphically.

Table[
        Graph[Join[
                Map[{#} &, 
                  Partition[Range[60], 2, 
                    1]], {{{5, 13}}, {{48, 56}}, {{14, 23}}, {{38, 
                      47}}, {{21, 31}}, {{30, 40}}, {{25, 36}}, {{16, 
                      28}}, {{33, 45}}, {{7, 20}}, {{41, 54}}, {{9, 
                      27}}, {{19, 37}}, {{24, 42}}, {{34, 52}}, {{3, 
                      29}}, {{32, 58}}, {{11, 39}}, {{22, 50}}, {{4, 
                      35}}, {{15, 46}}, {{26, 57}}, {{8, 44}}, {{17, 
                      53}}, {{10, 51}}, {{1, 43}}, {{18, 60}}, {{2, 
                      49}}, {{12, 59}}, {{6, 55}}, {{1, 60}}}] /. 
              Map[#[[1]] ->  #[[2]] &, 
                Transpose[{Drop[results[[g, 2, 2]], -1], 
                    Range[60]}]], 
            Table[N[{{Sin[x], Cos[x]}}], {x, 0, 119  Pi/60, Pi/30}]] // 
          ShowGraph, {g, 1, 59}];

CloseSlaves[];