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__.Graph instance at 0x01D74378>

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

Traceback (most recent call last):
File "<pyshell#10>", line 1, in <module>
g.find_all_paths('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#11>", 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(newpath)
return paths

def find_shortest_path(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_path(self.dictionary, node,
end, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest

[Roopesh]

Wrong:
newpath = find_path(self.dictionary, node, end, path)
newpaths = find_all_paths(self.dictionary, node, end, path)
newpath = find_shortest_path(self.dictionary, node, end, path)

Correct;
newpath = self.find_path(self.dictionary, node, end, path)
newpaths = self.find_all_paths(self.dictionary, node, end, path)
newpath = self.find_shortest_path(self.dictionary, node, end, path)

Regards
Roopesh

[Bruno Desthuilliers]

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__.Graph instance at 0x01D74378>

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

Traceback (most recent call last):
File "<pyshell#10>", line 1, in <module>
g.find_all_paths('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#11>", 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-defa...en-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(start)

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

if start not in self.dictionnary:

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]

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]

>

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

if start not in self.dictionnary:

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