[Tutor] Recursion doubt

[Anshu Raval]

Hi,
 
Thank you so much for your response. I followed the 2 reasonings you gave,
 
--
You can look at find_all as a master routine that keeps calling find_path until find_path gives up. If the search space has not been exhausted (here there are still other nodes connected to 'start') take a suitable candidate call find_path from there until no more paths from there can be found. Repeat until no more suitable candidates.
-----
(in this case find_path executes a depth-first search on the graph - represented as a dictionary & find_all combines the 2 searches, first the depth search & when it quits, the breadth search takes over.)
--------
 
But my question would again be how do you know to put square brackets around path in if start == end:             return [path] in find_all_paths. I am still puzzled by this.
 
Thanks & Regards,
Anshu


Date: Sun, 20 Apr 2008 03:21:03 +0200From: joskerc at gmail.comTo: reachmsn at hotmail.comSubject: Re: [Tutor] Recursion doubtCC: tutor at python.org
Hi,
 
you are tackling 3 "heavy" subjects in just 1 go!
 
graphs :a triving math society would approve your choice. But you might start with the *slightly* less difficult challenge: trees.
I do not know your math/programming background, so the following link can perhaps enlighten you: http://www.brpreiss.com/books/opus7/
 
Trees, graphs, queues and what more implemented in several languages. Python included.
Also, most CS starters have chapters devoted to (some of) them.
(E.g. http://www.greenteapress.com/thinkpython/)
 
Backtracking & recursion will surely be topics too.

Reading them will help getting a handle on it
 
The 3 chosen topics are advanced or even rather advanced even for most of CS people.
 
 
To return to your question...
Basically, find_path takes a node connected to 'start', if not at the 'end', make the current node 'start' and see if find_path does return a path. As soon as a path is foud find_path quits searching.
 
You can look at find_all as a master routine that keeps calling find_path until find_path gives up. If the search space has not been exhausted (here there are still other nodes connected to 'start') take a suitable candidate call find_path from there until no more paths from there can be found. Repeat until no more suitable candidates.
 
As you have gone through the whole search space, all paths from 'start' to 'end' were found.
 
Recursion makes backtracking easier: the program/routine will by itself keep track of the steps taken & where to go back if a search fails.
 
Backtracking is the powerful technique of remembering the steps already taken & to retrace them till the first non-explored sidetrack when needed.
 
Choosing the next non-explored sidetrack though can be complex involving other searches, ...
It all depends on what you look for, how the data is represented.
 
A related topic that will help you understand things is breadth-first & depth-first searches on trees.
 
(in this case find_path executes a depth-first search on the graph - represented as a dictionary & find_all combines the 2 searches, first the depth search & when it quits, the breadth search takes over.)
 
Greetz 
On 4/15/08, Anshu Raval <reachmsn at hotmail.com> wrote: 


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! 









 

Planning marriage in 2008! Join Shaadi.com matrimony FREE! Try it now!_______________________________________________Tutor maillist  -  Tutor at python.orghttp://mail.python.org/mailman/listinfo/tutor
_________________________________________________________________
Technology : Catch up on updates on the latest Gadgets, Reviews, Gaming and Tips to use technology etc.
http://computing.in.msn.com/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20080423/b24c9a5f/attachment-0001.htm>