Find all Hamiltonian cycles using Graphs.jl

Specific Domains Graphs
,
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
1 Like