{
 "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": {}
  }
 ]
}