Menu
▾
▴
[Pythoncard-cvs] PythonCard/samples/dijkstra .cvsignore, NONE, 1.1 dijkstra.py, NONE, 1.1 dijkstra.rsrc.py, NONE, 1.1 map.xyz, NONE, 1.1 priodict.py, NONE, 1.1 readme.txt, NONE, 1.1 shortpath.py, NONE, 1.1
Update of /cvsroot/pythoncard/PythonCard/samples/dijkstra In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv13249/samples/dijkstra Added Files: .cvsignore dijkstra.py dijkstra.rsrc.py map.xyz priodict.py readme.txt shortpath.py Log Message: added dijkstra sample --- NEW FILE: .cvsignore --- .cvsignore *.pyc *.log *.pyw .DS_Store --- NEW FILE: shortpath.py --- """ Dijkstra's algorithm for shortest paths, David Eppstein, UC Irvine, 4 April 2002 url: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228 modified by Jure Vrscaj for purposes of dijkstra.py """ import random from priodict import priorityDictionary def Dijkstra(imgdict,start,end=None,zmin=None,zmax=None,can=None,zoom=1): """ Find shortest paths from the start vertex to all vertices nearer than or equal to the end. The input graph G is assumed to have the following representation: A vertex can be any object that can be used as an index into a dictionary. G is a dictionary, indexed by vertices. For any vertex v, G[v] is itself a dictionary, indexed by the neighbors of v. For any edge v->w, G[v][w] is the length of the edge. This is related to the representation in <http://www.python.org/doc/essays/graphs.html> where Guido van Rossum suggests representing graphs as dictionaries mapping vertices to lists of neighbors, however dictionaries of edges have many advantages over lists: they can store extra information (here, the lengths), they support fast existence tests, and they allow easy modification of the graph by edge insertion and removal. Such modifications are not needed here but are important in other graph algorithms. Since dictionaries obey iterator protocol, a graph represented as described here could be handed without modification to an algorithm using Guido's representation. Of course, G and G[v] need not be Python dict objects; they can be any other object that obeys dict protocol, for instance a wrapper in which vertices are URLs and a call to G[v] loads the web page and finds its links. The output is a pair (D,P) where D[v] is the distance from start to v and P[v] is the predecessor of v along the shortest path from s to v. Dijkstra's algorithm is only guaranteed to work correctly when all edge lengths are positive. This code does not verify this property for all edges (only the edges seen before the end vertex is reached), but will correctly compute shortest paths even for some graphs with negative edges, and will raise an exception if it discovers that a negative edge has caused it to make a mistake. """ D = {} # dictionary of final distances P = {} # dictionary of predecessors Q = priorityDictionary() # est.dist. of non-final vert. Q[start] = 0 dirlist = [ (1,0),(-1,0),(0,1),(0,-1), (1,1), (-1,1), (-1,-1), (1,-1), #(2,0),(-2,0),(0,2),(0,-2), (2,2), (-2,2), (-2,-2), (2,-2), ] if can: can.autoRefresh = False refreshtime = len(imgdict)/100 for v in Q: x,y = v z = imgdict.get(v,-1) if z < zmin or z > zmax: continue D[v] = Q[v] if can: if (random.randint(0,refreshtime) == 0): can.refresh() pass can.foregroundColor = can.fillColor = (0x00,(D[v]*10)%255,(D[v]*10)%255) can.drawPoint([a*zoom for a in v]) if v == end: break for dx,dy in dirlist: w = (x+dx, y+dy) z2 = imgdict.get(w) if z2 == None: continue else: dz = z2 - z #vwLength = D[v]+(dx**2 + dy**2)**0.5 vwLength = D[v] + (dx**2 + dy**2 + dz**2)**0.5 if w in D: if vwLength < D[w]: raise ValueError, "Dijkstra: found better path to already-final vertex" elif w not in Q or vwLength < Q[w]: Q[w] = vwLength P[w] = v if can: can.autoRefresh = True can.refresh() return (D,P) def shortestPath(imgdict,start,end,zmin=0,zmax=255,can=None,zoom=1): """ Find a single shortest path from the given start vertex to the given end vertex. The input has the same conventions as Dijkstra(). The output is a list of the vertices in order along the shortest path. sample graph: G = {'s':{'u':10, 'x':5}, 'u':{'v':1, 'x':2}, 'v':{'y':4}, 'x':{'u':3, 'v':9, 'y':2}, 'y':{'s':7, 'v':6}} """ D,P = Dijkstra(imgdict,start,end,zmin,zmax,can,zoom) if False and can: can.foregroundColor = can.fillColor = (0xFF,0x00,0x00) for vert in D: Path = [] while 1: Path.append(vert) if vert == start: break vert = P.get(vert, start) can.drawPointList(Path) Path = [] while 1: Path.append(end) if end == start: break end = P.get(end, start) Path.reverse() return Path --- NEW FILE: priodict.py --- # Priority dictionary using binary heaps # David Eppstein, UC Irvine, 8 Mar 2002 from __future__ import generators class priorityDictionary(dict): def __init__(self): '''Initialize priorityDictionary by creating binary heap of pairs (value,key). Note that changing or removing a dict entry will not remove the old pair from the heap until it is found by smallest() or until the heap is rebuilt.''' self.__heap = [] dict.__init__(self) def smallest(self): '''Find smallest item after removing deleted items from heap.''' if len(self) == 0: raise IndexError, "smallest of empty priorityDictionary" heap = self.__heap while heap[0][1] not in self or self[heap[0][1]] != heap[0][0]: lastItem = heap.pop() insertionPoint = 0 while 1: smallChild = 2*insertionPoint+1 if smallChild+1 < len(heap) and \ heap[smallChild] > heap[smallChild+1]: smallChild += 1 if smallChild >= len(heap) or lastItem <= heap[smallChild]: heap[insertionPoint] = lastItem break heap[insertionPoint] = heap[smallChild] insertionPoint = smallChild return heap[0][1] def __iter__(self): '''Create destructive sorted iterator of priorityDictionary.''' def iterfn(): while len(self) > 0: x = self.smallest() yield x del self[x] return iterfn() def __setitem__(self,key,val): '''Change value stored in dictionary and add corresponding pair to heap. Rebuilds the heap if the number of deleted items grows too large, to avoid memory leakage.''' dict.__setitem__(self,key,val) heap = self.__heap if len(heap) > 2 * len(self): self.__heap = [(v,k) for k,v in self.iteritems()] self.__heap.sort() # builtin sort likely faster than O(n) heapify else: newPair = (val,key) insertionPoint = len(heap) heap.append(None) while insertionPoint > 0 and \ newPair < heap[(insertionPoint-1)//2]: heap[insertionPoint] = heap[(insertionPoint-1)//2] insertionPoint = (insertionPoint-1)//2 heap[insertionPoint] = newPair def setdefault(self,key,val): '''Reimplement setdefault to call our customized __setitem__.''' if key not in self: self[key] = val return self[key] --- NEW FILE: dijkstra.py --- #!/usr/bin/python """ [ Dijkstra's shortest path demo ] A visual demonstration of shortest path algorithm. version: 0.42b date: 2006-7-25 author: Jure Vrscaj <ju...@co...> homepage: http://codeshift.net/dijkstra """ from PythonCard import configuration, dialog, model import time try: import shortpath as dijkstra except: print 'Dijkstra not found, shortest path will not work' dijkstra = None try: import psyco psyco.full() except: print 'Psyco not found, ignoring it' def t(f, *args): start = time.time() #r = eval(s, g) r = f(*args) print " t: %f ms" % ((time.time()-start) * 1000) return r class App(model.Background): imgdict = {} G = {} lastpath = {} scalex = 1 scaley = 1 scalez = 1 offsetx = 0 offsety = 0 offsetz = 0 zoom = 2 startpoint = None endpoint = None zmin = 0 zmax = 255 showplague = False def on_initialize(self, _event): can = self.components.canvas1 self.on_size(None) try: self.imp('map.xyz') self.draw() except: can.drawCircle((100, 100), 10) def status(self, text): print text self.title = text def shortpath(self, mod=dijkstra): can = self.components.canvas1 start = self.startpoint end = self.endpoint zoom = self.zoom print "searching for shortest path... start=%s, end=%s"%(start, end) self.lastpath = t(mod.shortestPath, self.imgdict, start, end, self.zmin, self.zmax, {True:can}.get(self.showplague, False), zoom) can.foregroundColor = can.fillColor = (0x00,0x00,0xFF) for xy in self.lastpath: can.drawCircle([a*zoom for a in xy], zoom/2+1) def draw(self): can = self.components.canvas1 can.clear() colorpoints = {} for point, z in self.imgdict.iteritems(): x,y = point x,y = int(x*self.zoom),int(y*self.zoom) try: colorpoints[z].append((x,y)) except: colorpoints[z] = [(x,y)] try: zoom = int(self.zoom) assert(zoom) except: zoom = 1 ar = can.autoRefresh can.autoRefresh = False for color, points in colorpoints.iteritems(): if color < self.zmin: can.foregroundColor = can.fillColor = (0,color,0) elif color > self.zmax: can.foregroundColor = can.fillColor = (0,color,0) else: can.foregroundColor = can.fillColor = (color,color,color) if zoom == 1: can.drawPointList(points) else: for x,y in points: can.drawRectangle( (x,y), (zoom,zoom) ) can.refresh() can.autoRefresh = ar def imp(self, filename): self.status('Importing %s ...'%filename) self.imgdict = {} f = open(filename) for line in f: try: x,y,z = [float(a) for a in line.split()] except Exception,e: print "ERR: Ignoring line", line, "could not be parsed:", e continue x += self.offsetx y += self.offsety z += self.offsetz x *= self.scalex y *= self.scaley z *= self.scalez x, y, z = int(x), int(y), int(z) self.imgdict[(x,y)] = z self.status('Imported %s points.'%len(self.imgdict)) def on_size(self, event): can = self.components.canvas1 size = self.GetClientSize() can.SetSize(size) try: event.skip() except: pass def on_canvas1_mouseMiddleDown(self, event): self.showplague = not self.showplague def on_canvas1_mouseContextDown(self, event): self.on_canvas1_mouseDown(event, mod=dijkstra_alt) def on_canvas1_mouseDown(self, event, mod=None): if not mod: mod = dijkstra can = event.target x, y = [int(a/self.zoom) for a in event.position] color = self.imgdict.get((x,y)) self.status('color at %s,%s: %s'%(x,y,color)) if self.endpoint or not self.startpoint: self.startpoint = (x,y) self.endpoint = None can.foregroundColor = can.fillColor = (0x0,0xFF,0x0) can.drawCircle((x*self.zoom, y*self.zoom), 2) else: self.endpoint = (x,y) can.foregroundColor = can.fillColor = (0x0,0xFF,0x0) can.drawCircle((x*self.zoom, y*self.zoom), 2) can.redraw() self.shortpath(mod) def on_menuFileImport_select(self, event): wildcard = "*.xyz|*.xyz|*.*|*.*" result = dialog.openFileDialog(wildcard=wildcard) paths = result.paths if not result.accepted: return for a in paths: self.imp(a) self.draw() def on_menuActionDraw_select(self, event): self.draw() if __name__ == '__main__': configuration.setOption('showShell', True) app = model.Application(App) app.MainLoop() --- NEW FILE: map.xyz --- 5 54 133 98 141 63 47 68 156 37 -9 123 17 113 97 169 78 86 118 123 172 178 132 102 141 16 30 23 44 142 89 -15 70 168 1 17 117 34 76 64 82 153 140 95 85 73 132 146 36 24 115 22 95 37 62 -26 133 [...32841 lines suppressed...] 116.0 96.0 146.0 153.0 26.0 36.0 102.0 23.0 99.0 139.0 27.0 48.0 21.0 19.0 119.0 44.0 148.0 103.0 7.0 32.0 119.0 161.0 149.0 68.0 128.0 -8.0 12.0 91.0 -20.0 94.0 92.0 136.0 132.0 115.0 89.0 147.0 78.0 79.0 184.0 48.0 46.0 123.0 157.0 139.0 95.0 82.0 -2.0 7.0 6.0 107.0 77.0 172.0 135.0 48.0 91.0 113.0 150.0 77.0 62.0 153.0 --- NEW FILE: dijkstra.rsrc.py --- {'application':{'type':'Application', 'name':'Template', 'backgrounds': [ {'type':'Background', 'name':'background', 'title':u'shortest path', 'size':(389, 350), 'style':['resizeable'], 'menubar': {'type':'MenuBar', 'menus': [ {'type':'Menu', 'name':'menuFile', 'label':'&File', 'items': [ {'type':'MenuItem', 'name':'menuFileImport', 'label':u'&Import', }, {'type':'MenuItem', 'name':'menuFileExit', 'label':'E&xit', 'command':'exit', }, ] }, {'type':'Menu', 'name':'menuAction', 'label':u'&Action', 'items': [ {'type':'MenuItem', 'name':'menuActionDraw', 'label':u'Draw', }, ] }, {'type':'Menu', 'name':'menu', 'label':u'', 'items': [ ] }, ] }, 'components': [ {'type':'BitmapCanvas', 'name':'canvas1', 'position':(0, 0), 'size':(180, 146), 'backgroundColor':(255, 255, 255), 'foregroundColor':(0, 0, 0), }, ] # end components } # end background ] # end backgrounds } } --- NEW FILE: readme.txt --- Dijkstra's Shortest Path Algorithm Demo by Jure Vrscaj Click anywhere on the map to set the starting point and another click to set the end point, after that you should see a blue line connecting the two points. If you want to see how dijkstra does the trick, use the shell window and type: >>> self.showplague = True http://codeshift.net/dijkstra |