1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
{
"metadata": {
"name": "ch14"
},
"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": "'''\nexample 14.1\ndemonstrates minimum spanning tree with weighted graphs\n'''\nclass Edge:\n def __init__(self,sv,dv,d): # constructor\n self.srcVert = sv\n self.destVert = dv\n self.distance = d\n\nclass 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\nclass Vertex:\n def __init__(self,lab): # constructor\n self.label = lab\n self.isInTree = False\n\nclass 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\ntheGraph = Graph()\ntheGraph.addVertex('A') # 0 (start for mst)\ntheGraph.addVertex('B') # 1\ntheGraph.addVertex('C') # 2\ntheGraph.addVertex('D') # 3\ntheGraph.addVertex('E') # 4\ntheGraph.addVertex('F') # 5\ntheGraph.addEdge(0, 1, 16) # AB\ntheGraph.addEdge(0, 3, 24) # AD\n\ntheGraph.addEdge(1,2,1)\ntheGraph.addEdge(1,3,5)\ntheGraph.addEdge(1,4,2)\ntheGraph.addEdge(2,3,6)\ntheGraph.addEdge(2,4,8)\ntheGraph.addEdge(2,5,26)\ntheGraph.addEdge(3,4,142)\ntheGraph.addEdge(4,5,17)\n\nprint 'Minimum spanning tree: ',\ntheGraph.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": "'''\nexample 14.2\ndemonstrates shortest path with weighted, directed graphs\n'''\nclass DistPar:\n def __init__(self,pv,d): # constructor\n self.distance = d\n self.parentVert = pv\n\nclass Vertex:\n def __init__(self,lab): # constructor\n self.label = lab\n self.isInTree = False\n\nclass 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 \ntheGraph = Graph()\ntheGraph.addVertex('A') # 0 (start)\ntheGraph.addVertex('C') # 2\ntheGraph.addVertex('B') # 1\ntheGraph.addVertex('D') # 3\ntheGraph.addVertex('E') # 4\ntheGraph.addEdge(0,1,50)\ntheGraph.addEdge(0,3,80)\ntheGraph.addEdge(1,2,60)\ntheGraph.addEdge(1,3,90)\ntheGraph.addEdge(2,4,40)\ntheGraph.addEdge(3,2,20)\ntheGraph.addEdge(3,4,70)\ntheGraph.addEdge(4,1,50)\nprint 'Shortest paths' ,\ntheGraph.path() # shortest paths",
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": "Shortest paths A =\ninf ( A ) C =\n50 ( A ) B =\n100 ( D ) D =\n80 ( A ) E =\n140 ( B ) \n"
}
],
"prompt_number": 2
},
{
"cell_type": "code",
"collapsed": false,
"input": "",
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}
|
