Hi,
At the url http://www.python.org/doc/essays/graphs.html there is some code by
Guido Van Rossum for computing paths through a graph - I have pasted it below
for reference -
Let's write a simple function to determine a path between two nodes. It takes a
graph and the start and end nodes as arguments. It will return a list of nodes
(including the start and end nodes) comprising the path. When no path can be
found, it returns None. The same node will not occur more than once on the path
returned (i.e. it won't contain cycles). The algorithm uses an important
technique called backtracking: it tries each possibility in turn until it finds
a solution.
def find_path(graph, start, end, path=[]): path = path + [start]
if start == end: return path if not
graph.has_key(start): return None for node in graph[start]:
if node not in path: newpath = find_path(graph,
node, end, path) if newpath: return newpath return None
*** He then says------------------------
It is simple to change this function to return a list of all paths (without
cycles) instead of the first path it finds:
def find_all_paths(graph, start, end, path=[]): path = path +
[start] if start == end: return [path] if not
graph.has_key(start): return [] paths = [] for node
in graph[start]: if node not in path: newpaths =
find_all_paths(graph, node, end, path) for newpath in newpaths:
paths.append(newpath) return paths
*** I couldn't understand how it was simple to change the function find paths
to find all paths. How would you think about writing this second function
recursively. Especially the part about if start==end: return [path]. I feel you
would give square brackets around path here after first writing the inductive
part ... for node in graph[start] .... and then by trial and error put square
brackets around path in the Basis part. Can someone please explain how to write
this code. Thanks!
_________________________________________________________________
Video: Get a glimpse of the latest in Cricket, Bollywood, News and Fashion.
Only on MSN videos.
http://video.msn.com/?mkt=en-in_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
