recursion in Class-methods?

klant circularfunc at yahoo.se
Thu Jun 26 06:43:40 CEST 2008


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



More information about the Python-list mailing list