# Find all Hamiltonian cycles using Graphs.jl

**URL:** <https://discourse.julialang.org/t/find-all-hamiltonian-cycles-using-graphs-jl/71304>\
**Category:** Graphs\
**Tags:** question, graphs\
**Created:** [November 11, 2021, 3:31am UTC](https://discourse.julialang.org/t/find-all-hamiltonian-cycles-using-graphs-jl/71304 "2021-11-11T03:31:44Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![mdtisdall](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mdtisdall/32/27418_2.png) [@mdtisdall](https://discourse.julialang.org/u/mdtisdall)\
**Post date:** [November 11, 2021, 3:31am UTC](https://discourse.julialang.org/t/find-all-hamiltonian-cycles-using-graphs-jl/71304/1 "2021-11-11T03:31:44Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![GunnarFarneback](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gunnarfarneback/32/1827_2.png) [@GunnarFarneback](https://discourse.julialang.org/u/GunnarFarneback)\
**Post date:** [November 11, 2021, 8:33am UTC](https://discourse.julialang.org/t/find-all-hamiltonian-cycles-using-graphs-jl/71304/2 "2021-11-11T08:33:17Z")

</div>

[LongestPaths](https://github.com/GunnarFarneback/LongestPaths.jl) 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

```julia
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

```julia
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

```

---

<div class="post-metadata">

**Author:** ![LDA111222](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lda111222/32/28360_2.png) [@LDA111222](https://discourse.julialang.org/u/LDA111222)\
**Post date:** [November 11, 2021, 9:12am UTC](https://discourse.julialang.org/t/find-all-hamiltonian-cycles-using-graphs-jl/71304/3 "2021-11-11T09:12:20Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![mdtisdall](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mdtisdall/32/27418_2.png) [@mdtisdall](https://discourse.julialang.org/u/mdtisdall)\
**Post date:** [November 11, 2021, 3:42pm UTC](https://discourse.julialang.org/t/find-all-hamiltonian-cycles-using-graphs-jl/71304/4 "2021-11-11T15:42:20Z")

</div>

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