446,190 Members | 765 Online Need help? Post your question and get tips & solutions from a community of 446,190 IT Pros & Developers. It's quick & easy.

# Cannot understand the detailedly the following code

 P: n/a 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! Apr 8 '08 #1
9 Replies

 P: n/a On 2008-04-08, re******@hotmail.com

 P: n/a En Tue, 08 Apr 2008 09:45:35 -0300, A.T.Hofkamp escribió: On 2008-04-08, re******@hotmail.com after first writing the inductive part ... for node ingraph[start] ....and then by trial and error put square brackets around path in theBasis part. Can someone please explain how to write this code. Thanks! The same as any other function. (the trick with recursive functions is not to think about recursion. Instead, pretend you are calling another function that happens to have the same name.) But our BDFL played some tricks to make both functions look more similar than they would instead. Take the "single path" variant: 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 Why are those "return None" there, if not to be replaced by "return []"? Nobody writes that final one at least. Anyway, using the current Python version, it's easier to mutate the above function into a generator of all posible solutions; I hope the OP finds the mutation easier to follow: def find_all_paths(graph, start, end, path=[]): path = path + [start] if start == end: yield path return if start not in graph: return for node in graph[start]: if node not in path: for newpath in find_all_paths(graph, node, end, path): yield newpath The last two lines might be replaced in Python 3 by: yield *find_all_paths if this patch is accepted: http://bugs.python.org/issue2292 -- Gabriel Genellina Apr 9 '08 #3

 P: n/a On Apr 8, 5:45*pm, "A.T.Hofkamp"

 P: n/a On Apr 8, 5:45*pm, "A.T.Hofkamp" First define the input and output parameters/values of the function. (ie what goes in, and what comes out) Now what will be the output parameters - there is a Return statement. Input parameters are graph, vertexes start, node, end and path. Also how would you write the terminating and reduction cases after this. Actually i'm not clear how to proceed writing this recursive function. Thanks! Apr 9 '08 #5

 P: n/a On 2008-04-09, re******@hotmail.com First define the input and output parameters/values of the function.(ie what goes in, and what comes out) Now what will be the output parameters - there is a Return statement. Input parameters are graph, vertexes start, node, end and path. Also how would you write the terminating and reduction cases after this. Actually i'm not clear how to proceed writing this recursive function. Thanks! Don't look at code, don't even think about it (it gives you too much confusing details). Instead, have a beer, sit down in a sunny spot, and do mothing for a while. Think about the function as a (black) box. You don't know what is in it (it is not important yet). That box is the function (many people prefer to draw a rectangular shape on a sheet of paper, and consider that to be the function). What data does the box need to do its work, and what does it produce after it has done its work? (suppose you are given the task of 'finding all paths'. What information do you need to acomplish this task, and what information do you write down as result?) A simple example of a multiplication task: One needs 2 numbers to do the task, and the result is another number. Note that at this stage, you don't worry about HOW you do the task, only WHAT GOES IN AND WHAT COMES OUT. (actually, HOW depends on INPUT. Multiplication of 2 and 5 can be done differently from multiplication of 23069876208526945906838863907890387038579036870387 9038285790 and 59380637860938956826829683907893808346873876897628 97. For this reason, deciding the strategy of solving the problem comes after establishing input and output). Sincerely, Albert PS email will give you shorter response times. Apr 9 '08 #6

 P: n/a On Apr 9, 8:12*pm, "A.T.Hofkamp"

 P: n/a En Thu, 10 Apr 2008 23:57:29 -0300,

 P: n/a On Apr 11, 10:27*am, "Gabriel Genellina" wrote: En Thu, 10 Apr 2008 23:57:29 -0300,

 P: n/a On Apr 11, 10:27*am, "Gabriel Genellina" wrote: > If you want to understand how recursion works, or how you can actually * construct a recursive function step by step, see this excellent post by * Neil Cerutti: http://groups.google.com/group/comp....0b10631fd47886 Hi, I did read the above post by Cerutti but I'm still having trouble writing this recursive function. I will be grateful if someone can kindly guide me. Regards, Anshu Jun 27 '08 #10

### This discussion thread is closed

Replies have been disabled for this discussion. 