"Hamiltonian" path using Python

Question

I am trying to implement a recursive search for an arbitrary path (not necessarily a cycle) traversing all graph vertices using Python. Here's my code:

def hamilton(G, size, pt, path=[]):
    if pt not in set(path):
        path.append(pt)
        if len(path)==size:
            return path
        for pt_next in G[pt]:
            res_path = [i for i in path]
            hamilton (G, size, pt_next, res_path)

Here, pt is the starting point and path is the list of all previously traversed vertices not including pt, empty by default. The problem is, whenever such a path is found, the return statement refers to some inner call of the procedure and therefore the program does not terminate or return the path.

For example, take G = {1:[2,3,4], 2:[1,3,4], 3:[1,2,4], 4:[1,2,3]} (i.e. the complete 4-graph) and run hamilton(G,4,1,[]). It returns None, but if you print the path instead of returning it as a value, you'll see that it actually finds all six paths starting at 1.

If I tell the program to print the path together with the return statement, it eventually prints all such paths and hence runs much longer than needed.

How can I fix the code so that it would terminate the execution after the first suitable path is found?

Solution 1

The basic mistake is that the result of the recursive call needs to be returned, if it didn't lead to a dead end.

In addition, G[pt] will raise an IndexError if the point pt has no neighbors. This can easily be fixed by using dict.get.

def hamilton(G, size, pt, path=[]):
    print('hamilton called with pt={}, path={}'.format(pt, path))
    if pt not in set(path):
        path.append(pt)
        if len(path)==size:
            return path
        for pt_next in G.get(pt, []):
            res_path = [i for i in path]
            candidate = hamilton(G, size, pt_next, res_path)
            if candidate is not None:  # skip loop or dead end
                return candidate
        print('path {} is a dead end'.format(path))
    else:
        print('pt {} already in path {}'.format(pt, path))
    # loop or dead end, None is implicitly returned

Examples

>>> G = {1:[2,3,4], 2:[1,3,4], 3:[1,2,4], 4:[1,2,3]}
>>> hamilton(G, 4, 1)
hamilton called with pt=1, path=[]
hamilton called with pt=2, path=[1]
hamilton called with pt=1, path=[1, 2]
pt 1 already in path [1, 2]
hamilton called with pt=3, path=[1, 2]
hamilton called with pt=1, path=[1, 2, 3]
pt 1 already in path [1, 2, 3]
hamilton called with pt=2, path=[1, 2, 3]
pt 2 already in path [1, 2, 3]
hamilton called with pt=4, path=[1, 2, 3]
[1, 2, 3, 4]

>>> G = {1:[2], 2:[3,4], 4:[3]}
>>> hamilton(G, 4, 1)
hamilton called with pt=1, path=[]
hamilton called with pt=2, path=[1]
hamilton called with pt=3, path=[1, 2]
path [1, 2, 3] is a dead end
hamilton called with pt=4, path=[1, 2]
hamilton called with pt=3, path=[1, 2, 4]
[1, 2, 4, 3]

>>> G = {1:[2], 2:[3,4], 4:[3]}
>>> hamilton(G, 4, 2)
hamilton called with pt=2, path=[]
hamilton called with pt=3, path=[2]
path [2, 3] is a dead end
hamilton called with pt=4, path=[2]
hamilton called with pt=3, path=[2, 4]
path [2, 4, 3] is a dead end
path [2, 4] is a dead end
path [2] is a dead end
None

Note that using the function more than once can lead to wrong results because of the "mutable default argument" problem. But that's not the scope of this answer.

Solution 2

Here is a solution with no recursion DFS to search for a hamilton path from a specific vertex start_v.

it is made for the graph representation hashmap of arrays:

G = {0:[1], 1:[0, 2], 2:[1, 3], 3:[2, 4, 5], 4:[3, 6], 5:[3], 6:[4]}

def hamilton(graph, start_v):
  size = len(graph)
  # if None we are -unvisiting- comming back and pop v
  to_visit = [None, start_v]
  path = []
  while(to_visit):
    v = to_visit.pop()
    if v : 
      path.append(v)
      if len(path) == size:
        break
      for x in set(graph[v])-set(path):
        to_visit.append(None) # out
        to_visit.append(x) # in
    else: # if None we are comming back and pop v
      path.pop()
  return path

you can speed up if represent the graph by hashmap of sets:

G = {0:{1}, 1:{0, 2}, 2:{1, 3}, 3:{2, 4, 5}, 4:{3, 6}, 5:{3}, 6:{4}}

and also maintain a visited set and for not use set(path)

Then the solution will be slightly faster:

def hamilton(graph, start_v):
  size = len(graph)
  # if None we are -unvisiting- comming back and pop v
  to_visit = [None, start_v]
  path = []
  visited = set([])
  while(to_visit):
    v = to_visit.pop()
    if v : 
      path.append(v)
      if len(path) == size:
        break
      visited.add(v)
      for x in graph[v]-visited:
        to_visit.append(None) # out
        to_visit.append(x) # in
    else: # if None we are comming back and pop v
      visited.remove(path.pop())
  return path

Comments

[Max]

Thanks for the detailed response! I'll check the other approaches, but it seems that your modification for generating one path does not always work: say, for G={1:[2], 2:[3,4], 4:[3]} it gets stuck at 3 and raises an error.

[mkrieger1]

@Max Well spotted. There are actually two problems. The first one is trying to get the neighbors of a point that has no neighbors, which already exists in the original code. The second one is a problem in the algorithm - it turns out that what I've written isn't true either and your original version can be fixed easily. I'll need to update the answer.

[Zeromika]

G = {0:[1], 1:[0, 2], 2:[1, 3], 3:[2, 4, 5], 4:[3, 6], 5:[3], 6:[4]} Trying with this seems to be producing wrong results, just a heads up. I know this is an old solution, but I would say maybe changing the function name from hamilton in this question makes sense as either OP doesn't require a fully correct solution in terms of the hamilton path.

[nosense]

How do we fix the mutable default argument problem?

[Prune]

This fails on the first iteration, trying to pop from an empty list.