While trying to optimize this:
http://aspn.activestate.com/ASPN/Coo.../Recipe/119466
.... and still have a fast edge lookup, I've done the following tweaks:
class PathFind(object):
def __init__(self):
self.G = defaultdict(dict)
self.E = defaultdict(dict)
def addEdge(self, va, vb, cost, edge, way):
if way == -1: (vb, va) = (va, vb)
self.G[va][vb] = edge
if not way: self.G[vb][va] = edge
self.E[edge] = cost
def findPath(self, start, end):
def flatten(L): # Flatten linked list of form [0,[1,[2,[]]]]
while len(L) 0:
yield L[0]
L = L[1]
q = [(0, start, ())] # Heap of (cost, path_head, path_rest).
visited = set() # Visited vertices.
# Eliminate the dots pattern
push, pop, add = heapq.heappush, heapq.heappop, visited.add
G, E = self.G, self.E
while True:
(cost, v1, path) = pop(q)
if v1 not in visited:
add(v1)
path = (v1, path)
if v1 == end: return list(flatten(path))[::-1]
for (v2, e) in G[v1].iteritems():
if v2 not in visited:
push(q, (cost + E[e], v2, path))
def getEdges(self, path):
edges = []
for ix in xrange(len(path) - 1):
edges.append(self.G[path[ix]][path[ix + 1]])
return edges
addEdge() is used to initialize the Graph. It takes a way param: if -1
then the vertex order is reversed; 0 means it is bidir; 1 vertex order
is maintained.
This version maintains two Dictionaries: one for
pair_of_vertexes->edge and another for edge->cost.
findPath() will find the path between two vertexes and
getEdges(findPath()) will return this list of edges for that path.
The "Eliminate the dots" pattern actually improved performance in
about 10%. Still, I'm looking for some way to improve even more the
performance, while maintaining the dijkstra intact (I don't want an
A*). Psyco gave me about 20% of improvement. I wonder if anyone has
any idea to make this faster (maybe map? list comprehension? some
python trick?)...
Profiling blames the heapq (eheh). On a my CoreDuo T2300, it takes
1.6seconds to find a path of 800 vertexes in an half a million mesh.
Greetings!
Hugo Ferreira
