Search code examples
igraph

Hamiltonian path using iGraph

I started evaluating igraph library and its functionality. I need to calculate hamiltonian path of a graph generated by igraph_de_bruijn() function. Is there any ready made function in igraph library for that? I don't want to implement it from scratch. An example in C would be perfect.

Solution

  • The Hamiltonian path problem can be cast as a subgraph isomorphism problem, for which igraph has several functions. Construct a 1D lattice graph (a "line") with the same number of vertices as your graph, then search for this pattern using subisomorphism functions.

    Here's an example using the Mathematica interface.

    hamiltonianPath[g_] := 
 Values@First@IGLADGetSubisomorphism[
    GridGraph[{VertexCount[g]}],  (* <- this is just a 1D lattice, like O-O-O-O *)
    g                             (* <- this is the graph we want to match *)
 ]

    Let's try a dodecahedral graph:

    g = PolyhedronData["Dodecahedron", "SkeletonGraph"]

    Mathematica graphics

    Here's the order the vertices need to be visited in:

    path = hamiltonianPath[g]

(* {1, 16, 7, 3, 14, 9, 17, 19, 5, 11, 12, 8, 4, 20, 6, 2, 13, 18, 10, 15} *)

    Let's visualize it:

    HighlightGraph[g, PathGraph[path], GraphHighlightStyle -> "Thick"]

    Mathematica graphics

    I use Mathematica only for illustration. The procedure is identical when using the C interface.

    When you do this from C, you can use igraph_subisomorphic_lad to find a single subisomorphism (see the map argument). Use igraph_ring to create the pattern (circular=false for Hamiltonian path, circular=true for Hamiltonian cycle). If you want the dodecahedron for a test case, you can get it with igraph_famous.