diff options
Diffstat (limited to 'Data_Structures_and_Algorithms_in_Java/ch14.ipynb')
| -rw-r--r-- | Data_Structures_and_Algorithms_in_Java/ch14.ipynb | 314 |
1 files changed, 306 insertions, 8 deletions
diff --git a/Data_Structures_and_Algorithms_in_Java/ch14.ipynb b/Data_Structures_and_Algorithms_in_Java/ch14.ipynb index 7895bf4f..46aa59dc 100644 --- a/Data_Structures_and_Algorithms_in_Java/ch14.ipynb +++ b/Data_Structures_and_Algorithms_in_Java/ch14.ipynb @@ -1,6 +1,7 @@ { "metadata": { - "name": "ch14" + "name": "", + "signature": "sha256:2dd04a4aee1b7409691d218147433fe56bcbf7998733e71f7ca224eaa4cea307" }, "nbformat": 3, "nbformat_minor": 0, @@ -11,18 +12,174 @@ "cell_type": "heading", "level": 1, "metadata": {}, - "source": "Chapter 14 : Weighted Graphs" + "source": [ + "Chapter 14 : Weighted Graphs" + ] }, { "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 14.1 Page no: 681" + "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", + "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": [] @@ -31,19 +188,160 @@ "cell_type": "heading", "level": 3, "metadata": {}, - "source": "Example 14.2 Page 703" + "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", + "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 =\ninf ( A ) C =\n50 ( A ) B =\n100 ( D ) D =\n80 ( A ) E =\n140 ( B ) \n" + "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 @@ -51,7 +349,7 @@ { "cell_type": "code", "collapsed": false, - "input": "", + "input": [], "language": "python", "metadata": {}, "outputs": [] |