2
$\begingroup$

How to randomize given path found by FindHamiltonianPath?

FindHamiltonianPath outputs just one of possible Hamiltonian paths.

You can merely specify starting and end points but still only one path for each pair of points is given.

Is there any function that takes the output of FindHamiltonianPath and transforms it randomly but preserving it being Hamiltonian?

HighlightGraph[#, 
   PathGraph[FindHamiltonianPath[#]]] & /@ {PolyhedronData[
   "Dodecahedron", "Skeleton"], 
  PolyhedronData[PolyhedronData["Chiral"][[1]], "Skeleton"], 
  PolyhedronData[PolyhedronData["Chiral"][[8]], "Skeleton"]}

enter image description here

Update:

For example, for the above "Dodecahedron" we have these Hamiltonian paths (all start at vertex 13 and end at vertex 17):

enter image description here

$\endgroup$
2
  • $\begingroup$ What do you need this for? It's easy to find several Hamiltonian paths. Sampling all Hamiltonian paths uniformly is an entirely different matter. $\endgroup$
    – Szabolcs
    Nov 2 '20 at 20:01
  • $\begingroup$ I do not need any particular probability distribution. Just to randomly modify the path given by FindHamiltonianPath preserving it being Hamiltonian. "randomly" in the broad sense - it does not have to be uniform distribution. $\endgroup$ Nov 2 '20 at 20:06
4
$\begingroup$

You can find all the Hamiltonian cycles of a graph, which include all Hamiltonian paths, and select one of the paths at random.

g = PolyhedronData["Dodecahedron", "Skeleton"];
hc = FindHamiltonianCycle[g, All];
HighlightGraph[g, RandomChoice[hc]](*draw a random Hamiltonian path*)

For a graph with starting and ending vertices, we must remove the paths that don't include the two vertices as end points of an edge, and then remove the edge. We can draw the 20 graphs starting at vertex 13 and ending at vertex 17 by:

{s, t} = {13, 17};
hps2t = Select[hc, MemberQ[(s | t) \[UndirectedEdge] (s | t)]];
GraphicsGrid[
 Partition[
  Table[HighlightGraph[g, 
    DeleteCases[p, (s | t) \[UndirectedEdge] (s | t)], 
    GraphHighlightStyle -> "Thick"], {p, hps2t}], 5]]

graphs

$\endgroup$
5
  • $\begingroup$ That was not my question. You have just replicated what I did in my update of OP. My question was how to randomize path given by FindHamiltonianPath. There can be, say, 10^12 possible paths so you can not produce them all and select one randomly. $\endgroup$ Nov 2 '20 at 19:57
  • $\begingroup$ There are not 10^12 Hamiltonian paths, but it would seem there are Length[FindHamiltonianCycle[g, All]] such paths, right? So doesn't choosing one the paths from the Hamiltonian cycle give one of the possible results of FindHamiltonianPath? $\endgroup$
    – creidhne
    Nov 2 '20 at 20:14
  • $\begingroup$ We are not talking about one particular example of graph. Take for example g=GridGraph[{1000, 1000}] and try to do the same as with "Dodecahedron" graph. $\endgroup$ Nov 2 '20 at 20:19
  • $\begingroup$ @azerbajdzan Well, you could enumerate some cycles, not all of them. You said you don't need a specific distribution. I thought randomizing the graph structure would be useful in getting paths which are a bit more different from each other than what you'd get if you enumerate only a few cycles and work with those, but see the performance problems I ran into. $\endgroup$
    – Szabolcs
    Nov 2 '20 at 20:20
  • $\begingroup$ @azerbajdzan Of course, if your graphs don't have a regular representation (as the result returned by GridGraph), then you likely wouldn't lose any performance with the randomization method. $\endgroup$
    – Szabolcs
    Nov 2 '20 at 20:21
3
$\begingroup$

Since you say that you don't need any particular distribution, you can try to use the trick of randomizing the graph representation.

Take

g2 = Graph[RandomSample@VertexList[g], RandomSample@EdgeList[g]]

and find paths or cycles in g2. The algorithm will return a different one simply because it is working with a different representation of the same graph.

In bigger graphs, there may be too many Hamiltonian cycles to allow brute-force enumeration, as in the other answer by @credihne. In these cases, the randomization trick may be useful to get a few more paths which don't significantly overlap with the original.

Beware though, that the particular representation of some of the built-in graphs may allow the Hamiltonian path finder to return a result very quickly. Once we randomize it, FindHamiltonianPath may become unusably slow. This is what seems to happen with this graph:

g = GraphData["GreatRhombicosidodecahedralLineGraph"]

Therefore, it may still be more practical to enumerate not all, but some cycles/paths and choose from them randomly.

$\endgroup$
3
  • $\begingroup$ That is a great trick! I am inclined to think that it cannot be too far from uniform distribution if RandomSample is working with uniform distribution. No? $\endgroup$ Nov 2 '20 at 20:32
  • $\begingroup$ @azerbajdzan That really depends on how the Hamiltonian cycle finder algorithm works. I would not assume anything about the distribution. $\endgroup$
    – Szabolcs
    Nov 2 '20 at 20:40
  • $\begingroup$ Drawback of your method is that FindHamiltonianPath may be too slow for some graphs - like for example FindHamiltonianPath[GridGraph[{9, 9}]]- it takes "ages" to get the output. $\endgroup$ Nov 2 '20 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.