Hamiltonian path using iGraph

Question

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.

Answer 1

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"]

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"]

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.

Answer 2

I am looked on the Szabolcs' answer and try to find hamiltonian path as a subgraph isomorphism problem:

library(igraph)

n = 8
m <- t(matrix(c(
0,0,0,0,0,0,0,8,
3,0,0,0,0,0,0,0,
5,0,0,5,1,0,0,0,
0,0,6,0,0,7,1,0,
0,6,2,0,0,0,0,0,
0,0,0,0,0,0,0,0,
7,4,0,0,8,0,0,3,
0,3,0,0,0,9,0,0),ncol=n))

g1 <- graph_from_adjacency_matrix(m, weighted=TRUE, mode="directed")
V(g1)$name <-  letters[1:n]
pattern <- make_lattice(length = n, dim = 1)

In my example, a number paths were found, I took the first:

path <- unlist(subgraph_isomorphisms(pattern, as.undirected(g1, mode = "each"), method = "vf2")[1])
path
#a b e c d f h g 
#1 2 5 3 4 6 8 7