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
--
http://mail.python.org/mailman/listinfo/python-list
