En Tue, 08 Apr 2008 09:45:35 -0300, A.T.Hofkamp <[EMAIL PROTECTED]>
escribió:
> On 2008-04-08, [EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
>
> [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
--
Gabriel Genellina
--
http://mail.python.org/mailman/listinfo/python-list
