{ "metadata": { "name": "", "signature": "sha256:e4ee94b1921cc19d6665af422d1e40ebb2336538caa9a0070a2828a133297159" }, "nbformat": 3, "nbformat_minor": 0, "worksheets": [ { "cells": [ { "cell_type": "heading", "level": 1, "metadata": {}, "source": [ "Chapter 13 : Graphs" ] }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Example 13.1 Page no: 631" ] }, { "cell_type": "code", "collapsed": false, "input": [ " \n", "class StackX:\n", " def __init__(self):\n", " self.st = [] # make array\n", " self.top = -1\n", "\n", " def push(self,j): # put item on stack\n", " self.top += 1\n", " self.st.append(j)\n", "\n", " def pop(self): # take item off stack\n", " self.top -= 1\n", " return self.st.pop()\n", "\n", " def peek(self): # peek at top of stack\n", " return self.st[self.top]\n", " \n", " def isEmpty(self): # true if nothing on stack-\n", " return self.top == -1\n", "\n", "class Vertex:\n", " def __init__(self,lab): # constructor\n", " self.label = lab\n", " self.wasVisited = 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(0)\n", " self.adjMat.append(l)\n", " self.theStack = StackX()\n", "\n", " def addVertex(self,lab):\n", " self.vertexList.append( Vertex(lab))\n", " self.nVerts += 1\n", "\n", " def addEdge(self,start, end):\n", " self.adjMat[start][end] = 1\n", " self.adjMat[end][start] = 1\n", "\n", " def displayVertex(self,v):\n", " print self.vertexList[v].label ,\n", "\n", " def dfs(self): # depth-first search # begin at vertex 0\n", " self.vertexList[0].wasVisited = True # mark it\n", " self.displayVertex(0) # display it\n", " self.theStack.push(0) # push it\n", " while( not self.theStack.isEmpty() ): # until stack empty,\n", " # get an unvisited vertex adjacent to stack top\n", " v = self.getAdjUnvisitedVertex( self.theStack.peek() )\n", " if(v == -1): # if no such vertex,\n", " self.theStack.pop()\n", " else: # if it exists,\n", " self.vertexList[v].wasVisited = True # mark it\n", " self.displayVertex(v) # display it\n", " self.theStack.push(v) # push it\n", "\n", " # stack is empty, so we're done\n", " for j in range(self.nVerts): # reset flags\n", " self.vertexList[j].wasVisited = False # end dfs\n", "\n", " def getAdjUnvisitedVertex(self,v):\n", " for j in range(self.nVerts):\n", " if(self.adjMat[v][j]==1 and self.vertexList[j].wasVisited==False):\n", " return j\n", " return -1\n", "\n", "theGraph = Graph()\n", "theGraph.addVertex('A') # 0 (start for dfs)\n", "theGraph.addVertex('B') # 1\n", "theGraph.addVertex('C') # 2\n", "theGraph.addVertex('D') # 3\n", "theGraph.addVertex('E') # 4\n", "theGraph.addEdge(0,1)\n", "theGraph.addEdge(1,2)\n", "theGraph.addEdge(0,3)\n", "theGraph.addEdge(3,4)\n", "print 'Visits: ',\n", "theGraph.dfs() # depth-first search" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Visits: A B C D E\n" ] } ], "prompt_number": 1 }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Example 13.2 Page no : 639" ] }, { "cell_type": "code", "collapsed": false, "input": [ " \n", "class Queue:\n", " def __init__(self): # constructor\n", " self.SIZE = 20\n", " self.queArray = []\n", " for i in range(20):\n", " self.queArray.append(0)\n", " self.front = 0\n", " self.rear = -1\n", "\n", " def insert(self,j): # put item at self.rear of queue\n", " if(self.rear == self.SIZE-1):\n", " self.rear = -1\n", " self.rear += 1\n", " self.queArray[self.rear] = j\n", "\n", " def remove(self): # take item from front of queue\n", " temp = self.queArray[self.front]\n", " self.front += 1\n", " if(self.front == self.SIZE):\n", " self.front = 0\n", " return temp\n", "\n", " def isEmpty(self): # true if queue is empty\n", " return ( self.rear+1==self.front or (self.front+self.SIZE-1==self.rear) )\n", "\n", "class Vertex:\n", " def __init__(self,lab): # constructor\n", " self.label = lab\n", " self.wasVisited = 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(0)\n", " self.adjMat.append(l)\n", " self.theQueue = Queue()\n", "\n", " def addVertex(self,lab):\n", " self.vertexList.append( Vertex(lab))\n", " self.nVerts += 1\n", "\n", " def addEdge(self,start, end):\n", " self.adjMat[start][end] = 1\n", " self.adjMat[end][start] = 1\n", "\n", " def displayVertex(self,v):\n", " print self.vertexList[v].label ,\n", "\n", " def bfs(self): # breadth-first search\n", " # begin at vertex 0\n", " self.vertexList[0].wasVisited = True # mark it\n", " self.displayVertex(0) # display it\n", " self.theQueue.insert(0) # insert at tail\n", " while( not self.theQueue.isEmpty() ): # until queue empty,\n", " v1 = self.theQueue.remove() # remove vertex at head\n", " # until it has no unvisited neighbors\n", " while( self.getAdjUnvisitedVertex(v1) != -1 ):\n", " v2 = self.getAdjUnvisitedVertex(v1)\n", " self.vertexList[v2].wasVisited = True # mark it\n", " self.displayVertex(v2) # display it\n", " self.theQueue.insert(v2) # insert it\n", " for j in range(self.nVerts): # reset flags\n", " self.vertexList[j].wasVisited = False\n", "\n", " def getAdjUnvisitedVertex(self,v):\n", " for j in range(self.nVerts):\n", " if(self.adjMat[v][j]==1 and self.vertexList[j].wasVisited==False):\n", " return j\n", " return -1\n", "\n", "\n", "theGraph = Graph()\n", "theGraph.addVertex('A') # 0 (start for dfs)\n", "theGraph.addVertex('B') # 1\n", "theGraph.addVertex('C') # 2\n", "theGraph.addVertex('D') # 3\n", "theGraph.addVertex('E') # 4\n", "theGraph.addEdge(0,1)\n", "theGraph.addEdge(1,2)\n", "theGraph.addEdge(0,3)\n", "theGraph.addEdge(3,4)\n", "print 'Visits: ',\n", "theGraph.bfs() # breadth-first search" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Visits: A B D C E\n" ] } ], "prompt_number": 2 }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Example 13.3 Page no : 645" ] }, { "cell_type": "code", "collapsed": false, "input": [ " \n", "class StackX:\n", " def __init__(self):\n", " self.st = [] # make array\n", " self.top = -1\n", "\n", " def push(self,j): # put item on stack\n", " self.top += 1\n", " self.st.append(j)\n", "\n", " def pop(self): # take item off stack\n", " self.top -= 1\n", " return self.st.pop()\n", "\n", " def peek(self): # peek at top of stack\n", " return self.st[self.top]\n", " \n", " def isEmpty(self): # true if nothing on stack-\n", " return self.top == -1\n", "\n", "class Vertex:\n", " def __init__(self,lab): # constructor\n", " self.label = lab\n", " self.wasVisited = 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(0)\n", " self.adjMat.append(l)\n", " self.theStack = StackX()\n", "\n", " def addVertex(self,lab):\n", " self.vertexList.append( Vertex(lab))\n", " self.nVerts += 1\n", "\n", " def addEdge(self,start, end):\n", " self.adjMat[start][end] = 1\n", " self.adjMat[end][start] = 1\n", "\n", " def displayVertex(self,v):\n", " print self.vertexList[v].label ,\n", "\n", " def mst(self): # minimum spanning tree (depth first)\n", " # start at 0\n", " self.vertexList[0].wasVisited =True\n", " # mark it\n", " self.theStack.push(0)\n", " # push it\n", " while(not self.theStack.isEmpty() ):\n", " # until stack empty\n", " # get stack top\n", " currentVertex = self.theStack.peek()\n", " # get next unvisited neighbor \n", " v = self.getAdjUnvisitedVertex(currentVertex)\n", " if(v == -1):\n", " # if no more neighbors\n", " self.theStack.pop()\n", " else:\n", " # got a neighbor\n", " self.vertexList[v].wasVisited = True # mark it\n", " self.theStack.push(v)\n", " # push it\n", " # display edge\n", " self.displayVertex(currentVertex)\n", " # from currentV\n", " self.displayVertex(v)\n", " # to v\n", " print ' ',\n", " for j in range(self.nVerts):\n", " # reset flags\n", " self.vertexList[j].wasVisited = False\n", "\n", " def getAdjUnvisitedVertex(self, v):\n", " for j in range(self.nVerts):\n", " if(self.adjMat[v][j]==1 and self.vertexList[j].wasVisited==False):\n", " return j\n", " return -1\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') # 3Topological Sorting with Directed Graphs\n", "theGraph.addVertex('E') # 4\n", "theGraph.addEdge(0,1) \n", "theGraph.addEdge(0,2)\n", "theGraph.addEdge(0,3) \n", "theGraph.addEdge(0,4) \n", "theGraph.addEdge(1,2) \n", "theGraph.addEdge(1,3)\n", "theGraph.addEdge(1,4) \n", "theGraph.addEdge(2,3) \n", "theGraph.addEdge(2,4) \n", "theGraph.addEdge(3,4) \n", "print 'Minimum spanning tree: ',\n", "theGraph.mst() # minimum spanning tree" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "Minimum spanning tree: A B B C C D D E \n" ] } ], "prompt_number": 3 }, { "cell_type": "heading", "level": 3, "metadata": {}, "source": [ "Example 13.4 page No : 657" ] }, { "cell_type": "code", "collapsed": false, "input": [ " \n", "class Vertex:\n", " def __init__(self,lab): # constructor\n", " self.label = lab\n", " self.wasVisited = 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(0)\n", " self.adjMat.append(l)\n", "\n", " def addVertex(self,lab):\n", " self.vertexList.append( Vertex(lab))\n", " self.nVerts += 1\n", "\n", " def addEdge(self,start, end):\n", " self.adjMat[start][end] = 1\n", " self.adjMat[end][start] = 1\n", "\n", " def displayVertex(self,v):\n", " print self.vertexList[v].label ,\n", "\n", " def topo(self): # topological sort\n", " orig_nVerts = self.nVerts # remember how many verts\n", " while(self.nVerts > 0): # while vertices remain,\n", " # get a vertex with no successors, or -1\n", " currentVertex = self.noSuccessors()\n", " if(currentVertex == -1):\n", " # must be a cycleTopological Sorting with Directed Graphs\n", " print 'ERROR: Graph has cycles'\n", " return\n", "\n", " # insert vertex label in sorted array (start at end)\n", " self.sortedArray[nVerts-1] = self.vertexList[currentVertex].label\n", " self.deleteVertex(currentVertex)\n", " print 'Topologically sorted order: '\n", " for j in range(orig_nVerts):\n", " print sortedArray[j] ,\n", " print ''\n", "\n", " def noSuccessors(self): # returns vert with no successors\n", " # (or -1 if no such verts)\n", " isEdge = None\n", " for row in range(self.nVerts): # for each vertex,\n", " isEdge = False\n", " # check edges\n", " for col in range(self.nVerts):\n", " if( self.adjMat[row][col] > 0 ): # if edge to\n", " # another,\n", " isEdge = True\n", " break\n", " if( not isEdge ):\n", " # if no edges,\n", " return row\n", " return -1\n", "\n", " def deleteVertex(self,delVert):\n", " if(delVert != self.nVerts-1):\n", " # if not last vertex,\n", " # delete from vertexList\n", " for j in range(self.nVerts-1):\n", " self.vertexList[j] = self.vertexList[j+1]\n", " # delete row from adjMat\n", " for row in range(self.nVerts-1):\n", " self.moveRowUp(row, nVerts)\n", " # delete col from adjMat\n", " for col in range(self.nVerts-1):\n", " self.moveColLeft(col, nVerts-1)\n", " self.nVerts -= 1\n", "\n", " def moveRowUp(self,row,length):\n", " for col in range(length):\n", " self.adjMat[row][col] = self.adjMat[row+1][col]\n", "\n", " def moveColLeft(self,col, length):\n", " for row in range(self.length):\n", " self.adjMat[row][col] = self.adjMat[row][col+1]\n", "\n", "theGraph = Graph()\n", "theGraph.addVertex('A') # 0\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.addVertex('G') # 6\n", "theGraph.addVertex('H') # 7Connectivity in Directed Graphs\n", "theGraph.addEdge(0,3)\n", "theGraph.addEdge(0,4)\n", "theGraph.addEdge(1,4)\n", "theGraph.addEdge(2,5)\n", "theGraph.addEdge(3,6)\n", "theGraph.addEdge(4,6)\n", "theGraph.addEdge(5,7)\n", "theGraph.addEdge(6,7)\n", "theGraph.topo() # do the sort" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "ERROR: Graph has cycles\n" ] } ], "prompt_number": 4 }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [] } ], "metadata": {} } ] }