<html>
<head>
<style>
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
FONT-SIZE: 10pt;
FONT-FAMILY:Tahoma
}
</style>
</head>
<body class='hmmessage'>
<DIV id=inbdy><A name=msg_81347a9f584bf815></A><FONT class=fixed_width face="Courier, Monospaced">Hi, <BR>
At the url <A href="http://www.python.org/doc/essays/graphs.html" target=_blank rel=nofollow><U><FONT color=#800080>http://www.python.org/doc/essays/graphs.html</FONT></U></A> there is some <BR>code by Guido Van Rossum for computing paths through a graph - I have <BR>pasted it below for reference - <BR>
<P>Let's write a simple function to determine a path between two nodes. <BR>It takes a graph and the start and end nodes as arguments. It will <BR>return a list of nodes (including the start and end nodes) comprising <BR>the path. When no path can be found, it returns None. The same node <BR>will not occur more than once on the path returned (i.e. it won't <BR>contain cycles). The algorithm uses an important technique called <BR>backtracking: it tries each possibility in turn until it finds a <BR>solution. <BR>
<P> def find_path(graph, start, end, path=[]): <BR> path = path + [start] <BR> if start == end: <BR> return path <BR> if not graph.has_key(start): <BR> return None <BR> for node in graph[start]: <BR> if node not in path: <BR> newpath = find_path(graph, node, end, path) <BR> if newpath: return newpath <BR> return None <BR>
<P>*** He then says------------------------ <BR>
<P>It is simple to change this function to return a list of all paths <BR>(without cycles) instead of the first path it finds: <BR>
<P> def find_all_paths(graph, start, end, path=[]): <BR> path = path + [start] <BR> if start == end: <BR> return [path] <BR> if not graph.has_key(start): <BR> return [] <BR> paths = [] <BR> for node in graph[start]: <BR> if node not in path: <BR> newpaths = find_all_paths(graph, node, end, path) <BR> for newpath in newpaths: <BR> paths.append(newpath) <BR> return paths <BR>
<P>*** I couldn't understand how it was simple to change the function <BR>find paths to find all paths. How would you think about writing this <BR>second function recursively. Especially the part about if start==end: <BR>return [path]. I feel you would give square brackets around path here <BR>after first writing the inductive part ... for node in <BR>graph[start] .... <BR>and then by trial and error put square brackets around path in the <BR>Basis part. Can someone please explain how to write this code. Thanks! <BR></FONT><BR></DIV><br /><hr />Planning marriage in 2008!
Join Shaadi.com matrimony FREE! <a href='http://ss1.richmedia.in/recurl.asp?pid=429' target='_new'>Try it now!</a></body>
</html>