recursion in Class-methods?

[klant]

do i need to call Graph.find_path ?

>>g = Graph({'A': ['B', 'C'],

'B': ['C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F'],
'F': ['C']})

>>g

<__main__.Gra ph instance at 0x01D74378>

>>g.find_all_pa ths('A', 'C')

Traceback (most recent call last):
File "<pyshell#1 0>", line 1, in <module>
g.find_all_path s('A', 'C')
File "C:/Python25/Progs/pygameProgs/visualgraph/graph.py", line 26,
in find_all_paths
newpaths = find_all_paths( self.dictionary , node, end, path)
NameError: global name 'find_all_paths ' is not defined

>>g.find_path(' A', 'C')

Traceback (most recent call last):
File "<pyshell#1 1>", line 1, in <module>
g.find_path('A' , 'C')
File "C:/Python25/Progs/pygameProgs/visualgraph/graph.py", line 13,
in find_path
newpath = find_path(self. dictionary, node, end, path)
NameError: global name 'find_path' is not defined

>>>

class Graph:
def __init__(self, dictionary):
self.dictionary = dictionary

def find_path(self, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not self.dictionary .has_key(start) :
return None
for node in self.dictionary[start]:
if node not in path:
newpath = find_path(self. dictionary, node, end, path)
if newpath: return newpath
return None

def find_all_paths( self, start, end, path=[]):
path = path + [start]
if start == end:
return [path]
if not self.dictionary .has_key(start) :
return []
paths = []
for node in self.dictionary[start]:
if node not in path:
newpaths = find_all_paths( self.dictionary , node, end,
path)
for newpath in newpaths:
paths.append(ne wpath)
return paths

def find_shortest_p ath(self, start, end, path=[]):
path = path + [start]
if start == end:
return path
if not self.dictionary .has_key(start) :
return None
shortest = None
for node in self.dictionary[start]:
if node not in path:
newpath = find_shortest_p ath(self.dictio nary, node,
end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest

[Roopesh]

Re: recursion in Class-methods?

Wrong:
newpath = find_path(self. dictionary, node, end, path)
newpaths = find_all_paths( self.dictionary , node, end, path)
newpath = find_shortest_p ath(self.dictio nary, node, end, path)

Correct;
newpath = self.find_path( self.dictionary , node, end, path)
newpaths = self.find_all_p aths(self.dicti onary, node, end, path)
newpath = self.find_short est_path(self.d ictionary, node, end, path)

Regards
Roopesh

[Bruno Desthuilliers]

Re: recursion in Class-methods?

klant a écrit :

do i need to call Graph.find_path ?
>
>

>>>g = Graph({'A': ['B', 'C'],

'B': ['C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F'],
'F': ['C']})

>>>g

<__main__.Gra ph instance at 0x01D74378>

>>>g.find_all_p aths('A', 'C')

>
Traceback (most recent call last):
File "<pyshell#1 0>", line 1, in <module>
g.find_all_path s('A', 'C')
File "C:/Python25/Progs/pygameProgs/visualgraph/graph.py", line 26,
in find_all_paths
newpaths = find_all_paths( self.dictionary , node, end, path)
NameError: global name 'find_all_paths ' is not defined

>>>g.find_path( 'A', 'C')

>
Traceback (most recent call last):
File "<pyshell#1 1>", line 1, in <module>
g.find_path('A' , 'C')
File "C:/Python25/Progs/pygameProgs/visualgraph/graph.py", line 13,
in find_path
newpath = find_path(self. dictionary, node, end, path)
NameError: global name 'find_path' is not defined
>
>
>
>
class Graph:

Unless you need to ensure compat with ages-old Python versions, better
to use newstyle classes:

class Graph(object):

def __init__(self, dictionary):
self.dictionary = dictionary
>
def find_path(self, start, end, path=[]):

http://effbot.org/pyfaq/why-are-default-values-shared-between-objects.htm

Unless you exactly what you're doing (and given your current problem, I
can tell it's not the case), *don't* use mutable containers as default
function argument values.


def find_path(self, start, end, path=None):
if path is None:
path = []

path = path + [start]

path.append(sta rt)

if start == end:
return path
if not self.dictionary .has_key(start) :

if start not in self.dictionnar y:

return None

for node in self.dictionary[start]:
if node not in path:
newpath = find_path(self. dictionary, node, end, path)

newpath = self.find_path( ...)





(snip remaining code - same problems, same solutions...)

[defn noob]

Re: recursion in Class-methods?

class Graph(object):

where does anyone write like that? I've seen only examples like i have
written.

is the object then passed to init?


class Graph(object):
def __init__(self, dictionary):
self.structure = dictionary

or

class Graph(object):
def __init__(self, object):
self.structure = object


i dont get it.




and "mutable containers", do you refer to "path=[]" as a parameter.

[defn noob]

Re: recursion in Class-methods?

>

if start == end:
return path
if not self.dictionary .has_key(start) :

>
if start not in self.dictionnar y:
>

return None
for node in self.dictionary[start]:
if node not in path:
newpath = find_path(self. dictionary, node, end, path)

>
newpath = self.find_path( ...)
>
(snip remaining code - same problems, same solutions...)

it is to incoherent fo follow what you mean here(not meaning to sound
rude i appreciate the help).