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