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