recursion in Class-methods?

Saul Spatz sspatz at kcnet.com
Fri Jun 27 03:56:30 CEST 2008


defn noob wrote:
>>>         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).

I modified your code as shown below, and it seems to work fine.  (I 
didn't test the shortest path part, just the example you gave.)

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

     def find_path(self, start, end, path=None):
         if not path:
             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 = self.find_path(node, end, path)
                 if newpath: return newpath
         return None

     def find_all_paths(self, start, end, path=None):
         if not path:
             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 = self.find_all_paths(node, end, path)
                 for newpath in newpaths:
                     paths.append(newpath)
         return paths

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

g = Graph({'A': ['B', 'C'],
              'B': ['C', 'D'],
              'C': ['D'],
              'D': ['C'],
              'E': ['F'],
              'F': ['C']})
print g.find_all_paths('A', 'C')

Output:
[['A', 'B', 'C'], ['A', 'B', 'D', 'C'], ['A', 'C']]

Here are the changes I made.
1) Inherit from object.  (Anticipation of 3.0)

2) Changed calls such as find_path(self.dictionary, node, end, path) to 
self.find_path(node, end, path).  In python, an objects methods have no
special privileges in calling its other methods.  They call it like
self.otherMethod(...).  Also, the first parameter is supposed to be a
Graph object.  I'm not sure what the effect of calling it with a 
dictionary would be.  BTW, "dictionary" seems like an uninformative
name. Why not call it "adjacent" or "neighbor", or "successor"?

3) Changed the default value of path to None, as suggested by Bruno 
Desthuilliers. What he's telling you is that the default object is 
created only once; when the method is defined.  If it's an int or a 
string, that doesn't matter.  You can't change it, and so you will 
always have the same default value if you need it.  If it's a mutable 
object, like a list, when your method changes it, as with
path = path + [start]
it changes the global default object; the next time you need it, it 
won't be [] but whatever you last changed it to.

This last is a tricky point.  I hope I've been clear.

Saul



More information about the Python-list mailing list