{ "metadata": { "name": "", "signature": "sha256:2dd04a4aee1b7409691d218147433fe56bcbf7998733e71f7ca224eaa4cea307" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Chapter 14 : Weighted Graphs" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Example 14.1 Page no: 681" ] }, { "cell_type": "code", "collapsed": false, "input": [ " \n", "class Edge:\n", " def __init__(self,sv,dv,d): # constructor\n", " self.srcVert = sv\n", " self.destVert = dv\n", " self.distance = d\n", "\n", "class PriorityQ:\n", " def __init__(self):\n", " # constructor\n", " self.queArray = []\n", " self.size = 0\n", " def insert(self,item): # insert item in sorted order\n", " self.queArray.append(item)\n", " b = self.size\n", " for j in range(self.size): # find place to insert\n", " if( item.distance >= self.queArray[j].distance ):\n", " b = j\n", " break\n", " for k in range(self.size-1,b-1,-1):#=self.size-1 k>=j k--) # move items up\n", " self.queArray[k+1] = self.queArray[k]\n", " self.queArray[b] = item\n", " # insert item\n", " self.size += 1\n", "\n", " def removeMin(self): # remove minimum item\n", " self.size -= 1\n", " return self.queArray[self.size] \n", "\n", " def removeN(self,n): # remove item at n\n", " for j in range(n,self.size-1): # move items down\n", " self.queArray[j] = self.queArray[j+1]\n", " self.size -= 1\n", "\n", " def peekMin(self): # peek at minimum item\n", " return self.self.queArray[self.size-1] \n", "\n", " def size(self): # return number of items\n", " return self.size\n", "\n", " def isEmpty(self): # true if queue is empty\n", " return (self.size==0) \n", "\n", " def peekN(self,n): # peek at item n\n", " return self.queArray[n]\n", "\n", " def find(self,findDex): # find item with specified\n", " # self.destVert value\n", " for j in range(self.size-1):\n", " if(self.queArray[j].destVert == findDex):\n", " return j\n", " return -1\n", "\n", "class Vertex:\n", " def __init__(self,lab): # constructor\n", " self.label = lab\n", " self.isInTree = False\n", "\n", "class Graph:\n", " def __init__(self):\n", " self.vertexList = [] # adjacency matrix\n", " self.adjMat = []\n", " self.nVerts = 0\n", " for j in range(20): # set adjacency\n", " l = []\n", " for k in range(20):\n", " l.append(1000000)\n", " self.adjMat.append(l)\n", " self.thePQ = PriorityQ()\n", " self.nTree = 0\n", " self.currentVert = 0\n", "\n", " def addVertex(self,lab):\n", " self.vertexList.append( Vertex(lab))\n", " self.nVerts += 1\n", "\n", " def addEdge(self,start, end,weight):\n", " self.adjMat[start][end] = weight\n", " self.adjMat[end][start] = weight\n", "\n", "\n", " def displayVertex(self,v):\n", " print self.vertexList[v].label ,\n", "\n", " def mstw(self):\n", " self.currentVert = 0 # minimum spanning tree\n", " # start at 0\n", " while(self.nTree < self.nVerts-1): # while not all verts in tree\n", " # put self.currentVert in tree\n", " self.vertexList[self.currentVert].isInTree = True\n", " self.nTree += 1\n", " # insert edges adjacent to self.currentVert into PQ\n", " for j in range(self.nVerts): # for each vertex,\n", " if(j==self.currentVert): # skip if its us\n", " continue\n", " if(self.vertexList[j].isInTree): # skip if in the tree\n", " continue\n", " self.distance = self.adjMat[self.currentVert][j]\n", " if( self.distance == 1000000): # skip if no edge\n", " continue\n", " self.putInPQ(j, self.distance) # put it in PQ (maybe)\n", " if(self.thePQ.size==0): # no vertices in PQ?\n", " print 'GRAPH NOT CONNECTED',\n", " return\n", " # remove edge with minimum self.distance, from PQ\n", " theEdge = self.thePQ.removeMin()\n", " sourceVert = theEdge.srcVert\n", " self.currentVert = theEdge.destVert\n", " # display edge from source to current\n", " print self.vertexList[sourceVert].label ,self.vertexList[self.currentVert].label, \" \",\n", "\n", " for j in range(self.nVerts): # unmark vertices\n", " self.vertexList[j].isIsTree = False\n", "\n", " def putInPQ(self,newVert,newDist): # is there another edge with the same destination vertex?\n", " queueIndex = self.thePQ.find(newVert)\n", " if(queueIndex != -1): # got edges index\n", " tempEdge = self.thePQ.peekN(queueIndex) # get edge\n", " oldDist = tempEdge.distance\n", " if(oldDist > newDist): # if new edge shorter,\n", " self.thePQ.removeN(queueIndex) # remove old edge\n", " theEdge = Edge(self.currentVert, newVert, newDist)\n", " self.thePQ.insert(theEdge)# insert new edge\n", " # else no action just leave the old vertex there\n", " else: # no edge with same destination vertex\n", " # so insert new one\n", " theEdge = Edge(self.currentVert, newVert, newDist)\n", " self.thePQ.insert(theEdge)\n", "\n", "\n", "theGraph = Graph()\n", "theGraph.addVertex('A') # 0 (start for mst)\n", "theGraph.addVertex('B') # 1\n", "theGraph.addVertex('C') # 2\n", "theGraph.addVertex('D') # 3\n", "theGraph.addVertex('E') # 4\n", "theGraph.addVertex('F') # 5\n", "theGraph.addEdge(0, 1, 16) # AB\n", "theGraph.addEdge(0, 3, 24) # AD\n", "\n", "theGraph.addEdge(1,2,1)\n", "theGraph.addEdge(1,3,5)\n", "theGraph.addEdge(1,4,2)\n", "theGraph.addEdge(2,3,6)\n", "theGraph.addEdge(2,4,8)\n", "theGraph.addEdge(2,5,26)\n", "theGraph.addEdge(3,4,142)\n", "theGraph.addEdge(4,5,17)\n", "\n", "print 'Minimum spanning tree: ',\n", "theGraph.mstw() # minimum spanning tree" ], "language": "python", "metadata": {}, "outputs": [] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Example 14.2 Page 703" ] }, { "cell_type": "code", "collapsed": false, "input": [ " \n", "class DistPar:\n", " def __init__(self,pv,d): # constructor\n", " self.distance = d\n", " self.parentVert = pv\n", "\n", "class Vertex:\n", " def __init__(self,lab): # constructor\n", " self.label = lab\n", " self.isInTree = False\n", "\n", "class Graph:\n", " def __init__(self): # constructor\n", " self.vertexList = [] # adjacency matrix\n", " self.adjMat = []\n", " self.nVerts = 0\n", " self.nTree = 0\n", " for j in range(20): # set adjacency\n", " l = []\n", " for k in range(20):\n", " l.append(1000000)\n", " self.adjMat.append(l)\n", " self.currentVert = 0\n", " self.sPath = [] # shortest paths\n", " self.startToCurrent = 0\n", "\n", " def addVertex(self,lab):\n", " self.vertexList.append( Vertex(lab))\n", " self.nVerts += 1\n", "\n", " def addEdge(self,start, end,weight):\n", " self.adjMat[start][end] = weight\n", "\n", "\n", " def displayVertex(self,v):\n", " print self.vertexList[v].label ,\n", "\n", " def path(self): # find all shortest paths\n", " startTree = 0 # start at vertex 0\n", " self.vertexList[startTree].isInTree = True\n", " self.nTree = 1 # put it in tree\n", " # transfer row of distances from adjMat to sPath\n", " for j in range(self.nVerts):\n", " tempDist = self.adjMat[startTree][j]\n", " try:\n", " self.sPath[j] = DistPar(startTree, tempDist)\n", " except:\n", " self.sPath.append(DistPar(startTree, tempDist))\n", " # until all vertices are in the tree\n", " while(self.nTree < self.nVerts):\n", " indexMin = self.getMin() # get minimum from sPath\n", " minDist = self.sPath[indexMin].distance\n", " if(minDist == 1000000): # if all infinite\n", " # or in tree,\n", " print 'There are unreachable vertices'\n", " break # sPath is complete\n", " else:\n", " # reset self.currentVert\n", " self.currentVert = indexMin # to closest vert\n", " self.startToCurrent = self.sPath[indexMin].distance\n", " # minimum distance from startTree is\n", " # to self.currentVert, and is self.startToCurrent\n", " # put current vertex in tree\n", " self.vertexList[self.currentVert].isInTree = True\n", " self.nTree += 1\n", " self.adjust_sPath() # update sPath[] array\n", "\n", " self.displayPaths() # display sPath[] contents\n", " self.nTree = 0 # clear tree\n", " for j in range(self.nVerts):\n", " self.vertexList[j].isInTree = False \n", "\n", " def getMin(self): # get entry from sPath\n", " minDist = 1000000 # assume minimum\n", " indexMin = 0\n", " for j in range(self.nVerts): # for each vertex,\n", " # if its in tree and\n", " if( not self.vertexList[j].isInTree and self.sPath[j].distance < minDist ):\n", " minDist = self.sPath[j].distance\n", " indexMin = j # update minimum\n", " return indexMin\n", "\n", " def adjust_sPath(self):\n", " # adjust values in shortest-path array sPath\n", " column = 1\n", " # skip starting vertex\n", " while(column < self.nVerts): # go across columns\n", " # if this columns vertex already in tree, skip it\n", " if( self.vertexList[column].isInTree ):\n", " column += 1\n", " continue\n", " # calculate distance for one sPath entry get edge from self.currentVert to column\n", " currentToFringe = self.adjMat[self.currentVert][column]\n", " # add distance from start\n", " startToFringe = self.startToCurrent + currentToFringe\n", " # get distance of current sPath entry\n", " sPathDist = self.sPath[column].distance\n", " # compare distance from start with sPath entry\n", " if(startToFringe < sPathDist): # if shorter,\n", " # update sPath\n", " self.sPath[column].parentVert = self.currentVert\n", " self.sPath[column].distance = startToFringe\n", " column += 1\n", "\n", " def displayPaths(self):\n", " for j in range(self.nVerts): # display contents of sPath[]\n", " print self.vertexList[j].label ,' =' \n", " if(self.sPath[j].distance == 1000000):\n", " print 'inf', # inf\n", " else:\n", " print self.sPath[j].distance , # 50\n", " parent = self.vertexList[ self.sPath[j].parentVert ].label\n", " print '(' , parent , ')' , # (A)\n", " print ''\n", " \n", "theGraph = Graph()\n", "theGraph.addVertex('A') # 0 (start)\n", "theGraph.addVertex('C') # 2\n", "theGraph.addVertex('B') # 1\n", "theGraph.addVertex('D') # 3\n", "theGraph.addVertex('E') # 4\n", "theGraph.addEdge(0,1,50)\n", "theGraph.addEdge(0,3,80)\n", "theGraph.addEdge(1,2,60)\n", "theGraph.addEdge(1,3,90)\n", "theGraph.addEdge(2,4,40)\n", "theGraph.addEdge(3,2,20)\n", "theGraph.addEdge(3,4,70)\n", "theGraph.addEdge(4,1,50)\n", "print 'Shortest paths' ,\n", "theGraph.path() # shortest paths" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Shortest paths A =\n", "inf ( A ) C =\n", "50 ( A ) B =\n", "100 ( D ) D =\n", "80 ( A ) E =\n", "140 ( B ) \n" ] } ], "prompt_number": 2 }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [] } ], "metadata": {} } ] }