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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
{
"metadata": {
"name": "ch13"
},
"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": "'''\nexample 13.1\ndemonstrates depth-first search\n'''\nclass 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\nclass Vertex:\n def __init__(self,lab): # constructor\n self.label = lab\n self.wasVisited = 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(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\ntheGraph = Graph()\ntheGraph.addVertex('A') # 0 (start for dfs)\ntheGraph.addVertex('B') # 1\ntheGraph.addVertex('C') # 2\ntheGraph.addVertex('D') # 3\ntheGraph.addVertex('E') # 4\ntheGraph.addEdge(0,1)\ntheGraph.addEdge(1,2)\ntheGraph.addEdge(0,3)\ntheGraph.addEdge(3,4)\nprint 'Visits: ',\ntheGraph.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": "'''\nExample 13.2\ndemonstrates breadth-first search\n'''\nclass 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\nclass Vertex:\n def __init__(self,lab): # constructor\n self.label = lab\n self.wasVisited = 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(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\ntheGraph = Graph()\ntheGraph.addVertex('A') # 0 (start for dfs)\ntheGraph.addVertex('B') # 1\ntheGraph.addVertex('C') # 2\ntheGraph.addVertex('D') # 3\ntheGraph.addVertex('E') # 4\ntheGraph.addEdge(0,1)\ntheGraph.addEdge(1,2)\ntheGraph.addEdge(0,3)\ntheGraph.addEdge(3,4)\nprint 'Visits: ',\ntheGraph.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": "'''\nexample 13.3\ndemonstrates minimum spanning tree\n'''\nclass 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\nclass Vertex:\n def __init__(self,lab): # constructor\n self.label = lab\n self.wasVisited = 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(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\ntheGraph = Graph()\ntheGraph.addVertex('A') # 0 (start for mst)\ntheGraph.addVertex('B') # 1\ntheGraph.addVertex('C') # 2\ntheGraph.addVertex('D') # 3Topological Sorting with Directed Graphs\ntheGraph.addVertex('E') # 4\ntheGraph.addEdge(0,1) \ntheGraph.addEdge(0,2)\ntheGraph.addEdge(0,3) \ntheGraph.addEdge(0,4) \ntheGraph.addEdge(1,2) \ntheGraph.addEdge(1,3)\ntheGraph.addEdge(1,4) \ntheGraph.addEdge(2,3) \ntheGraph.addEdge(2,4) \ntheGraph.addEdge(3,4) \nprint 'Minimum spanning tree: ',\ntheGraph.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": "'''\nExample 13.4\ndemonstrates topological sorting\n'''\nclass Vertex:\n def __init__(self,lab): # constructor\n self.label = lab\n self.wasVisited = 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(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\ntheGraph = Graph()\ntheGraph.addVertex('A') # 0\ntheGraph.addVertex('B') # 1\ntheGraph.addVertex('C') # 2\ntheGraph.addVertex('D') # 3\ntheGraph.addVertex('E') # 4\ntheGraph.addVertex('F') # 5\ntheGraph.addVertex('G') # 6\ntheGraph.addVertex('H') # 7Connectivity in Directed Graphs\ntheGraph.addEdge(0,3)\ntheGraph.addEdge(0,4)\ntheGraph.addEdge(1,4)\ntheGraph.addEdge(2,5)\ntheGraph.addEdge(3,6)\ntheGraph.addEdge(4,6)\ntheGraph.addEdge(5,7)\ntheGraph.addEdge(6,7)\ntheGraph.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": {}
}
]
}
|
