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']})
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
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']})
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
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-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(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).

 

[Bruno Desthuilliers]

defn noob a écrit :

class Graph(object):

where does anyone write like that?

Almost everywhere nowadays.

I've seen only examples like i have
written.

Most of the doc has still not been updated since the introduction of
newstyle classes years ago. You'll find more here:
http://docs.python.org/ref/node33.html

is the object then passed to init?

Nope, it's the base class for your Graph class.

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

or

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

parent class list in a class statement and argument list of an
initializer are totally unrelated.

The syntax for a class statement is:
classdef ::= "class" classname [inheritance] ":" suite
inheritance ::= "(" [expression_list] ")"
classname ::= identifier

cf http://docs.python.org/ref/class.html

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

Indeed. This is one of the most (in)famous Python gotchas.