3

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?

Improve this question
4
  • You might want to take a look here. Commented Dec 26, 2017 at 19:00
  • Can you add a small example input for the function that demonstrates the problem? Commented Dec 26, 2017 at 19:00
  • @bgse: Do you mean that the mutable default path argument is the catch? I removed it and nothing seems to change. Commented Dec 26, 2017 at 19:35
  • @mkrieger1: 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 a NoneType object, 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. Commented Dec 26, 2017 at 19:39

2 Answers 2

Reset to default
5

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

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.
@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.
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.
How do we fix the mutable default argument problem?
5

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
Improve this answer

1 Comment

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.