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?
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
>>> 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.