dijkstra_eppstein

dijkstra_eppstein.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# priorityDictionary - heap\n",
    "# http://code.activestate.com/recipes/117228/\n",
    "# Priority dictionary using binary heaps\n",
    "# David Eppstein, UC Irvine, 8 Mar 2002\n",
    "\n",
    "from __future__ import generators\n",
    "\n",
    "class priorityDictionary(dict):\n",
    "    def __init__(self):\n",
    "        '''Initialize priorityDictionary by creating binary heap\n",
    "of pairs (value,key).  Note that changing or removing a dict entry will\n",
    "not remove the old pair from the heap until it is found by smallest() or\n",
    "until the heap is rebuilt.'''\n",
    "        self.__heap = []\n",
    "        dict.__init__(self)\n",
    "\n",
    "    def smallest(self):\n",
    "        '''Find smallest item after removing deleted items from heap.'''\n",
    "        if len(self) == 0:\n",
    "            raise IndexError(\"smallest of empty priorityDictionary\")\n",
    "        heap = self.__heap\n",
    "        while heap[0][1] not in self or self[heap[0][1]] != heap[0][0]:\n",
    "            lastItem = heap.pop()\n",
    "            insertionPoint = 0\n",
    "            while 1:\n",
    "                smallChild = 2*insertionPoint+1\n",
    "                if smallChild+1 < len(heap) and \\\n",
    "                        heap[smallChild] > heap[smallChild+1]:\n",
    "                    smallChild += 1\n",
    "                if smallChild >= len(heap) or lastItem <= heap[smallChild]:\n",
    "                    heap[insertionPoint] = lastItem\n",
    "                    break\n",
    "                heap[insertionPoint] = heap[smallChild]\n",
    "                insertionPoint = smallChild\n",
    "        return heap[0][1]\n",
    "\n",
    "    def __iter__(self):\n",
    "        '''Create destructive sorted iterator of priorityDictionary.'''\n",
    "        def iterfn():\n",
    "            while len(self) > 0:\n",
    "                x = self.smallest()\n",
    "                yield x\n",
    "                del self[x]\n",
    "        return iterfn()\n",
    "\n",
    "    def __setitem__(self,key,val):\n",
    "        '''Change value stored in dictionary and add corresponding\n",
    "pair to heap.  Rebuilds the heap if the number of deleted items grows\n",
    "too large, to avoid memory leakage.'''\n",
    "        dict.__setitem__(self,key,val)\n",
    "        heap = self.__heap\n",
    "        if len(heap) > 2 * len(self):\n",
    "            self.__heap = [(v,k) for k,v in self.iteritems()]\n",
    "            self.__heap.sort()  # builtin sort likely faster than O(n) heapify\n",
    "        else:\n",
    "            newPair = (val,key)\n",
    "            insertionPoint = len(heap)\n",
    "            heap.append(None)\n",
    "            while insertionPoint > 0 and \\\n",
    "                    newPair < heap[(insertionPoint-1)//2]:\n",
    "                heap[insertionPoint] = heap[(insertionPoint-1)//2]\n",
    "                insertionPoint = (insertionPoint-1)//2\n",
    "            heap[insertionPoint] = newPair\n",
    "\n",
    "    def setdefault(self,key,val):\n",
    "        '''Reimplement setdefault to call our customized __setitem__.'''\n",
    "        if key not in self:\n",
    "            self[key] = val\n",
    "        return self[key]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Dijkstra\n",
    "# http://www.ics.uci.edu/~eppstein/161/python/dijkstra.py\n",
    "# Dijkstra's algorithm for shortest paths\n",
    "# David Eppstein, UC Irvine, 4 April 2002\n",
    "\n",
    "def Dijkstra(G,start,end=None):\n",
    "\t\"\"\"\n",
    "\tFind shortest paths from the  start vertex to all vertices nearer than or equal to the end.\n",
    "\n",
    "\tThe input graph G is assumed to have the following representation:\n",
    "\tA vertex can be any object that can be used as an index into a dictionary.\n",
    "\tG is a dictionary, indexed by vertices.  For any vertex v, G[v] is itself a dictionary,\n",
    "\tindexed by the neighbors of v.  For any edge v->w, G[v][w] is the length of the edge.\n",
    "\tThis is related to the representation in <http://www.python.org/doc/essays/graphs.html>\n",
    "\twhere Guido van Rossum suggests representing graphs as dictionaries mapping vertices\n",
    "\tto lists of outgoing edges, however dictionaries of edges have many advantages over lists:\n",
    "\tthey can store extra information (here, the lengths), they support fast existence tests,\n",
    "\tand they allow easy modification of the graph structure by edge insertion and removal.\n",
    "\tSuch modifications are not needed here but are important in many other graph algorithms.\n",
    "\tSince dictionaries obey iterator protocol, a graph represented as described here could\n",
    "\tbe handed without modification to an algorithm expecting Guido's graph representation.\n",
    "\n",
    "\tOf course, G and G[v] need not be actual Python dict objects, they can be any other\n",
    "\ttype of object that obeys dict protocol, for instance one could use a wrapper in which vertices\n",
    "\tare URLs of web pages and a call to G[v] loads the web page and finds its outgoing links.\n",
    "\t\n",
    "\tThe output is a pair (D,P) where D[v] is the distance from start to v and P[v] is the\n",
    "\tpredecessor of v along the shortest path from s to v.\n",
    "\t\n",
    "\tDijkstra's algorithm is only guaranteed to work correctly when all edge lengths are positive.\n",
    "\tThis code does not verify this property for all edges (only the edges examined until the end\n",
    "\tvertex is reached), but will correctly compute shortest paths even for some graphs with negative\n",
    "\tedges, and will raise an exception if it discovers that a negative edge has caused it to make a mistake.\n",
    "\t\"\"\"\n",
    "\n",
    "\tD = {}\t# dictionary of final distances\n",
    "\tP = {}\t# dictionary of predecessors\n",
    "\tQ = priorityDictionary()\t# estimated distances of non-final vertices\n",
    "\tQ[start] = 0\n",
    "\t\n",
    "\tfor v in Q:\n",
    "\t\tD[v] = Q[v]\n",
    "\t\tif v == end: break\n",
    "\t\t\n",
    "\t\tfor w in G[v]:\n",
    "\t\t\tvwLength = D[v] + G[v][w]\n",
    "\t\t\tif w in D:\n",
    "\t\t\t\tif vwLength < D[w]:\n",
    "\t\t\t\t\traise ValueError(\"Dijkstra: found better path to already-final vertex\")\n",
    "\t\t\telif w not in Q or vwLength < Q[w]:\n",
    "\t\t\t\tQ[w] = vwLength\n",
    "\t\t\t\tP[w] = v\n",
    "\t\n",
    "\treturn (D,P)\n",
    "\t\t\t\n",
    "def shortestPath(G,start,end):\n",
    "\t\"\"\"\n",
    "\tFind a single shortest path from the given start vertex to the given end vertex.\n",
    "\tThe input has the same conventions as Dijkstra().\n",
    "\tThe output is a list of the vertices in order along the shortest path.\n",
    "\t\"\"\"\n",
    "\n",
    "\tD,P = Dijkstra(G,start,end)\n",
    "\tPath = []\n",
    "\twhile 1:\n",
    "\t\tPath.append(end)\n",
    "\t\tif end == start: break\n",
    "\t\tend = P[end]\n",
    "\tPath.reverse()\n",
    "\treturn Path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "({'s': 0, 'v': 9, 'y': 7, 'x': 5, 'u': 8}, {'v': 'u', 'u': 'x', 'x': 's', 'y': 'x'})\n",
      "['s', 'x', 'u', 'v']\n"
     ]
    }
   ],
   "source": [
    "# example, CLR p.528\n",
    "G = {'s': {'u':10, 'x':5},\n",
    "\t'u': {'v':1, 'x':2},\n",
    "\t'v': {'y':4},\n",
    "\t'x':{'u':3,'v':9,'y':2},\n",
    "\t'y':{'s':7,'v':6}}\n",
    "\n",
    "print(Dijkstra(G,'s'))\n",
    "print(shortestPath(G,'s','v'))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}