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: [EMAIL PROTECTED]: [EMAIL
PROTECTED]: Re: [Tutor] Recursion doubtCC: tutor@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 <[EMAIL PROTECTED]> 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 - [EMAIL
PROTECTED]://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/_______________________________________________
Tutor maillist - Tutor@python.org
http://mail.python.org/mailman/listinfo/tutor
