removing problem statements

1 files changed, 415 insertions, 15 deletions

diff --git a/Data_Structures_and_Algorithms_in_Java/ch13.ipynb b/Data_Structures_and_Algorithms_in_Java/ch13.ipynb
index cab6d6e8..ab8fea53 100644
--- a/Data_Structures_and_Algorithms_in_Java/ch13.ipynb
+++ b/Data_Structures_and_Algorithms_in_Java/ch13.ipynb
@@ -1,6 +1,7 @@
 {
  "metadata": {
-  "name": "ch13"
+  "name": "",
+  "signature": "sha256:e4ee94b1921cc19d6665af422d1e40ebb2336538caa9a0070a2828a133297159"
  },
  "nbformat": 3,
  "nbformat_minor": 0,
@@ -11,25 +12,116 @@
      "cell_type": "heading",
      "level": 1,
      "metadata": {},
-     "source": "Chapter 13 : Graphs"
+     "source": [
+      "Chapter 13 : Graphs"
+     ]
     },
     {
      "cell_type": "heading",
      "level": 3,
      "metadata": {},
-     "source": "Example 13.1  Page no: 631"
+     "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",
+     "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"
+       "text": [
+        "Visits:  A B C D E\n"
+       ]
       }
      ],
      "prompt_number": 1
@@ -38,19 +130,113 @@
      "cell_type": "heading",
      "level": 3,
      "metadata": {},
-     "source": "Example 13.2  Page no : 639"
+     "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",
+     "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"
+       "text": [
+        "Visits:  A B D C E\n"
+       ]
       }
      ],
      "prompt_number": 2
@@ -59,19 +245,126 @@
      "cell_type": "heading",
      "level": 3,
      "metadata": {},
-     "source": "Example 13.3 Page no : 645"
+     "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",
+     "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"
+       "text": [
+        "Minimum spanning tree:  A B   B C   C D   D E  \n"
+       ]
       }
      ],
      "prompt_number": 3
@@ -80,19 +373,126 @@
      "cell_type": "heading",
      "level": 3,
      "metadata": {},
-     "source": "Example 13.4  page No : 657"
+     "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",
+     "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"
+       "text": [
+        "ERROR: Graph has cycles\n"
+       ]
       }
      ],
      "prompt_number": 4
@@ -100,7 +500,7 @@
     {
      "cell_type": "code",
      "collapsed": false,
-     "input": "",
+     "input": [],
      "language": "python",
      "metadata": {},
      "outputs": []