By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
464,712 Members | 1,466 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 464,712 IT Pros & Developers. It's quick & easy.

recursion in Class-methods?

P: n/a
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
Jun 27 '08 #1
Share this Question
Share on Google+
4 Replies

P: n/a
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

Jun 27 '08 #2

P: n/a
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...)
Jun 27 '08 #3

P: n/a
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.
Jun 27 '08 #4

P: n/a
>
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).
Jun 27 '08 #5

This discussion thread is closed

Replies have been disabled for this discussion.