"hamiltonian" Path Using Python

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, pa

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 notin set(path):
        path.append(pt)
        iflen(path)==size:
            returnpathfor pt_next in G.get(pt, []):
            res_path = [i for i inpath]
            candidate = hamilton(G, size, pt_next, res_path)
            if candidate is not None:  # skip loop or dead endreturn 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]}

defhamilton(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)
      iflen(path) == size:
        breakfor x inset(graph[v])-set(path):
        to_visit.append(None) # out
        to_visit.append(x) # inelse: # 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:

defhamilton(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)
      iflen(path) == size:
        break
      visited.add(v)
      for x in graph[v]-visited:
        to_visit.append(None) # out
        to_visit.append(x) # inelse: # if None we are comming back and pop v
      visited.remove(path.pop())
  return path