Find all Hamiltonian cycles using Graphs.jl

Specific Domains Graphs
,
1

I’m wondering if there’s an existing implementation of an algorithm to find all Hamiltonian cycles within an unweighted, undirected graph. The graphs I’m interested in are small, on the order of 20 vertices. Basically I’m looking for something like the FindHamiltonianCycles function in Mathematica, but using the Graphs.jl data structures, so that I don’t have to roll my own heuristic implementation for my specific graphs of interest.

2

LongestPaths can find one Hamiltonian cycle but won’t help you getting all of them and is more interesting for graphs where full enumeration is out of the question.

If the total number of cycles of any length isn’t too large you can do

filter(cycle -> length(cycle) == nv(g), simplecycles(DiGraph(g)))

If the total number of cycles is prohibitive you can try something more fancy along the lines of

c = Channel{Vector{Int}}()
task = @async Graphs.itercycles(DiGraph(g), c)
while !istaskdone(task)
    cycle = take!(c)
    if length(cycle) == nv(g)
        println(cycle)
    end
    yield()
end
3

First, finding all Hamiltonian cycles in a graph is a NP-hard problem.
For the algorithm which find all Hamiltonian cycles, list all dfs trees and select all trees which is a path and the root and the end is connected in the graph, G.

4

My graphs are small enough that your one-liner works very well. Thanks!