Are There Multiple Hamiltonian Paths on a Graph

algorithmsgraph

Can anyone suggest an algorithm for this problem.

Given an undirected unweighted cyclic graph, and a given start and end node in that graph, I'd like to determine if there is exactly one valid path from start to end visiting all nodes (i.e. a Hamiltonian path, not a cycle).

It's NP-hard, but my N is relatively small (up to 30 nodes or so) and each node's connectivity is typically very small (no more than 4-5, often 2 or 3, typically local links [i.e. they correspond to locations in 2d connected to near neighbours]), so I'm confident it is feasible.

Published algorithms are typically for cycles, for finding a single solution, and for unknown start and end points. I'm curious if anyone can suggest something more fitting, or if you have any intuition on an approach.

Best Answer

If the problem is small enough, a totally naive approach works well. We want to generate all pinned hamiltonian paths connecting two nodes a and b in a given graph. For this, we just generate all valid paths originating from a and filter out those that are not hamiltonian or that do not end in b.

The following code snippet is an implementation of this idea in OCaml. On my machine it can find all pinned hamiltonian path in a complete graph of size 9 (there is (9-2)! = 5040 such paths, they are all the permutations of 7 non-pinned nodes), but the program cannot handle the case of size 10. This should give you an idea of the complexity of the operation, but as you see, I could not be less naive when implementing this.

module Graph =
struct
  type t = {
    node: int list;
    edge: (int * int list) list;
  }

  let nodes graph =
    List.sort_uniq Pervasives.compare graph.node

  let neighbours graph n =
    try List.assoc n graph.edge
    with Not_found -> []

  let pointed_hamiltonian_paths graph a =
    let is_visiting_all_nodes path =
      let sort = List.sort Pervasives.compare in
      sort path = sort graph.node
    in
    let hamiltonian_extensions path =
      match path with
      | [] -> []
      | node :: _ ->
          match List.filter
                  (fun x -> not(List.mem x path))
                  (neighbours graph node)
          with
          | [] -> [ path ]
          | newnodes -> List.map (fun x -> x :: path) newnodes
    in
    let rec loop paths =
      match List.concat (List.map hamiltonian_extensions paths) with
      | [] -> []
      | newpaths ->
          if newpaths = paths then paths else loop newpaths
    in
    List.filter is_visiting_all_nodes (loop [[a]])

  let pinned_hamiltonian_paths graph a b =
    List.filter (fun path -> (match path with hd ::_ -> hd = b | [] -> false))
      (pointed_hamiltonian_paths graph a)

  let example_1 = {
    node = [1; 2; 3; 4; 5];
    edge = [
      1, [ 4 ];
      2, [ 4; 5];
      3, [ 5 ];
      4, [ 1; 2; 5 ];
      5, [ 2; 3; 4 ];
    ];
  }

  let example_2 = {
    node = [ 6; 7; 8 ];
    edge = [
      6, [ 7; 8];
      7, [ 6; 8];
      8, [ 6; 7];
    ];
  }

  let example_3 = {
    node = example_1.node @ example_2.node;
    edge = example_1.edge @ example_2.edge;
  }

  let complete n =
    let rec loop ax i =
      if i < 1 then ax else loop (i :: ax) (pred i)
    in
    let seq = loop [] n in {
      node = seq;
      edge = List.map (fun x -> x, seq) seq;
    }
end

There are three examples of graphs defined, the first one is:

A simple graph with 5 nodes

the second one is a complete graph without loops (edges having the same start and end points) and the third one is the disjoint union of the two. With these definitions we can experiment a bit in the toplevel:

# Graph.pinned_hamiltonian_paths Graph.example_1 1 3;;
- : int list list = [[3; 5; 2; 4; 1]]

# Graph.pinned_hamiltonian_paths Graph.example_2 6 8;;
- : int list list = [[8; 7; 6]]

# Graph.pinned_hamiltonian_paths Graph.example_3 1 3;;
- : int list list = [] (* The graph is not connected! :) *)

# Graph.pinned_hamiltonian_paths (Graph.complete 4) 1 4;;
- : int list list = [[4; 3; 2; 1]; [4; 2; 3; 1]]
Related Topic