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*<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!<http://ss1.richmedia.in/recurl.asp?pid=429> > > _______________________________________________ > Tutor maillist - Tutor@python.org > http://mail.python.org/mailman/listinfo/tutor > >
_______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
