Cannot understand the detailedly the following code

[reachmsn]

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!

 

[Gabriel Genellina]

[deleted a long piece of text by our BDFL about recursive graph
path-finding algorithm]

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!

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

 

[reachmsn]

[deleted a long piece of text by our BDFL about recursive graph path-finding algorithm]

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!

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.)

As for the actual procedure of writing a function:

First define the input and output parameters/values of the function.
(ie what goes in, and what comes out)

For recursive functions, there are always two cases, a terminating case, and a
reduction case. In the first case, you may not use the recursive function, in
the latter function you should.
Both cases should use the information available from the input parameters, and
provide a result that matches with the output requirements of the function.. Add
a if/then/else that distinguishes between what case you have, and you're done.

Sincerely,
Albert

OK so trying to follow your instructions I have-


def find_all_paths(graph, start, end, path=[]):


for node in graph[start]:

 

[reachmsn]

[deleted a long piece of text by our BDFL about recursive graph path-finding algorithm]

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!

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.)

As for the actual procedure of writing a function:

First define the input and output parameters/values of the function.
(ie what goes in, and what comes out)

For recursive functions, there are always two cases, a terminating case, and a
reduction case. In the first case, you may not use the recursive function, in
the latter function you should.
Both cases should use the information available from the input parameters, and
provide a result that matches with the output requirements of the function.. Add
a if/then/else that distinguishes between what case you have, and you're done.

Sincerely,
Albert

Ok following these instructions one gets

def find_all_paths(graph, start, end, path=[]):
path= path+ [start]

for node in graph[start]:

find_all_paths(graph, node, end, path)

Now >

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!

 

[reachmsn]

Ok following these instructions one gets

def find_all_paths(graph, start, end, path=[]):
 path= path+ [start]

 for node in graph[start]:

   find_all_paths(graph, node, end, path)

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
230698762085269459068388639078903870385790368703879038285790 and
5938063786093895682682968390789380834687387689762897. 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.- Hide quoted text -

- Show quoted text -

Hello,



Thank you for the suggestion of relaxing!



After that the black box function you mentioned looks like this-





Output- path1

path 2

| ... path n

|

|

|

----------------------

| |

| |

| function -find_ |

| _all_paths() |

| |

----------------------

|

|

|

|



Input - graph, start, end





i.e. you give, the graph, the start and end vertices as inputs and you
get the output as a listing of all the paths. This is where I got to.
It would be very nice if you could kindly hint on how to proceed
further. Thank you so much for your time!



Thanks & Regards,

Anshu

 

[Gabriel Genellina]

i.e. you give, the graph, the start and end vertices as inputs and you
get the output as a listing of all the paths. This is where I got to.
It would be very nice if you could kindly hint on how to proceed
further. Thank you so much for your time!

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.lang.python/msg/9f0b10631fd47886

 

[reachmsn]

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.lang.python/msg/9f0b10631fd47886

Hi,

I did read the post by Neil Cerutti, but I still am unable to write
this recursive function. I will appreciate it if someone can kindly
guide me.

Thanks,
Anshu

 

[reachmsn]

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.lang.python/msg/9f0b10631fd47886

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