C1W4__8LINEAR-TIME_SELECTION_9GRAPHS_AND_THE_CONTRACTION_ALGORITHM.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# VIII. Linear Time Selection \n",
    "In this notebook we will look at two types of selection algorithms, the RSelect, or the randomized selection algorithm and a deterministic version called DSelect. But before we proceed the question is \"What is selection?\" A selection problem aims to find the $i^{th}$ smallest number for n given numbers. The simplest approach would be to sort the input array and then select the $i^{th}$ position number essentially doing the selection in $nlogn$ time. This however is not the optimum way as selection if an easier problem than sorting and thus we should achieve this in much less running time than sorting. To select a number from n given numbers, we will have to view all the numbers at the minimum and thus $O(n)$ is a reasonable lower bound and we know that sorting can be done in $O(nlogn)$ which is an upperbound for our problem.\n",
    "\n",
    "Can we do something to possibly perform the selection in $O(n)$ time? Let us implement the selection problem using the partition routine we used in quick sort."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "def swap(element1, element2):\n",
    "    temp = element1\n",
    "    element1 = element2\n",
    "    element2 = temp\n",
    "    return element1, element2\n",
    "\n",
    "def partition(array, l, r):\n",
    "    #Partitions the input array in place and returns the index of the pivot element\n",
    "    #in the partitioned array and the number of comparisons performed which is required for the analysis\n",
    "    #of the number of comparisons performed.\n",
    "    i = l + 1\n",
    "    for j in range(1, r):\n",
    "        if array[0] > array[j]:\n",
    "            if j != i:\n",
    "                array[i], array[j] = swap(array[i], array[j])   \n",
    "            i += 1\n",
    "    array[0], array[i-1] = swap(array[0], array[i-1]) \n",
    "    return array, i-1\n",
    "\n",
    "\n",
    "def choose_pivot(array):\n",
    "    randomidx = random.randint(0,len(array)-1)\n",
    "    array[0], array[randomidx] = swap(array[0], array[randomidx])\n",
    "    return array\n",
    "\n",
    "def Randomized_Selection(array , order_statistic, init_ncomparisons = 0 ):\n",
    "    global ncomparisons\n",
    "    if init_ncomparisons == 0:\n",
    "        ncomparisons = 0\n",
    "    n = len(array)\n",
    "    if n == 1:\n",
    "        return array[0], ncomparisons\n",
    "    if n > 1:\n",
    "        array = choose_pivot(array)   # Randomized algorithm: choosing pivot\n",
    "        array, pvtidx = partition(array, 0, n)\n",
    "        ncomparisons += n-1\n",
    "        if pvtidx == order_statistic - 1:\n",
    "            return array[pvtidx], ncomparisons\n",
    "        elif pvtidx > order_statistic - 1:\n",
    "            return Randomized_Selection(array[:pvtidx], order_statistic, init_ncomparisons = 1)\n",
    "        if pvtidx < order_statistic - 1:\n",
    "            return Randomized_Selection(array[pvtidx+1:], order_statistic - pvtidx - 1, init_ncomparisons = 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Randomized_Selection & Number of comparisons made using randomized algorithm:\n",
      "(2, 9)\n",
      "1st Order stat is (1, 12)\n",
      "2nd Order stat is (2, 12)\n",
      "3rd Order stat is (3, 11)\n",
      "4th Order stat is (4, 7)\n",
      "5th Order stat is (5, 14)\n",
      "6th Order stat is (6, 16)\n",
      "7th Order stat is (7, 7)\n",
      "8th Order stat is (8, 7)\n"
     ]
    }
   ],
   "source": [
    "print(\"Randomized_Selection & Number of comparisons made using randomized algorithm:\")\n",
    "print(Randomized_Selection([3, 2, 1, 5, 0, 7, 8], 3))\n",
    "print('1st Order stat is {}'.format(Randomized_Selection([3, 8, 2, 5, 1, 4, 7, 6], 1)))\n",
    "print('2nd Order stat is {}'.format(Randomized_Selection([3, 8, 2, 5, 1, 4, 7, 6], 2)))\n",
    "print('3rd Order stat is {}'.format(Randomized_Selection([3, 8, 2, 5, 1, 4, 7, 6], 3)))\n",
    "print('4th Order stat is {}'.format(Randomized_Selection([3, 8, 2, 5, 1, 4, 7, 6], 4)))\n",
    "print('5th Order stat is {}'.format(Randomized_Selection([3, 8, 2, 5, 1, 4, 7, 6], 5)))\n",
    "print('6th Order stat is {}'.format(Randomized_Selection([3, 8, 2, 5, 1, 4, 7, 6], 6)))\n",
    "print('7th Order stat is {}'.format(Randomized_Selection([3, 8, 2, 5, 1, 4, 7, 6], 7)))\n",
    "print('8th Order stat is {}'.format(Randomized_Selection([3, 8, 2, 5, 1, 4, 7, 6], 8)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will test the implementation with some of the test data given [here](http://algorithmsilluminated.org/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Median and Number of comparisons  using Randomized Selection\n",
      "5th Order statistic of the content expected to be 5469, got : (5469, 29)\n",
      "50th Order statistic of the content expected to be 4715, got: (4715, 153)\n"
     ]
    }
   ],
   "source": [
    "import urllib3\n",
    "http = urllib3.PoolManager()\n",
    "\n",
    "def test_case(url):\n",
    "    # Test case\n",
    "    r1 = http.request('GET', url)\n",
    "    IntegerArrayString = r1.data.split('\\r\\n')\n",
    "    del IntegerArrayString[-1]\n",
    "    IntegerArray = [int(i) for i in IntegerArrayString]\n",
    "    return IntegerArray\n",
    "\n",
    "print(\"Median and Number of comparisons  using Randomized Selection\")\n",
    "print(\"5th Order statistic of the content expected to be 5469, got : {}\".format(Randomized_Selection(test_case(\"http://algorithmsilluminated.org/datasets/problem6.5test1.txt\"), 5)))\n",
    "print(\"50th Order statistic of the content expected to be 4715, got: {}\".format(Randomized_Selection(test_case(\"http://algorithmsilluminated.org/datasets/problem6.5test2.txt\"), 50)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From above tests, the randomized implementation works in place with constant extra memory and works on a similar way quick sort does. The only difference is that after partition we either recurse on the left or the right side of the array unlike sorting where we recurse on both partitions around pivot. We will prove that the above algorithm runs in linear time.\n",
    "\n",
    "***\n",
    "\n",
    "**Intutition**\n",
    "\n",
    "The partition sub routine does exactly what it does in case of quick sort. Once we choose the partition routine, we know in linear time, what position the pivot element will end up in after the recursve calls. Once we know that value, we can then recurse on the left or the right split after the pivot. In the best case suppose we end up picking the median of the input array as pivot, in which case the array will be split in exactly halves. Since we always do linear work outside the recursive calls, we can express our recurrance as follows $$T(n)\\:=\\:T(\\frac{n}{2}) + O(n) $$\n",
    "\n",
    "By master method, a = 1, b = 2 and d = 1, we have $a < b^d$ which is case 2 of the master method. The running time is in this case dominated by the work done outside recursive calls giving us the time as $O(n^d)$ = $O(n)$ in this case. This shows us that if we get an approximate median and split the array into two approximately equal pieces, we can expect the selection problem to run in linear time. Let us see how exactly we get linear time on an average for a given array using the following proof.\n",
    "\n",
    "***\n",
    "\n",
    "**Proof**\n",
    "\n",
    "We will track the progress of our selection problem in phases. we will call the problem is in phase j if it is operating on an array of length $(\\frac{3}{4})^{j + 1}$ to $(\\frac{3}{4})^{j}$. For example, it will be in phase 0, if the size of the array is between 0.75n to n, phase 1 of the size array is 0.56n to 0.75n and so on. The maximum value of phase j when the value of the input size will be 1 should be $log_{4/3}n$.\n",
    "\n",
    "We will now define a random variable $X_j$ which gives is the number of times the selection process made recursive calls in phase j. The minimum value of this variable is 0.\n",
    "\n",
    "The maximum size of the array in phase j is $(\\frac{3}{4})^j$ and thus the work done in this phase is no more than $c\\cdot (\\frac{3}{4})^j \\cdot n$. Thus\n",
    "\n",
    "$$Running\\:time\\:of\\:RSelect\\:is\\:\\leq \\sum_{j \\geq 0} c\\cdot (\\frac{3}{4})^j\\cdot n X_j$$\n",
    "By linearity of expectations\n",
    "\n",
    "$$E[Running\\:time\\:of\\:RSelect\\:is]\\:\\leq cn \\sum_{j \\geq 0} (\\frac{3}{4})^jE[X_j]$$\n",
    "How do we find $E[X_j]$?\n",
    "\n",
    "Whenever we choose an approximate median as pivot, a number that gives us 25-75% split of the input array, we are guaranteed to procees to next phase. If only when the split produces an array giving is greater than 75% of elements remaining after partition, we stay in the phase j for another recursive call. Thus we can conclude, picking an approximate median is guaranteed to take us to next phase.\n",
    "\n",
    "Secondly, picking an approximate median has a probability of 50%. Suppose we have n numbers say, 1 to 100, then by picking anything from 26 to 75 is an approximate median which makes up 50% of the input numbers.\n",
    "\n",
    "The random variable $X_j$ is similar to a coin flipping problem. Suppose N is a random variable which counts the number of times we need to flip the coin to get heads (or tails).\n",
    "\n",
    "The random variable $X_j$ and $N$ are similar but the $E[X_j] \\leq E[N]$\n",
    "\n",
    "The coin flopping experiment has to flip the coin atleast once to get heads. The value of X_j can be 0 if we completely skip the phase.\n",
    "We have maximum probability of 0.5 of not going out of phase j and staying in the same phase. This is similar to 0.5 probability we get tails and we we need to flip the coin another time.\n",
    "The expected value of the coin flip experiment is\n",
    "\n",
    "$E(N)\\: = \\: 1\\: +\\: \\frac{1}{2}E(N)$\n",
    "\n",
    "The only value of E(N) that satisfies the above equation is 2. The equation is explained as follows. The value 1 is for that minimum one flip needed and the value 0.5 is the probability that we get tails. We can thus say that $E(X_j) \\leq 2$\n",
    "\n",
    "Geometric sequence $1\\: + \\: r^2\\: + \\: r^3 \\dots r^k = \\frac{1 - r^{k + 1}}{1 - r}$\n",
    "\n",
    "This $\\sum_{j \\geq 0} (\\frac{3}{4})^j\\: \\leq\\: \\frac{1}{1 - \\frac{3}{4}} = 4$\n",
    "\n",
    "Therefore,  $E[Running\\:time\\:of\\:RSelect\\:is]\\:\\leq cn \\sum_{j \\geq 0} (\\frac{3}{4})^jE[X_j] = 4\\cdot 2cn = 8cn$\n",
    "\n",
    "Hence, the running time of randomized select algorithm on an average runs in $O(n)$\n",
    "\n",
    "***\n",
    "\n",
    "Next we will look at an algorithm which does the selection in linear time and is deterministic. Its called DSelect in our notebook\n",
    "\n",
    "We will analyze the running time of the algorithm. For Pseudo code of the algorithm refer page 169 of the book.\n",
    "\n",
    "The first time consuming activity of DSelect is to find the median of medians. For this purpose we find the break the input array in batches of 5 and find medians of each of these splits of 5. This way we find the a total of $\\frac{n}{5}$ medians. We recursively keep finding the medians of medians till we hit the base case where we only one element in the input array. To illustrate this, consider we have the following input array\n",
    "\n",
    "11, 6, 10, 2, 15, 8, 1, 7, 14, 3, 9, 12, 4, 5, 13\n",
    "\n",
    "We break find medians of the splits of 5 of the array giving us 10 (median of 11, 6, 10, 2, 15), 7 (median of 8, 1, 7, 14, 3, 9) and 9 median of (9, 12, 4, 5, 13). Median of these three medians is 9 and thus this is the pivot of our choice.\n",
    "\n",
    "Finding median of 5 numbers is a constant time activity and let that constant be c. We operate on an array of $\\frac{n}{5}$ to find medians. Thus the time taken to find the medians of medians is $\\frac{n}{5}\\cdot c$ = $O(n)$\n",
    "\n",
    "Thus find median of medians is a Linear time operation.\n",
    "\n",
    "The median of medians is found by calling DSelect recursively on an array of size $\\frac{n}{5}$ and then the partition, which is done in linear time, determines the statistic of the pivot element (the median of medians). Based on the $i{th}$ order statistic we are interested in, we either recurse on the portion of the input to the left of the pivot or the one on the right. We therefore have two sub problems\n",
    "\n",
    "The Dselect called on $\\frac{n}{5}$ array to find median of medians\n",
    "The second recursive call on DSelect on the reduced array.\n",
    "Outside the recursive call, the DSelect does linear work to find the medians and to partition the numbers around pivot. Therefore the recurrence is\n",
    "\n",
    "$T(n)\\: \\leq \\: T(\\frac{n}{5})\\:+\\:T(?)\\:+ O(n)\\:$\n",
    "\n",
    "Right now we are interested in deterministically find $T(?)$\n",
    "\n",
    "For this purpose we introduce the 30-70 Lemma (which we will prove later). This Lemma states that the median of medians is no less than at least 60% of elements in at least 50% of the groups of 5 and no greater than at least 60% of at least 50% of groups of 5. The value 60% of 50% is 0.6 * 0.5 = 30%. This sounds confusing, but it essentially says that there are at least 30% numbers in the input array those are smaller than the partition element (median of medians), and there are at least 30% of numbers in the input array those are larger than the partition element. The result of this is, that under no circumstance we will get the split around partition greater than 70% of original input. Therefore, $T(?) \\leq T(\\frac{7n}{10})$ hence the running time of DSelect is\n",
    "\n",
    "$T(n)\\: \\leq \\: T(\\frac{n}{5})\\:+\\:T(\\frac{7n}{10})\\:+ O(n)\\:$\n",
    "\n",
    "We will prove the algorithm runs in linear time using induction. We assume that for k < n, $T(k) \\leq lk$\n",
    "\n",
    "We will assign l to some arbritrary constant independent of n, for our derivation we will assign l = 10c. This is a legitimate assumption as for the base case we know T(1) = 1. Since $c\\geq 1$, $T(1) \\leq 10c$\n",
    "\n",
    "Therefore for $n\\geq 2$\n",
    "\n",
    "$T(n)\\: \\leq \\: l\\frac{n}{5}\\:+\\:l\\frac{7n}{10}\\:+ cn\\: = \\frac{9ln}{10}\\:+ cn\\: = 9cn + cn = 10cn = l\\cdot n$\n",
    "\n",
    "This proves the indictive step that the $T(n)\\: \\leq l\\cdot n\\:=\\:O(n)$\n",
    "\n",
    "We are still to prove the 30-70 Lemma. The simple explanation is as follows.\n",
    "\n",
    "Consider k number arrays each of length 5. For simplicity lets assume k is 5. Thus there are two medians smaller and two medians larger than the median or medians (mom). We call them $s_1$, $s_2$ and $l_1$, $l_2$ respectively.\n",
    "We can therefore conclusively say that no more than 3 of 5, which is 60% of numbers including the medians in $s_1$ and $s_2$ and the minimum 2 numbers in the same batch of 5 as mom are smaller than mom.\n",
    "Similarly, we can therefore conclusively say that no more than 3 of 5, which is 60% of numbers including the medians in $l_1$ and $l_2$ and the maximum 2 numbers in the same batch of 5 as mom are larger than mom.\n",
    "Thus for this example where k = 5 (n = 25). Minimum 8 numbers are smaller than mom and minimum 8 numbers are larger than mom. The next recursive call will not have the pivot and either of these 8 numbers which makes it 9 numbers minimum. This means the maximum size of the array we can have is 16 which is 64% of input array.\n",
    "This generalization holds true for any large value of k and we are guaranteed to not have more than 70% of original input passed to the subsequent recursive call.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 139,
   "metadata": {},
   "outputs": [],
   "source": [
    "def swap(element1, element2):\n",
    "    temp = element1\n",
    "    element1 = element2\n",
    "    element2 = temp\n",
    "    return element1, element2\n",
    "\n",
    "def partition(array, l, r):\n",
    "    #Partitions the input array in place and returns the index of the pivot element\n",
    "    #in the partitioned array and the number of comparisons performed which is required for the analysis\n",
    "    #of the number of comparisons performed.\n",
    "    i = l + 1\n",
    "    for j in range(1, r):\n",
    "        if array[0] > array[j]:\n",
    "            if j != i:\n",
    "                array[i], array[j] = swap(array[i], array[j])   \n",
    "            i += 1\n",
    "    array[0], array[i-1] = swap(array[0], array[i-1]) \n",
    "    return array, i-1\n",
    "\n",
    "def quicksort_naivepivot(array , init_ncomparisons = 0):\n",
    "    global ncomparisons\n",
    "    if init_ncomparisons == 0:\n",
    "        ncomparisons = 0\n",
    "    n = len(array)\n",
    "    if n == 1:\n",
    "        #print(array)\n",
    "        return array, ncomparisons\n",
    "    if n > 1:\n",
    "        #print(array)\n",
    "        pivot = array[0]   # 1st element is pivot\n",
    "        array, pvtidx = partition(array, 0, n)\n",
    "        ncomparisons += n-1\n",
    "        #print(\"partitioned : {}\".format(array))\n",
    "        if pvtidx != 0:\n",
    "            array[:pvtidx], _ = quicksort_naivepivot(array[:pvtidx], init_ncomparisons = 1)\n",
    "        if pvtidx != n-1:\n",
    "            array[pvtidx+1:], _ = quicksort_naivepivot(array[pvtidx+1:], init_ncomparisons = 1)\n",
    "    return array, ncomparisons\n",
    "\n",
    "def choose_pivot_median_of_medians(array):\n",
    "    #print(\"m&m: {}\".format(array))\n",
    "    group5 = len(array) // 5 if len(array) % 5 == 0 else (len(array) // 5)+1\n",
    "    idx = 0\n",
    "    idxC = 0\n",
    "    C = [None]*group5\n",
    "    arraysorted = [None]*len(array)\n",
    "    for g in range(group5-1):\n",
    "        #print(array[idx:idx+5])\n",
    "        arraysorted[idx:idx+5] = quicksort_naivepivot(array[idx:idx+5])[0]\n",
    "        C[idxC] = arraysorted[idx:idx+5][2]\n",
    "        #print(C[idxC])\n",
    "        idx += 5\n",
    "        idxC += 1\n",
    "    if len(array[idx:]) != 1:\n",
    "        lastmid = len(array[idx:]) // 2 \n",
    "        arraysorted[idx:] =  quicksort_naivepivot(array[idx:])[0]\n",
    "        C[idxC] = arraysorted[idx:][lastmid]\n",
    "    else:\n",
    "        arraysorted[idx] = array[idx]\n",
    "        C[idxC] = array[idx]\n",
    "    #print(C)\n",
    "    if len(arraysorted) == 1:\n",
    "        #print(\"m&m basecase: {}\".format(arraysorted))\n",
    "        return arraysorted\n",
    "    else:\n",
    "        medianidx = Deterministic_Selection(C, (group5 // 2)+1)[1]\n",
    "        #print(\"median idx: {}\".format(medianidx))\n",
    "        arraysorted[0], arraysorted[medianidx] = swap(arraysorted[0], arraysorted[medianidx])\n",
    "        #print(\"median first: {}\".format(arraysorted))\n",
    "        return arraysorted\n",
    "\n",
    "def Deterministic_Selection(array , order_statistic, globalidx = 0, init_ncomparisons = 0 ):\n",
    "    global ncomparisons\n",
    "    if init_ncomparisons == 0:\n",
    "        ncomparisons = 0\n",
    "    n = len(array)\n",
    "    if n == 1:\n",
    "        #print(\"DS basecase: {}\".format(array))\n",
    "        return array[0], globalidx, ncomparisons\n",
    "    if n > 1:\n",
    "        #print(\"DS array: {}\".format(array))\n",
    "        array = choose_pivot_median_of_medians(array)   # Randomized algorithm: choosing pivot\n",
    "        #print(\"DS array after: {}\".format(array))\n",
    "        array, pvtidx = partition(array, 0, n)\n",
    "        ncomparisons += n-1\n",
    "        if pvtidx == order_statistic - 1:\n",
    "            return array[pvtidx], pvtidx+globalidx, ncomparisons\n",
    "        elif pvtidx > order_statistic - 1:\n",
    "            return Deterministic_Selection(array[:pvtidx], order_statistic, globalidx = pvtidx+1, init_ncomparisons = 1)\n",
    "        if pvtidx < order_statistic - 1:\n",
    "            return Deterministic_Selection(array[pvtidx+1:], order_statistic - pvtidx - 1, init_ncomparisons = 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "('2st Order stat is', 6)\n",
      "('1st Order stat is', 1)\n",
      "('2nd Order stat is', 2)\n",
      "('3rd Order stat is', 3)\n",
      "('4th Order stat is', 4)\n",
      "('5th Order stat is', 5)\n",
      "('6th Order stat is', 6)\n",
      "('7th Order stat is', 7)\n",
      "('8th Order stat is', 8)\n",
      "('11th Order stat is', 12)\n"
     ]
    }
   ],
   "source": [
    "print('2st Order stat is', Deterministic_Selection([3, 6], 2)[0])\n",
    "print('1st Order stat is', Deterministic_Selection([3, 8, 2, 5, 1, 4, 7, 6], 1)[0])\n",
    "print('2nd Order stat is', Deterministic_Selection([3, 8, 2, 5, 1, 4, 7, 6], 2)[0])\n",
    "print('3rd Order stat is', Deterministic_Selection([3, 8, 2, 5, 1, 4, 7, 6], 3)[0])\n",
    "print('4th Order stat is', Deterministic_Selection([3, 8, 2, 5, 1, 4, 7, 6], 4)[0])\n",
    "print('5th Order stat is', Deterministic_Selection([3, 8, 2, 5, 1, 4, 7, 6], 5)[0])\n",
    "print('6th Order stat is', Deterministic_Selection([3, 8, 2, 5, 1, 4, 7, 6], 6)[0])\n",
    "print('7th Order stat is', Deterministic_Selection([3, 8, 2, 5, 1, 4, 7, 6], 7)[0])\n",
    "print('8th Order stat is', Deterministic_Selection([3, 8, 2, 5, 1, 4, 7, 6], 8)[0])\n",
    "print('11th Order stat is', Deterministic_Selection([56, 765, 34,242,3, 8, 542, 789, 2, 5,321, 1, 4, 7, 87, 90, 6, 9, 77, 55, 18,10,66, 79,15,131,12, 134], 11)[0])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Median using Deterministic Selection: \n",
      "5th Order statistic of the content expected to be 5469, got : 5469\n",
      "50th Order statistic of the content expected to be 4715, got: 4715\n"
     ]
    }
   ],
   "source": [
    "print(\"Median using Deterministic Selection: \")\n",
    "print(\"5th Order statistic of the content expected to be 5469, got : {}\".format(Deterministic_Selection(test_case(\"http://algorithmsilluminated.org/datasets/problem6.5test1.txt\"), 5)[0]))\n",
    "print(\"50th Order statistic of the content expected to be 4715, got: {}\".format(Deterministic_Selection(test_case(\"http://algorithmsilluminated.org/datasets/problem6.5test2.txt\"), 50)[0]))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#  IX. GRAPHS AND THE CONTRACTION ALGORITHM\n",
    "Graphs are relationships between pair of objects. The objects are called Vertices (singulat: vertex) or nodes and the relationship between them is represented by the edge. The graph (G) is represented using the vertices (V) and the edges (E).\n",
    "\n",
    "***\n",
    "\n",
    "Two flavors of graph are directed and undirected.\n",
    "\n",
    "- In an undirected graph, the edges are formed by the undirected edges {v, w}. This mearly means that the vertices have a connection between them and there is no direction necessary for the edge. Thus the edge (v, w) is same as edge (w, v). Friendship in social networking site like Facebook is an example of undirected graph. If Tom is friend of Jerry then Jerry is also a friend of Tom.\n",
    "- Directed graphs on other hand have edges directed from node v to w. In this case since the edge originates from v, it is the tail and since it goes to w, w is the head of the edge. The edges (v, w) is not same as (w, v) abd infact one of them may not even exist. Twitter followers can be represented by directed edges. If Tom follows Jerry on twitter, Jerry may or may not follow Tom. Twitter following is not mutual unlike friends on Facebook.\n",
    "\n",
    "Some examples of graphs are\n",
    "- Road networks: Though we may represent this using undirected graphs for simplicity its more apt to represent road networks using directed graphs. Roads generally are two way in which case we will have both edges (v, w) and (w, v) but that may not always be true in cases we have one way streets.\n",
    "- World wide web: This is an example of directed graph where the page containing hyperlink to another page is the tail of the directed graph and the page it references being the head.\n",
    "- Precedence constraints: We use this to form dependency trees where to preform a task A, we can find what are the prerequisites.\n",
    "\n",
    "**Notation of a graph**<br>\n",
    "A graph G is represented using its Vertices and Edges as\n",
    "\n",
    "G = (V, E)\n",
    "\n",
    "where\n",
    "\n",
    "n = $\\vert V \\vert$, number of vertices and\n",
    "\n",
    "m = $\\vert E \\vert$, number of edges\n",
    "\n",
    "**Quiz 7.1**<br>\n",
    "\n",
    "Lets consider an undirected graph G with n vertices with no parallel edges (no two vertices have two edges connecting them). What are the minimum and maximum number of edges.\n",
    "\n",
    "To start with minimum number of edges, a graph will stay as one graph if we can traverse from one vertex to another. Its not too difficult to see that we will need n - 1. That is to connect from a vertex $v_1$, we will have n - 1 edges to remaining n - 1 vertices $n_2 .. n_n$. Kind of like a hub and spoke where one verted is the hub and other vertices form the end of the spoke.\n",
    "\n",
    "Now for maximum edges, we will draw from first vertex, n-1 edges to remaining edges. Then from second vertex have to draw n - 2 edges to remaining vertices. Why n - 2? Its because there already is an edge from first vertex to the second and we dont have parallel edges. Continuing this way, we will have (n - 1) + (n - 1) + (n - 3) + ... + 1 + 0 edges which is same as $\\frac{n(n-1)}{2}$\n",
    "\n",
    "***\n",
    "\n",
    "**Sparse and Dense graphs**<br>\n",
    "We see above that the number of vertices m = $\\Omega{(n)}$ and m = $\\theta{(n^2)}$. This the number of edges range from linear to quadratic. Though there is no strict cutoff for considering a graph sparse or dense, we can call a graph sparse if the number of edges is close to linear or dense if it is close to quadratic.\n",
    "\n",
    "Thus something like $\\theta{(nlogn)}$ is considered sparse whare as $\\theta{(\\frac{n^2}{log n})}$ is dense. Subquadratic like $n^{1.5}$ is either sparse or dense depending on the application\n",
    "\n",
    "**Graph Representation**<br>\n",
    "We will look at a couple of ways to represent graphs\n",
    "\n",
    "***\n",
    "\n",
    "**Adjacency List**<br>\n",
    "This is form of representation where we store the vertices in a one list and one list will store the list of edges. Each edge will have a two pointers to the vertex connecting the two vertices.\n",
    "\n",
    "For directed graphs, we will store two lists for each vertex, one list for incoming and one list for outgoing edges.\n",
    "\n",
    "For all quiz and test your understanding questions, refer to the book as i dont want to type out the question text here.\n",
    "\n",
    "**Quiz 7.2**<br>\n",
    "\n",
    "\n",
    "We can see above, we have two lists one has a size same as the number of vertices(n) and one has size same as number of edges(m). Thus the adjacency list will have a space requirement of $O(m + n)$\n",
    "\n",
    "***\n",
    "\n",
    "**Adjacency Matrix**<br>\n",
    "Consider a graph G = (V, E). We have n vertices and m edges. Each of the m edges will have both their endpoints as two vertices from n possible vertices.\n",
    "\n",
    "$\n",
    "A_{ij} = \n",
    "\\begin{cases}\n",
    "1 \\text{ if edge (i,j) belongs to G}\\\\\n",
    "0 \\text{ otherwise}\n",
    "\\end{cases}\n",
    "$\n",
    "\n",
    "The adjacency matrix for the graph with following edges\n",
    "\n",
    "$\n",
    "1 \\leftrightarrow 2 \\\\\n",
    "2 \\leftrightarrow 3 \\\\\n",
    "2 \\leftrightarrow 4 \\\\\n",
    "3 \\leftrightarrow 4 \\\\\n",
    "$\n",
    "\n",
    "becomes\n",
    "\n",
    "$\n",
    "\\begin{bmatrix}\n",
    "0 & 1 & 0 & 0\\\\\n",
    "1 & 0 & 1 & 1\\\\\n",
    "0 & 1 & 0 & 1\\\\\n",
    "0 & 1 & 1 & 0\\\\\n",
    "\\end{bmatrix}\n",
    "$\n",
    "\n",
    "The rows represents one end of the edge and other end is represented as the column. Notice how the matrix is symmetric across the diagonal in case of undirected graph.\n",
    "\n",
    "The adjacency matrix can also easily be used for directed graphs.\n",
    "\n",
    "***\n",
    "\n",
    "**Quiz 7.3**<br>\n",
    "\n",
    "The adjacency matrix will require a matrix of size $n^2$ to store the edges and this the space requirement for the matrix is $O(n^2)$\n",
    "\n",
    "***\n",
    "\n",
    "Generally, if the graph is dense or number of vertices is not huge (for example the pages on the web where one page is one vertex), we may choose Adjacency Matrix. However, for normal graph traversal, if we were to find from a verted all adjacent vertex, Adjacency list is better as for matrix the operation will be of order $O(n)$ which will involve going through the entire row of 0s and 1s to find all vertices adjacent/connect to the current vertex. In adjacency list however, getting the adjacent vertices of a vertex is a constant time operation. Also for sparse graphs Adjacency List is the way to go.\n",
    "\n",
    "We will also build an Adjacency List implementation in Python which we will use in other notebooks.\n",
    "\n",
    "***\n",
    "\n",
    "**Test Your Understanding**<br>\n",
    "\n",
    "***\n",
    "\n",
    "**Problem 7.1**<br>\n",
    "\n",
    "- At least one Vertex of G has at most degree 10.\n",
    "    - For a Graph with 10000+ vertices, even if all vertices have a degree of 10 (which is a stronger statement than saying at least one vertex has degree 10 ). The number of edges is a small constant (< 10) times the number of vertices and thus graph is still sparse.\n",
    "- Every vertex of G has at most 10 degree.\n",
    "    - Similar to above, saying all vertices have a degree 10 is much stronger assumption and the graph is still sparse in this case.\n",
    "- At least one vertex of G has degree n - 1\n",
    "    - This can either be sparse or dense. At the very minimum, only one vertex connects to all other n - 1 vertices and other n - 1 vertices have degree 1 (connecting to that vertex with degree n - 1). This makes the graph sparse (with minimum number of edges to form the graph). However, the important fact here is it says At least which means all vertices can have degree n - 1 in the extreme case which makes it as dense as it can, connecting each vertex to all other vertices.\n",
    "- Every verted has degree n- 1\n",
    "    - This one is easy, this is a dense graph. Explanation same as the explanation for the worst case in above scenario\n",
    "    \n",
    "***\n",
    "    \n",
    "**Problem 7.2**<br>\n",
    "\n",
    "For a graph stored as Adjacency Matrix, the complexity to find adjacent edges is of order of n (number of vertices). To see why, consider the matrix which has size $n \\times n$. When we are given a vertex v, we will slice a row corresponding to vertex v from this Matrix. This row (vector) of 0s and 1s will be of size n and the operation to find adjacent vertices will require us to iterate though it to find all entries with value 1. Thus the complexity of the operation to find adjacent vertices is $O(n)$\n",
    "\n",
    "***\n",
    "\n",
    "**Problem 7.3**<br>\n",
    "\n",
    "If a directed Graph stores only outgoing edges (the edge where the vertex is the tail of the edge) with each vertex, then to find all incoming vertices, we need to find the vertex v in the outgoing edges of other n - 1 vertices. The choice of data structure here is very important for storing the outgoing edges. If the set, like a Hash Set is used, we can expect the contains operation for the vertex in each set to have a constant complexity ($O(1)$). Combining both, the iteration though all n - 1 vertices to search for the vertex in their outgoing edges and the constant time operation to check the existence of the vertex in each of the outgoing edges of a vertex, we can expect the overall operation to have a complexity $O(n)$\n",
    "\n",
    "***\n",
    "\n",
    "We will now look at a simple Adjacency List implementation in Python which we will use for storing the graph even om subsequent chapters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from copy import deepcopy\n",
    "from itertools import combinations\n",
    "\n",
    "class Graph_UndirectedAdjList:\n",
    "    def __init__(self):\n",
    "        self._vertices = {}\n",
    "        self._edges = []\n",
    "        \n",
    "    def addEdge(self, v1, v2):\n",
    "        #Adds edge between two edges v1 an v2\n",
    "        if not [v1, v2] in self._edges and  not [v2, v1] in self._edges:\n",
    "            self._edges.append([v1, v2])\n",
    "            if v1 in self._vertices:\n",
    "                self._vertices[v1].append(v2)\n",
    "            else:\n",
    "                self._vertices[v1] = [v2]  #adjacent vertex\n",
    "            if v2 in self._vertices:\n",
    "                self._vertices[v2].append(v1)\n",
    "            else:\n",
    "                self._vertices[v2] = [v1]  #adjacent vertex\n",
    "            \n",
    "    def adjacentEdges(self, vertex):\n",
    "        return self._vertices[vertex] if vertex in self._vertices else None\n",
    "    \n",
    "    def vertices(self):\n",
    "        return self._vertices.keys()\n",
    "    \n",
    "    def edges(self):\n",
    "        return self._edges\n",
    "    \n",
    "    def addMultipleEdges(self, vertex, adjacentvertices):\n",
    "        for a_vertices in adjacentvertices:\n",
    "            self.addEdge(vertex, a_vertices)\n",
    "        \n",
    "    def contractEdge(self, edge):\n",
    "        # remove edge and future self-loop if any\n",
    "        idx = 0\n",
    "        for _ in range(len(self._edges)):\n",
    "            #print(self._edges)\n",
    "            if self._edges[idx][0] == edge[0]  and  self._edges[idx][1] == edge[1] :\n",
    "                self._edges.remove(self._edges[idx])\n",
    "                idx -= 1\n",
    "            elif self._edges[idx][0] == edge[1]  and  self._edges[idx][1] == edge[0] :\n",
    "                self._edges.remove(self._edges[idx])\n",
    "                idx -= 1\n",
    "            idx +=1             \n",
    "        # change all vertices of edges to contracted vertex\n",
    "        for i in range(len(self._edges)):\n",
    "            for j in range(len(self._edges[i])):\n",
    "                for k in range(len(edge)):\n",
    "                    #print(\"compared to uc: {}  replace node uc: {}\".format(edge[k], self._edges[i][j]))\n",
    "                    #print(\"i: {}  j: {}  k: {}\".format(i,j,k))\n",
    "                    if self._edges[i][j] == edge[k]:\n",
    "                        if isinstance(edge[0], int) and isinstance(edge[1], int):\n",
    "                            self._edges[i][j] = [edge[0], edge[1]]\n",
    "                            #print(\"Comp int-int: {}\".format([edge[0], edge[1]]))\n",
    "                        elif isinstance(edge[0], list) and  isinstance(edge[1], list) :\n",
    "                            self._edges[i][j] = list(edge[0]) + list(edge[1])\n",
    "                            #print(\"Comp list-list: {}\".format(list(edge[0]) + list(edge[1])))\n",
    "                        elif isinstance(edge[0], list) and not isinstance(edge[1], list) :\n",
    "                            newedge0 = deepcopy(edge[0])\n",
    "                            newedge1 = deepcopy(edge[1])\n",
    "                            newedge0.append(newedge1)\n",
    "                            self._edges[i][j] = newedge0\n",
    "                            #print(\"Comp list-int: {}\".format(newedge0))\n",
    "                        elif isinstance(edge[1], list) and not isinstance(edge[0], list):\n",
    "                            newedge0 = deepcopy(edge[0])\n",
    "                            newedge1 = deepcopy(edge[1])\n",
    "                            newedge1.append(newedge0)\n",
    "                            self._edges[i][j] = newedge1\n",
    "                            #print(\"Comp list-int: {}\".format(newedge1))\n",
    "        # contract vertices\n",
    "        for i in self._vertices.keys():\n",
    "            #print(\"i: {}\".format(i))\n",
    "            newedge0 = edge[0]\n",
    "            newedge1 = edge[1]\n",
    "            e0 = edge[0]\n",
    "            e1 = edge[1]\n",
    "            newval0 = []\n",
    "            newval1 = []\n",
    "            if isinstance(i, tuple):\n",
    "                if isinstance(edge[0], int):\n",
    "                    e0 = (edge[0], ) \n",
    "                if isinstance(edge[1], int):\n",
    "                    e1 = (edge[1], )\n",
    "                newedge0 = tuple(e0)\n",
    "                newedge1 = tuple(e1)\n",
    "            #print(\"newedge0 : {}  newedge1: {}\".format(newedge0, newedge1))\n",
    "            if i == newedge0:\n",
    "                newval0 = self._vertices[i]\n",
    "                #print(\"newval0: {}\".format(newval0))\n",
    "                self._vertices.pop(i)\n",
    "            if i == newedge1:\n",
    "                newval1 = self._vertices[i]\n",
    "                #print(\"newval1: {}\".format(newval1))\n",
    "                self._vertices.pop(i)\n",
    "        if isinstance(edge[0], int):\n",
    "            e0 = (edge[0], ) \n",
    "        if isinstance(edge[1], int):\n",
    "            e1 = (edge[1], )\n",
    "        if isinstance(edge[1], list) and not isinstance(edge[0], list):\n",
    "            self._vertices[tuple(e1) + tuple(e0)] = newval0 + newval1\n",
    "        else:\n",
    "            self._vertices[tuple(e0) + tuple(e1)] = newval0 + newval1\n",
    "        # remove self-loop if any\n",
    "        for i in self._edges:\n",
    "            if i[0] == i[1]:\n",
    "                self._edges.remove(i)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Edges: [[6, 7], [6, 8], [6, 9], [6, 2], [6, 5], [6, 3], [7, 5], [7, 9], [7, 4], [7, 3]]\n",
      "Vertices: [2, 3, 4, 5, 6, 7, 8, 9]\n",
      "Adjacent Edges: [6]\n",
      "\n",
      "After Contraction 1:\n",
      "Edges: [[[6, 9], 7], [[6, 9], 8], [[6, 9], 2], [[6, 9], 5], [[6, 9], 3], [7, 5], [7, [6, 9]], [7, 4], [7, 3]]\n",
      "Vertices: [2, 3, 4, 5, 7, 8, (6, 9)]\n",
      "\n",
      "After Contraction 2:\n",
      "Edges: [[[6, 9, 7], 8], [[6, 9, 7], 2], [[6, 9, 7], 5], [[6, 9, 7], 3], [[6, 9, 7], 5], [[6, 9, 7], 4], [[6, 9, 7], 3]]\n",
      "Vertices: [2, 3, 4, 5, 8, (6, 9, 7)]\n"
     ]
    }
   ],
   "source": [
    "graph = Graph_UndirectedAdjList()\n",
    "#graph.addEdge(1, 2)\n",
    "#graph.addEdge(3, 4)\n",
    "#graph.addEdge(5, 2)\n",
    "graph.addMultipleEdges(6, [7, 8, 9, 2, 5, 3])\n",
    "graph.addMultipleEdges(7, [5, 6, 9, 4, 3])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))\n",
    "print(\"Adjacent Edges: {}\".format(graph.adjacentEdges(2)))\n",
    "print(\"\\nAfter Contraction 1:\")\n",
    "graph.contractEdge([6, 9])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))\n",
    "print(\"\\nAfter Contraction 2:\")\n",
    "graph.contractEdge([[6, 9], 7])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Edges: [[6, 7], [6, 8], [6, 9], [6, 2], [6, 5], [6, 3], [7, 5], [7, 9], [7, 4], [7, 3]]\n",
      "Vertices: [2, 3, 4, 5, 6, 7, 8, 9]\n",
      "Adjacent Edges: [6]\n",
      "\n",
      "After Contraction 1:\n",
      "Edges: [[6, [7, 5]], [6, 8], [6, 9], [6, 2], [6, [7, 5]], [6, 3], [[7, 5], 9], [[7, 5], 4], [[7, 5], 3]]\n",
      "Vertices: [2, 3, 4, 6, 8, 9, (7, 5)]\n",
      "\n",
      "After Contraction 2:\n",
      "Edges: [[[6, 8], [7, 5]], [[6, 8], 9], [[6, 8], 2], [[6, 8], [7, 5]], [[6, 8], 3], [[7, 5], 9], [[7, 5], 4], [[7, 5], 3]]\n",
      "Vertices: [2, 3, 4, (6, 8), 9, (7, 5)]\n",
      "\n",
      "After Contraction 3:\n",
      "Edges: [[[6, 8, 2], [7, 5]], [[6, 8, 2], 9], [[6, 8, 2], [7, 5]], [[6, 8, 2], 3], [[7, 5], 9], [[7, 5], 4], [[7, 5], 3]]\n",
      "Vertices: [3, 4, (6, 8, 2), 9, (7, 5)]\n",
      "\n",
      "After Contraction 4:\n",
      "Edges: [[[6, 8, 2], [7, 5, 9]], [[6, 8, 2], [7, 5, 9]], [[6, 8, 2], [7, 5, 9]], [[6, 8, 2], 3], [[7, 5, 9], 4], [[7, 5, 9], 3]]\n",
      "Vertices: [3, 4, (6, 8, 2), (7, 5, 9)]\n",
      "\n",
      "After Contraction 5:\n",
      "Edges: [[[6, 8, 2], [7, 5, 9, 3]], [[6, 8, 2], [7, 5, 9, 3]], [[6, 8, 2], [7, 5, 9, 3]], [[6, 8, 2], [7, 5, 9, 3]], [[7, 5, 9, 3], 4]]\n",
      "Vertices: [4, (6, 8, 2), (7, 5, 9, 3)]\n",
      "\n",
      "After Contraction 6:\n",
      "Edges: [[[6, 8, 2, 7, 5, 9, 3], 4]]\n",
      "Vertices: [4, (6, 8, 2, 7, 5, 9, 3)]\n"
     ]
    }
   ],
   "source": [
    "#debug\n",
    "graph = Graph_UndirectedAdjList()\n",
    "#graph.addEdge(1, 2)\n",
    "#graph.addEdge(3, 4)\n",
    "#graph.addEdge(5, 2)\n",
    "graph.addMultipleEdges(6, [7, 8, 9, 2, 5, 3])\n",
    "graph.addMultipleEdges(7, [5, 6, 9, 4, 3])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))\n",
    "print(\"Adjacent Edges: {}\".format(graph.adjacentEdges(2)))\n",
    "print(\"\\nAfter Contraction 1:\")\n",
    "graph.contractEdge([7, 5])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))\n",
    "print(\"\\nAfter Contraction 2:\")\n",
    "graph.contractEdge([6, 8])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))\n",
    "print(\"\\nAfter Contraction 3:\")\n",
    "graph.contractEdge([[6, 8], 2])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))\n",
    "print(\"\\nAfter Contraction 4:\")\n",
    "graph.contractEdge([[7, 5], 9])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))\n",
    "print(\"\\nAfter Contraction 5:\")\n",
    "graph.contractEdge([[7, 5, 9], 3])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))\n",
    "print(\"\\nAfter Contraction 6:\")\n",
    "graph.contractEdge([[6, 8, 2], [7, 5, 9, 3]])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Edges: [[6, 7], [6, 8], [6, 9], [6, 2], [6, 5], [6, 3], [7, 5], [7, 9], [7, 4], [7, 3]]\n",
      "Vertices: [2, 3, 4, 5, 6, 7, 8, 9]\n",
      "Adjacent Edges: [6]\n",
      "\n",
      "After Contraction 1:\n",
      "Edges: [[[6, 9], 7], [[6, 9], 8], [[6, 9], 2], [[6, 9], 5], [[6, 9], 3], [7, 5], [7, [6, 9]], [7, 4], [7, 3]]\n",
      "Vertices: [2, 3, 4, 5, 7, 8, (6, 9)]\n",
      "\n",
      "After Contraction 2:\n",
      "Edges: [[[6, 9], [7, 5]], [[6, 9], 8], [[6, 9], 2], [[6, 9], [7, 5]], [[6, 9], 3], [[7, 5], [6, 9]], [[7, 5], 4], [[7, 5], 3]]\n",
      "Vertices: [2, 3, 4, 8, (6, 9), (7, 5)]\n",
      "\n",
      "After Contraction 3:\n",
      "Edges: [[[6, 9, 7, 5], 8], [[6, 9, 7, 5], 2], [[6, 9, 7, 5], 3], [[6, 9, 7, 5], 4], [[6, 9, 7, 5], 3]]\n",
      "Vertices: [2, 3, 4, 8, (6, 9, 7, 5)]\n",
      "\n",
      "After Contraction 4:\n",
      "Edges: [[[6, 9, 7, 5, 8], 2], [[6, 9, 7, 5, 8], 3], [[6, 9, 7, 5, 8], 4], [[6, 9, 7, 5, 8], 3]]\n",
      "Vertices: [2, 3, 4, (6, 9, 7, 5, 8)]\n",
      "\n",
      "After Contraction 5:\n",
      "Edges: [[[6, 9, 7, 5, 8, 3], 2], [[6, 9, 7, 5, 8, 3], 4]]\n",
      "Vertices: [2, 4, (6, 9, 7, 5, 8, 3)]\n",
      "\n",
      "After Contraction 6:\n",
      "Edges: [[[6, 9, 7, 5, 8, 3, 2], 4]]\n",
      "Vertices: [4, (6, 9, 7, 5, 8, 3, 2)]\n"
     ]
    }
   ],
   "source": [
    "graph = Graph_UndirectedAdjList()\n",
    "#graph.addEdge(1, 2)\n",
    "#graph.addEdge(3, 4)\n",
    "#graph.addEdge(5, 2)\n",
    "graph.addMultipleEdges(6, [7, 8, 9, 2, 5, 3])\n",
    "graph.addMultipleEdges(7, [5, 6, 9, 4, 3])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))\n",
    "print(\"Adjacent Edges: {}\".format(graph.adjacentEdges(2)))\n",
    "print(\"\\nAfter Contraction 1:\")\n",
    "graph.contractEdge([6, 9])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))\n",
    "print(\"\\nAfter Contraction 2:\")\n",
    "graph.contractEdge([7, 5])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))\n",
    "print(\"\\nAfter Contraction 3:\")\n",
    "graph.contractEdge([[6, 9], [7, 5]])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))\n",
    "print(\"\\nAfter Contraction 4:\")\n",
    "graph.contractEdge([[6, 9, 7, 5], 8])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))\n",
    "print(\"\\nAfter Contraction 5:\")\n",
    "graph.contractEdge([[6, 9, 7, 5, 8], 3])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))\n",
    "print(\"\\nAfter Contraction 6:\")\n",
    "graph.contractEdge([[6, 9, 7, 5, 8, 3], 2])\n",
    "print(\"Edges: {}\".format(graph.edges()))\n",
    "print(\"Vertices: {}\".format(graph.vertices()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "What we see above is a simple implementation of an adjacency list to represent the graph. With operations to\n",
    "\n",
    "- Add edges\n",
    "- Get list of vertices\n",
    "- Get list of edges\n",
    "- Get adjacent vertices given a vertex in the graph\n",
    "- Contract Edge "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Karger MinCut : Random Contraction Algorithm\n",
      "No of steps: 134\n",
      "Step 0 : Crossing edge : 1\n",
      "Step 1 : Crossing edge : 1\n",
      "Step 2 : Crossing edge : 2\n",
      "Step 3 : Crossing edge : 2\n",
      "Step 4 : Crossing edge : 2\n",
      "Step 5 : Crossing edge : 1\n",
      "Step 6 : Crossing edge : 1\n",
      "Step 7 : Crossing edge : 1\n",
      "Step 8 : Crossing edge : 1\n",
      "Step 9 : Crossing edge : 2\n",
      "Step 10 : Crossing edge : 1\n",
      "Step 11 : Crossing edge : 1\n",
      "Step 12 : Crossing edge : 2\n",
      "Step 13 : Crossing edge : 2\n",
      "Step 14 : Crossing edge : 1\n",
      "Step 15 : Crossing edge : 1\n",
      "Step 16 : Crossing edge : 2\n",
      "Step 17 : Crossing edge : 2\n",
      "Step 18 : Crossing edge : 2\n",
      "Step 19 : Crossing edge : 1\n",
      "Step 20 : Crossing edge : 4\n",
      "Step 21 : Crossing edge : 1\n",
      "Step 22 : Crossing edge : 1\n",
      "Step 23 : Crossing edge : 2\n",
      "Step 24 : Crossing edge : 2\n",
      "Step 25 : Crossing edge : 2\n",
      "Step 26 : Crossing edge : 1\n",
      "Step 27 : Crossing edge : 2\n",
      "Step 28 : Crossing edge : 1\n",
      "Step 29 : Crossing edge : 2\n",
      "Step 30 : Crossing edge : 2\n",
      "Step 31 : Crossing edge : 2\n",
      "Step 32 : Crossing edge : 2\n",
      "Step 33 : Crossing edge : 2\n",
      "Step 34 : Crossing edge : 2\n",
      "Step 35 : Crossing edge : 2\n",
      "Step 36 : Crossing edge : 1\n",
      "Step 37 : Crossing edge : 2\n",
      "Step 38 : Crossing edge : 1\n",
      "Step 39 : Crossing edge : 1\n",
      "Step 40 : Crossing edge : 2\n",
      "Step 41 : Crossing edge : 2\n",
      "Step 42 : Crossing edge : 1\n",
      "Step 43 : Crossing edge : 1\n",
      "Step 44 : Crossing edge : 1\n",
      "Step 45 : Crossing edge : 2\n",
      "Step 46 : Crossing edge : 2\n",
      "Step 47 : Crossing edge : 1\n",
      "Step 48 : Crossing edge : 4\n",
      "Step 49 : Crossing edge : 4\n",
      "Step 50 : Crossing edge : 2\n",
      "Step 51 : Crossing edge : 2\n",
      "Step 52 : Crossing edge : 1\n",
      "Step 53 : Crossing edge : 1\n",
      "Step 54 : Crossing edge : 1\n",
      "Step 55 : Crossing edge : 2\n",
      "Step 56 : Crossing edge : 2\n",
      "Step 57 : Crossing edge : 1\n",
      "Step 58 : Crossing edge : 4\n",
      "Step 59 : Crossing edge : 1\n",
      "Step 60 : Crossing edge : 1\n",
      "Step 61 : Crossing edge : 1\n",
      "Step 62 : Crossing edge : 2\n",
      "Step 63 : Crossing edge : 2\n",
      "Step 64 : Crossing edge : 1\n",
      "Step 65 : Crossing edge : 2\n",
      "Step 66 : Crossing edge : 1\n",
      "Step 67 : Crossing edge : 2\n",
      "Step 68 : Crossing edge : 1\n",
      "Step 69 : Crossing edge : 2\n",
      "Step 70 : Crossing edge : 1\n",
      "Step 71 : Crossing edge : 2\n",
      "Step 72 : Crossing edge : 1\n",
      "Step 73 : Crossing edge : 2\n",
      "Step 74 : Crossing edge : 2\n",
      "Step 75 : Crossing edge : 2\n",
      "Step 76 : Crossing edge : 2\n",
      "Step 77 : Crossing edge : 1\n",
      "Step 78 : Crossing edge : 1\n",
      "Step 79 : Crossing edge : 2\n",
      "Step 80 : Crossing edge : 2\n",
      "Step 81 : Crossing edge : 1\n",
      "Step 82 : Crossing edge : 1\n",
      "Step 83 : Crossing edge : 4\n",
      "Step 84 : Crossing edge : 1\n",
      "Step 85 : Crossing edge : 2\n",
      "Step 86 : Crossing edge : 2\n",
      "Step 87 : Crossing edge : 2\n",
      "Step 88 : Crossing edge : 2\n",
      "Step 89 : Crossing edge : 2\n",
      "Step 90 : Crossing edge : 1\n",
      "Step 91 : Crossing edge : 1\n",
      "Step 92 : Crossing edge : 2\n",
      "Step 93 : Crossing edge : 1\n",
      "Step 94 : Crossing edge : 2\n",
      "Step 95 : Crossing edge : 2\n",
      "Step 96 : Crossing edge : 1\n",
      "Step 97 : Crossing edge : 2\n",
      "Step 98 : Crossing edge : 1\n",
      "Step 99 : Crossing edge : 2\n",
      "Step 100 : Crossing edge : 1\n",
      "Step 101 : Crossing edge : 2\n",
      "Step 102 : Crossing edge : 1\n",
      "Step 103 : Crossing edge : 2\n",
      "Step 104 : Crossing edge : 2\n",
      "Step 105 : Crossing edge : 2\n",
      "Step 106 : Crossing edge : 2\n",
      "Step 107 : Crossing edge : 2\n",
      "Step 108 : Crossing edge : 1\n",
      "Step 109 : Crossing edge : 1\n",
      "Step 110 : Crossing edge : 2\n",
      "Step 111 : Crossing edge : 1\n",
      "Step 112 : Crossing edge : 2\n",
      "Step 113 : Crossing edge : 2\n",
      "Step 114 : Crossing edge : 1\n",
      "Step 115 : Crossing edge : 2\n",
      "Step 116 : Crossing edge : 1\n",
      "Step 117 : Crossing edge : 2\n",
      "Step 118 : Crossing edge : 2\n",
      "Step 119 : Crossing edge : 1\n",
      "Step 120 : Crossing edge : 1\n",
      "Step 121 : Crossing edge : 2\n",
      "Step 122 : Crossing edge : 2\n",
      "Step 123 : Crossing edge : 1\n",
      "Step 124 : Crossing edge : 2\n",
      "Step 125 : Crossing edge : 1\n",
      "Step 126 : Crossing edge : 2\n",
      "Step 127 : Crossing edge : 2\n",
      "Step 128 : Crossing edge : 1\n",
      "Step 129 : Crossing edge : 2\n",
      "Step 130 : Crossing edge : 1\n",
      "Step 131 : Crossing edge : 2\n",
      "Step 132 : Crossing edge : 2\n",
      "Step 133 : Crossing edge : 2\n",
      "MinCut: 1\n",
      "1st cut: 2  2nd cut: (6, 7, 5, 4, 8, 9, 3)\n"
     ]
    }
   ],
   "source": [
    "import random \n",
    "import math\n",
    "\n",
    "def RandomContractionAlgorithm(objGraph): \n",
    "    while len(objGraph.vertices()) > 2 or len(objGraph.edges()) > 1 :\n",
    "        if len(objGraph.vertices()) == 2 or len(objGraph.edges()) == 2 :\n",
    "            break\n",
    "        #print(\"V: {} E: {}\".format(len(objGraph.vertices()), len(objGraph.edges())))\n",
    "        #if len(objGraph.edges()) <= 2:\n",
    "            #print(\"V: {} E: {}\".format(len(objGraph.vertices()), len(objGraph.edges())))\n",
    "        randomedgeidx = random.randint(0,len(objGraph.edges())-1)\n",
    "        #print(\"Random no: {}\".format(randomedgeidx))\n",
    "        #print(\"Random edge: {}\".format(objGraph.edges()[randomedgeidx]))\n",
    "        objGraph.contractEdge(objGraph.edges()[randomedgeidx])\n",
    "        #print(\"Edges: {}\".format(objGraph.edges()))\n",
    "        #print(\"Vertices: {}\".format(objGraph.vertices()))\n",
    "    #if len(objGraph.vertices()) > 2 and len(objGraph.edges()) > 1 :\n",
    "    crossingedges = len(objGraph.edges())\n",
    "    return objGraph.vertices(), crossingedges\n",
    "    \n",
    "\n",
    "\n",
    "def KargerMinCut(objectGraph):\n",
    "    n = len(objectGraph.vertices())\n",
    "    N = int(math.ceil(n**2 * math.log(n)))\n",
    "    min_cut = float('inf')\n",
    "    mincut_nodes = None\n",
    "    print(\"Karger MinCut : Random Contraction Algorithm\")\n",
    "    print(\"No of steps: {}\".format(N))\n",
    "    for ij in range(N):\n",
    "    #for _ in range(1):\n",
    "        objGraph = deepcopy(objectGraph)\n",
    "        cuts, crossingedges = RandomContractionAlgorithm(objGraph)\n",
    "        print(\"Step {} : Crossing edge : {}\".format(ij, crossingedges))\n",
    "        if crossingedges < min_cut:\n",
    "            min_cut = crossingedges\n",
    "            mincut_nodes = cuts\n",
    "    #print(\"Karger MinCut : Random Contraction Algorithm\")\n",
    "    #print(\"Edges: {}\".format(objectGraph.edges()))\n",
    "    #print(\"Vertices: {}\".format(objectGraph.vertices()))\n",
    "    print(\"MinCut: {}\".format(min_cut))    \n",
    "    print(\"1st cut: {}  2nd cut: {}\".format(mincut_nodes[0], mincut_nodes[1]))\n",
    "\n",
    "graph = Graph_UndirectedAdjList()\n",
    "graph.addMultipleEdges(6, [7, 8, 9, 2, 5, 3])\n",
    "graph.addMultipleEdges(7, [5, 6, 9, 4, 3])\n",
    "KargerMinCut(graph)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 521,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "2\n",
      "[[6, 3, 8, 7, 9], 5]\n",
      "[[6, 3, 8, 7, 9], 5, [3333]]\n",
      "[[[6, 3, 8, 7, 9], 5], [[6, 7], 8]]\n",
      "[[6, 3, 8, 7, 9], 5, [[6, 7], 8]]\n",
      "[[[6, 3, 8, 7, 9], 5], [[6, 7], 8]]\n",
      "5\n",
      "2\n",
      "[[[6, 3, 7, 9], 8], [[6, 3, 7, 9], 2], [[6, 3, 7, 9], 5], [5, [6, 3, 7, 9]], [[6, 3, 7, 9], 4]]\n",
      "[[[6, 3, 7, 9], 8], [[6, 3, 7, 9], 2], [[6, 3, 7, 9], 5], [5, [6, 3, 7, 9]], [[6, 3, 7, 9], 4]]\n",
      "[[[6, 3, 7, 9], 8], [[6, 3, 7, 9], 2], [[6, 3, 7, 9], 5], [5, [6, 3, 7, 9]], [[6, 3, 7, 9], 4]]\n",
      "[[[6, 3, 7, 9], 8], [[6, 3, 7, 9], 2], [[6, 3, 7, 9], 5], [5, [6, 3, 7, 9]], [[6, 3, 7, 9], 4]]\n",
      "[[[6, 3, 7, 9], 8], [[6, 3, 7, 9], 2], [5, [6, 3, 7, 9]], [[6, 3, 7, 9], 4]]\n",
      "[[[6, 3, 7, 9], 8], [[6, 3, 7, 9], 2], [[6, 3, 7, 9], 4]]\n",
      "[[[6, 3, 7, 9], 8], [[6, 3, 7, 9], 2], [[6, 3, 7, 9], 4]]\n"
     ]
    }
   ],
   "source": [
    "# titbit\n",
    "x = [[[6, 3, 8, 7, 9], 5], [[6, 7], 8]]\n",
    "print(len( x ))\n",
    "print(len(x[0]))\n",
    "y = deepcopy(x[0])\n",
    "print(y)\n",
    "y.append([3333])\n",
    "print(y)\n",
    "print(x)\n",
    "for _ in range(7):\n",
    "    y = deepcopy(x[0])\n",
    "    y.append(x[1])\n",
    "print(y)\n",
    "print(x)\n",
    "\n",
    "\n",
    "\n",
    "x = [[[6, 3, 7, 9], 8], [[6, 3, 7, 9], 2], [[6, 3, 7, 9], 5], [5, [6, 3, 7, 9]], [[6, 3, 7, 9], 4]]\n",
    "print(len(x))\n",
    "print(len(x[1]))\n",
    "\n",
    "print(x) \n",
    "edge = [[6, 3, 7, 9], 5]\n",
    "idx = 0\n",
    "for _ in range(len(x)):\n",
    "    print(x)\n",
    "    if x[idx][0] == edge[0]  and  x[idx][1] == edge[1] :\n",
    "        x.remove(x[idx])\n",
    "        idx -= 1\n",
    "    if x[idx][0] == edge[1]  and  x[idx][1] == edge[0] :\n",
    "        x.remove(x[idx])\n",
    "        idx -= 1    \n",
    "    idx +=1\n",
    "print(x)    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "[[[6, 8, 3], [7, 9, 4, 5]], [[6, 8, 3], [7, 9, 4, 5]], [[6, 8, 3], 2], [[6, 8, 3], [7, 9, 4, 5]], [[7, 9, 4, 5], [6, 8, 3]]]\n",
      "0\n",
      "[[[6, 8, 3], [7, 9, 4, 5]], [[6, 8, 3], 2], [[6, 8, 3], [7, 9, 4, 5]], [[7, 9, 4, 5], [6, 8, 3]]]\n",
      "0\n",
      "[[[6, 8, 3], 2], [[6, 8, 3], [7, 9, 4, 5]], [[7, 9, 4, 5], [6, 8, 3]]]\n",
      "1\n",
      "[[[6, 8, 3], 2], [[6, 8, 3], [7, 9, 4, 5]], [[7, 9, 4, 5], [6, 8, 3]]]\n",
      "1\n",
      "[[[6, 8, 3], 2], [[7, 9, 4, 5], [6, 8, 3]]]\n",
      "[[[6, 8, 3], 2]]\n"
     ]
    }
   ],
   "source": [
    "# titbit\n",
    "x = [[[6, 8, 3], [7, 9, 4, 5]], [[6, 8, 3], [7, 9, 4, 5]], [[6, 8, 3], 2], [[6, 8, 3], [7, 9, 4, 5]], [[7, 9, 4, 5], [6, 8, 3]]]\n",
    "edge = [[6, 8, 3], [7, 9, 4, 5]]\n",
    "idx = 0\n",
    "for _ in range(len(x)):\n",
    "    print(idx)\n",
    "    print(x)\n",
    "    if x[idx][0] == edge[0]  and  x[idx][1] == edge[1] :\n",
    "        x.remove(x[idx])\n",
    "        idx -= 1\n",
    "    elif x[idx][0] == edge[1]  and  x[idx][1] == edge[0] :\n",
    "        x.remove(x[idx])\n",
    "        idx -= 1    \n",
    "    idx += 1\n",
    "print(x)      \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Challenge Problem\n",
    "Download the following text file:  kargerMinCut.txt\n",
    "The file contains the adjacency list representation of a simple undirected graph. There are 200 vertices labeled 1 to 200. The first column in the file represents the vertex label, and the particular row (other entries except the first column) tells all the vertices that the vertex is adjacent to. So for example, the $6^{th}$ row looks like : \"6\t155\t56\t52\t120\t......\". This just means that the vertex with label 6 is adjacent to (i.e., shares an edge with) the vertices with labels 155,56,52,120,......,etc\n",
    "\n",
    "Your task is to code up and run the randomized contraction algorithm for the min cut problem and use it on the above graph to compute the min cut. (HINT: Note that you'll have to figure out an implementation of edge contractions. Initially, you might want to do this naively, creating a new graph from the old every time there's an edge contraction. But you should also think about more efficient implementations.) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/aishwaya/anaconda2/lib/python2.7/site-packages/urllib3/connectionpool.py:858: InsecureRequestWarning: Unverified HTTPS request is being made. Adding certificate verification is strongly advised. See: https://urllib3.readthedocs.io/en/latest/advanced-usage.html#ssl-warnings\n",
      "  InsecureRequestWarning)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Karger MinCut : Random Contraction Algorithm\n",
      "No of steps: 211933\n",
      "Step 0 : Crossing edge : 21\n",
      "Step 1 : Crossing edge : 21\n",
      "Step 2 : Crossing edge : 20\n",
      "Step 3 : Crossing edge : 23\n",
      "Step 4 : Crossing edge : 26\n",
      "Step 5 : Crossing edge : 21\n",
      "Step 6 : Crossing edge : 24\n",
      "Step 7 : Crossing edge : 23\n",
      "Step 8 : Crossing edge : 20\n",
      "Step 9 : Crossing edge : 25\n",
      "Step 10 : Crossing edge : 20\n",
      "Step 11 : Crossing edge : 27\n",
      "Step 12 : Crossing edge : 20\n",
      "Step 13 : Crossing edge : 26\n",
      "Step 14 : Crossing edge : 23\n",
      "Step 15 : Crossing edge : 20\n",
      "Step 16 : Crossing edge : 25\n",
      "Step 17 : Crossing edge : 20\n",
      "Step 18 : Crossing edge : 21\n",
      "Step 19 : Crossing edge : 20\n",
      "Step 20 : Crossing edge : 20\n",
      "Step 21 : Crossing edge : 26\n",
      "Step 22 : Crossing edge : 24\n",
      "Step 23 : Crossing edge : 21\n",
      "Step 24 : Crossing edge : 21\n",
      "Step 25 : Crossing edge : 23\n",
      "Step 26 : Crossing edge : 23\n",
      "Step 27 : Crossing edge : 22\n",
      "Step 28 : Crossing edge : 23\n",
      "Step 29 : Crossing edge : 26\n",
      "Step 30 : Crossing edge : 23\n",
      "Step 31 : Crossing edge : 31\n",
      "Step 32 : Crossing edge : 20\n",
      "Step 33 : Crossing edge : 22\n",
      "Step 34 : Crossing edge : 26\n",
      "Step 35 : Crossing edge : 20\n",
      "Step 36 : Crossing edge : 23\n",
      "Step 37 : Crossing edge : 27\n",
      "Step 38 : Crossing edge : 20\n",
      "Step 39 : Crossing edge : 31\n",
      "Step 40 : Crossing edge : 20\n",
      "Step 41 : Crossing edge : 20\n",
      "Step 42 : Crossing edge : 21\n",
      "Step 43 : Crossing edge : 22\n",
      "Step 44 : Crossing edge : 20\n",
      "Step 45 : Crossing edge : 31\n",
      "Step 46 : Crossing edge : 24\n",
      "Step 47 : Crossing edge : 21\n",
      "Step 48 : Crossing edge : 26\n",
      "Step 49 : Crossing edge : 22\n",
      "Step 50 : Crossing edge : 21\n",
      "Step 51 : Crossing edge : 26\n",
      "Step 52 : Crossing edge : 20\n",
      "Step 53 : Crossing edge : 20\n",
      "Step 54 : Crossing edge : 22\n",
      "Step 55 : Crossing edge : 22\n",
      "Step 56 : Crossing edge : 22\n",
      "Step 57 : Crossing edge : 23\n",
      "Step 58 : Crossing edge : 25\n",
      "Step 59 : Crossing edge : 24\n",
      "Step 60 : Crossing edge : 21\n",
      "Step 61 : Crossing edge : 23\n",
      "Step 62 : Crossing edge : 21\n",
      "Step 63 : Crossing edge : 22\n",
      "Step 64 : Crossing edge : 20\n",
      "Step 65 : Crossing edge : 31\n",
      "Step 66 : Crossing edge : 24\n",
      "Step 67 : Crossing edge : 22\n",
      "Step 68 : Crossing edge : 27\n",
      "Step 69 : Crossing edge : 20\n",
      "Step 70 : Crossing edge : 24\n",
      "Step 71 : Crossing edge : 20\n",
      "Step 72 : Crossing edge : 21\n",
      "Step 73 : Crossing edge : 30\n",
      "Step 74 : Crossing edge : 26\n",
      "Step 75 : Crossing edge : 22\n",
      "Step 76 : Crossing edge : 20\n",
      "Step 77 : Crossing edge : 20\n",
      "Step 78 : Crossing edge : 22\n",
      "Step 79 : Crossing edge : 20\n",
      "Step 80 : Crossing edge : 20\n",
      "Step 81 : Crossing edge : 22\n",
      "Step 82 : Crossing edge : 25\n",
      "Step 83 : Crossing edge : 24\n",
      "Step 84 : Crossing edge : 23\n",
      "Step 85 : Crossing edge : 20\n",
      "Step 86 : Crossing edge : 20\n",
      "Step 87 : Crossing edge : 28\n",
      "Step 88 : Crossing edge : 25\n",
      "Step 89 : Crossing edge : 21\n",
      "Step 90 : Crossing edge : 22\n",
      "Step 91 : Crossing edge : 20\n",
      "Step 92 : Crossing edge : 23\n",
      "Step 93 : Crossing edge : 22\n",
      "Step 94 : Crossing edge : 26\n",
      "Step 95 : Crossing edge : 21\n",
      "Step 96 : Crossing edge : 24\n",
      "Step 97 : Crossing edge : 24\n",
      "Step 98 : Crossing edge : 22\n",
      "Step 99 : Crossing edge : 21\n",
      "Step 100 : Crossing edge : 20\n",
      "Step 101 : Crossing edge : 24\n",
      "Step 102 : Crossing edge : 20\n",
      "Step 103 : Crossing edge : 24\n",
      "Step 104 : Crossing edge : 23\n",
      "Step 105 : Crossing edge : 40\n",
      "Step 106 : Crossing edge : 20\n",
      "Step 107 : Crossing edge : 20\n",
      "Step 108 : Crossing edge : 21\n",
      "Step 109 : Crossing edge : 26\n",
      "Step 110 : Crossing edge : 25\n",
      "Step 111 : Crossing edge : 22\n",
      "Step 112 : Crossing edge : 20\n",
      "Step 113 : Crossing edge : 21\n",
      "Step 114 : Crossing edge : 21\n",
      "Step 115 : Crossing edge : 20\n",
      "Step 116 : Crossing edge : 20\n",
      "Step 117 : Crossing edge : 26\n",
      "Step 118 : Crossing edge : 24\n",
      "Step 119 : Crossing edge : 20\n",
      "Step 120 : Crossing edge : 25\n",
      "Step 121 : Crossing edge : 20\n",
      "Step 122 : Crossing edge : 22\n",
      "Step 123 : Crossing edge : 22\n",
      "Step 124 : Crossing edge : 22\n",
      "Step 125 : Crossing edge : 23\n",
      "Step 126 : Crossing edge : 17\n",
      "Step 127 : Crossing edge : 20\n",
      "Step 128 : Crossing edge : 20\n",
      "Step 129 : Crossing edge : 20\n",
      "Step 130 : Crossing edge : 23\n",
      "Step 131 : Crossing edge : 20\n",
      "Step 132 : Crossing edge : 25\n",
      "Step 133 : Crossing edge : 20\n",
      "Step 134 : Crossing edge : 20\n",
      "Step 135 : Crossing edge : 25\n",
      "Step 136 : Crossing edge : 24\n",
      "Step 137 : Crossing edge : 34\n",
      "Step 138 : Crossing edge : 20\n",
      "Step 139 : Crossing edge : 21\n",
      "Step 140 : Crossing edge : 24\n",
      "Step 141 : Crossing edge : 21\n",
      "Step 142 : Crossing edge : 20\n",
      "Step 143 : Crossing edge : 20\n",
      "Step 144 : Crossing edge : 20\n",
      "Step 145 : Crossing edge : 20\n",
      "Step 146 : Crossing edge : 20\n",
      "Step 147 : Crossing edge : 20\n",
      "Step 148 : Crossing edge : 23\n",
      "Step 149 : Crossing edge : 25\n",
      "Step 150 : Crossing edge : 21\n",
      "Step 151 : Crossing edge : 28\n",
      "Step 152 : Crossing edge : 20\n",
      "Step 153 : Crossing edge : 20\n",
      "Step 154 : Crossing edge : 26\n",
      "Step 155 : Crossing edge : 21\n",
      "Step 156 : Crossing edge : 20\n",
      "Step 157 : Crossing edge : 25\n",
      "Step 158 : Crossing edge : 20\n",
      "Step 159 : Crossing edge : 20\n",
      "Step 160 : Crossing edge : 20\n",
      "Step 161 : Crossing edge : 20\n",
      "Step 162 : Crossing edge : 21\n",
      "Step 163 : Crossing edge : 23\n",
      "Step 164 : Crossing edge : 22\n",
      "Step 165 : Crossing edge : 21\n",
      "Step 166 : Crossing edge : 20\n",
      "Step 167 : Crossing edge : 20\n",
      "Step 168 : Crossing edge : 21\n",
      "Step 169 : Crossing edge : 20\n",
      "Step 170 : Crossing edge : 20\n",
      "Step 171 : Crossing edge : 20\n",
      "Step 172 : Crossing edge : 20\n",
      "Step 173 : Crossing edge : 20\n",
      "Step 174 : Crossing edge : 23\n",
      "Step 175 : Crossing edge : 20\n",
      "Step 176 : Crossing edge : 21\n",
      "Step 177 : Crossing edge : 23\n",
      "Step 178 : Crossing edge : 20\n",
      "Step 179 : Crossing edge : 20\n",
      "Step 180 : Crossing edge : 28\n",
      "Step 181 : Crossing edge : 20\n",
      "Step 182 : Crossing edge : 26\n",
      "Step 183 : Crossing edge : 24\n",
      "Step 184 : Crossing edge : 35\n",
      "Step 185 : Crossing edge : 20\n",
      "Step 186 : Crossing edge : 26\n",
      "Step 187 : Crossing edge : 24\n",
      "Step 188 : Crossing edge : 20\n",
      "Step 189 : Crossing edge : 59\n",
      "Step 190 : Crossing edge : 44\n",
      "Step 191 : Crossing edge : 23\n",
      "Step 192 : Crossing edge : 23\n",
      "Step 193 : Crossing edge : 21\n",
      "Step 194 : Crossing edge : 20\n",
      "Step 195 : Crossing edge : 24\n",
      "Step 196 : Crossing edge : 22\n",
      "Step 197 : Crossing edge : 26\n",
      "Step 198 : Crossing edge : 20\n",
      "Step 199 : Crossing edge : 21\n",
      "Step 200 : Crossing edge : 23\n",
      "Step 201 : Crossing edge : 20\n",
      "Step 202 : Crossing edge : 20\n",
      "Step 203 : Crossing edge : 26\n",
      "Step 204 : Crossing edge : 20\n",
      "Step 205 : Crossing edge : 24\n",
      "Step 206 : Crossing edge : 20\n",
      "Step 207 : Crossing edge : 21\n",
      "Step 208 : Crossing edge : 22\n",
      "Step 209 : Crossing edge : 44\n",
      "Step 210 : Crossing edge : 27\n",
      "Step 211 : Crossing edge : 24\n",
      "Step 212 : Crossing edge : 22\n",
      "Step 213 : Crossing edge : 26\n",
      "Step 214 : Crossing edge : 28\n",
      "Step 215 : Crossing edge : 22\n",
      "Step 216 : Crossing edge : 20\n",
      "Step 217 : Crossing edge : 20\n",
      "Step 218 : Crossing edge : 20\n",
      "Step 219 : Crossing edge : 20\n",
      "Step 220 : Crossing edge : 24\n",
      "Step 221 : Crossing edge : 20\n",
      "Step 222 : Crossing edge : 20\n",
      "Step 223 : Crossing edge : 20\n",
      "Step 224 : Crossing edge : 23\n",
      "Step 225 : Crossing edge : 26\n",
      "Step 226 : Crossing edge : 24\n",
      "Step 227 : Crossing edge : 22\n",
      "Step 228 : Crossing edge : 48\n",
      "Step 229 : Crossing edge : 20\n",
      "Step 230 : Crossing edge : 22\n",
      "Step 231 : Crossing edge : 17\n",
      "Step 232 : Crossing edge : 20\n",
      "Step 233 : Crossing edge : 30\n",
      "Step 234 : Crossing edge : 22\n",
      "Step 235 : Crossing edge : 20\n",
      "Step 236 : Crossing edge : 23\n",
      "Step 237 : Crossing edge : 25\n",
      "Step 238 : Crossing edge : 23\n",
      "Step 239 : Crossing edge : 17\n",
      "Step 240 : Crossing edge : 23\n",
      "Step 241 : Crossing edge : 20\n",
      "Step 242 : Crossing edge : 23\n",
      "Step 243 : Crossing edge : 22\n",
      "Step 244 : Crossing edge : 21\n",
      "Step 245 : Crossing edge : 25\n",
      "Step 246 : Crossing edge : 20\n",
      "Step 247 : Crossing edge : 20\n",
      "Step 248 : Crossing edge : 21\n",
      "Step 249 : Crossing edge : 22\n",
      "Step 250 : Crossing edge : 24\n",
      "Step 251 : Crossing edge : 20\n",
      "Step 252 : Crossing edge : 26\n",
      "Step 253 : Crossing edge : 22\n",
      "Step 254 : Crossing edge : 22\n",
      "Step 255 : Crossing edge : 26\n",
      "Step 256 : Crossing edge : 21\n",
      "Step 257 : Crossing edge : 27\n",
      "Step 258 : Crossing edge : 25\n",
      "Step 259 : Crossing edge : 20\n",
      "Step 260 : Crossing edge : 24\n",
      "Step 261 : Crossing edge : 22\n",
      "Step 262 : Crossing edge : 25\n",
      "Step 263 : Crossing edge : 24\n",
      "Step 264 : Crossing edge : 22\n",
      "Step 265 : Crossing edge : 20\n",
      "Step 266 : Crossing edge : 20\n",
      "Step 267 : Crossing edge : 20\n",
      "Step 268 : Crossing edge : 21\n",
      "Step 269 : Crossing edge : 20\n",
      "Step 270 : Crossing edge : 22\n",
      "Step 271 : Crossing edge : 20\n",
      "Step 272 : Crossing edge : 31\n",
      "Step 273 : Crossing edge : 21\n",
      "Step 274 : Crossing edge : 20\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Step 275 : Crossing edge : 22\n",
      "Step 276 : Crossing edge : 25\n",
      "Step 277 : Crossing edge : 21\n",
      "Step 278 : Crossing edge : 17\n",
      "Step 279 : Crossing edge : 21\n",
      "Step 280 : Crossing edge : 28\n",
      "Step 281 : Crossing edge : 22\n",
      "Step 282 : Crossing edge : 24\n",
      "Step 283 : Crossing edge : 26\n",
      "Step 284 : Crossing edge : 21\n",
      "Step 285 : Crossing edge : 20\n",
      "Step 286 : Crossing edge : 20\n",
      "Step 287 : Crossing edge : 22\n",
      "Step 288 : Crossing edge : 24\n",
      "Step 289 : Crossing edge : 22\n",
      "Step 290 : Crossing edge : 28\n",
      "Step 291 : Crossing edge : 20\n",
      "Step 292 : Crossing edge : 21\n",
      "Step 293 : Crossing edge : 20\n",
      "Step 294 : Crossing edge : 20\n",
      "Step 295 : Crossing edge : 20\n",
      "Step 296 : Crossing edge : 24\n",
      "Step 297 : Crossing edge : 25\n",
      "Step 298 : Crossing edge : 22\n",
      "Step 299 : Crossing edge : 20\n",
      "Step 300 : Crossing edge : 24\n",
      "Step 301 : Crossing edge : 26\n",
      "Step 302 : Crossing edge : 26\n",
      "Step 303 : Crossing edge : 26\n",
      "Step 304 : Crossing edge : 26\n",
      "Step 305 : Crossing edge : 26\n",
      "Step 306 : Crossing edge : 23\n",
      "Step 307 : Crossing edge : 27\n",
      "Step 308 : Crossing edge : 21\n",
      "Step 309 : Crossing edge : 22\n",
      "Step 310 : Crossing edge : 20\n",
      "Step 311 : Crossing edge : 20\n",
      "Step 312 : Crossing edge : 24\n",
      "Step 313 : Crossing edge : 20\n",
      "Step 314 : Crossing edge : 23\n",
      "Step 315 : Crossing edge : 31\n",
      "Step 316 : Crossing edge : 20\n",
      "Step 317 : Crossing edge : 20\n",
      "Step 318 : Crossing edge : 20\n",
      "Step 319 : Crossing edge : 22\n",
      "Step 320 : Crossing edge : 17\n",
      "Step 321 : Crossing edge : 26\n",
      "Step 322 : Crossing edge : 24\n",
      "Step 323 : Crossing edge : 22\n",
      "Step 324 : Crossing edge : 21\n",
      "Step 325 : Crossing edge : 30\n",
      "Step 326 : Crossing edge : 20\n",
      "Step 327 : Crossing edge : 22\n",
      "Step 328 : Crossing edge : 23\n",
      "Step 329 : Crossing edge : 27\n",
      "Step 330 : Crossing edge : 28\n",
      "Step 331 : Crossing edge : 21\n",
      "Step 332 : Crossing edge : 20\n",
      "Step 333 : Crossing edge : 23\n",
      "Step 334 : Crossing edge : 20\n",
      "Step 335 : Crossing edge : 17\n",
      "Step 336 : Crossing edge : 21\n",
      "Step 337 : Crossing edge : 27\n",
      "Step 338 : Crossing edge : 20\n",
      "Step 339 : Crossing edge : 20\n",
      "Step 340 : Crossing edge : 22\n",
      "Step 341 : Crossing edge : 25\n",
      "Step 342 : Crossing edge : 23\n",
      "Step 343 : Crossing edge : 21\n",
      "Step 344 : Crossing edge : 20\n",
      "Step 345 : Crossing edge : 23\n",
      "Step 346 : Crossing edge : 27\n",
      "Step 347 : Crossing edge : 22\n",
      "Step 348 : Crossing edge : 45\n",
      "Step 349 : Crossing edge : 27\n",
      "Step 350 : Crossing edge : 26\n",
      "Step 351 : Crossing edge : 28\n",
      "Step 352 : Crossing edge : 20\n",
      "Step 353 : Crossing edge : 28\n",
      "Step 354 : Crossing edge : 27\n",
      "Step 355 : Crossing edge : 22\n",
      "Step 356 : Crossing edge : 20\n",
      "Step 357 : Crossing edge : 22\n",
      "Step 358 : Crossing edge : 25\n",
      "Step 359 : Crossing edge : 26\n",
      "Step 360 : Crossing edge : 23\n",
      "Step 361 : Crossing edge : 20\n",
      "Step 362 : Crossing edge : 20\n",
      "Step 363 : Crossing edge : 22\n",
      "Step 364 : Crossing edge : 27\n",
      "Step 365 : Crossing edge : 26\n",
      "Step 366 : Crossing edge : 20\n",
      "Step 367 : Crossing edge : 20\n",
      "Step 368 : Crossing edge : 22\n",
      "Step 369 : Crossing edge : 20\n",
      "Step 370 : Crossing edge : 21\n",
      "Step 371 : Crossing edge : 20\n",
      "Step 372 : Crossing edge : 23\n",
      "Step 373 : Crossing edge : 47\n",
      "Step 374 : Crossing edge : 22\n",
      "Step 375 : Crossing edge : 22\n",
      "Step 376 : Crossing edge : 20\n",
      "Step 377 : Crossing edge : 21\n",
      "Step 378 : Crossing edge : 23\n",
      "Step 379 : Crossing edge : 25\n",
      "Step 380 : Crossing edge : 24\n",
      "Step 381 : Crossing edge : 24\n",
      "Step 382 : Crossing edge : 20\n",
      "Step 383 : Crossing edge : 20\n",
      "Step 384 : Crossing edge : 20\n",
      "Step 385 : Crossing edge : 20\n",
      "Step 386 : Crossing edge : 21\n",
      "Step 387 : Crossing edge : 21\n",
      "Step 388 : Crossing edge : 23\n",
      "Step 389 : Crossing edge : 20\n",
      "Step 390 : Crossing edge : 23\n",
      "Step 391 : Crossing edge : 20\n",
      "Step 392 : Crossing edge : 20\n",
      "Step 393 : Crossing edge : 20\n",
      "Step 394 : Crossing edge : 20\n",
      "Step 395 : Crossing edge : 23\n",
      "Step 396 : Crossing edge : 28\n",
      "Step 397 : Crossing edge : 20\n",
      "Step 398 : Crossing edge : 22\n",
      "Step 399 : Crossing edge : 23\n",
      "Step 400 : Crossing edge : 27\n",
      "Step 401 : Crossing edge : 22\n",
      "Step 402 : Crossing edge : 22\n",
      "Step 403 : Crossing edge : 21\n",
      "Step 404 : Crossing edge : 25\n",
      "Step 405 : Crossing edge : 21\n",
      "Step 406 : Crossing edge : 29\n",
      "Step 407 : Crossing edge : 20\n",
      "Step 408 : Crossing edge : 20\n",
      "Step 409 : Crossing edge : 20\n",
      "Step 410 : Crossing edge : 22\n",
      "Step 411 : Crossing edge : 20\n",
      "Step 412 : Crossing edge : 20\n",
      "Step 413 : Crossing edge : 20\n",
      "Step 414 : Crossing edge : 23\n",
      "Step 415 : Crossing edge : 20\n",
      "Step 416 : Crossing edge : 20\n",
      "Step 417 : Crossing edge : 25\n",
      "Step 418 : Crossing edge : 26\n",
      "Step 419 : Crossing edge : 24\n",
      "Step 420 : Crossing edge : 21\n",
      "Step 421 : Crossing edge : 22\n",
      "Step 422 : Crossing edge : 20\n",
      "Step 423 : Crossing edge : 20\n",
      "Step 424 : Crossing edge : 21\n",
      "Step 425 : Crossing edge : 21\n",
      "Step 426 : Crossing edge : 20\n",
      "Step 427 : Crossing edge : 20\n",
      "Step 428 : Crossing edge : 26\n",
      "Step 429 : Crossing edge : 24\n",
      "Step 430 : Crossing edge : 20\n",
      "Step 431 : Crossing edge : 20\n",
      "Step 432 : Crossing edge : 20\n",
      "Step 433 : Crossing edge : 24\n",
      "Step 434 : Crossing edge : 24\n",
      "Step 435 : Crossing edge : 22\n",
      "Step 436 : Crossing edge : 20\n",
      "Step 437 : Crossing edge : 47\n",
      "Step 438 : Crossing edge : 22\n",
      "Step 439 : Crossing edge : 22\n",
      "Step 440 : Crossing edge : 25\n",
      "Step 441 : Crossing edge : 17\n",
      "Step 442 : Crossing edge : 21\n",
      "Step 443 : Crossing edge : 20\n",
      "Step 444 : Crossing edge : 20\n",
      "Step 445 : Crossing edge : 20\n",
      "Step 446 : Crossing edge : 22\n",
      "Step 447 : Crossing edge : 26\n",
      "Step 448 : Crossing edge : 40\n",
      "Step 449 : Crossing edge : 22\n",
      "Step 450 : Crossing edge : 20\n",
      "Step 451 : Crossing edge : 22\n",
      "Step 452 : Crossing edge : 27\n",
      "Step 453 : Crossing edge : 20\n",
      "Step 454 : Crossing edge : 22\n",
      "Step 455 : Crossing edge : 20\n",
      "Step 456 : Crossing edge : 17\n",
      "Step 457 : Crossing edge : 20\n",
      "Step 458 : Crossing edge : 23\n",
      "Step 459 : Crossing edge : 20\n",
      "Step 460 : Crossing edge : 40\n",
      "Step 461 : Crossing edge : 26\n",
      "Step 462 : Crossing edge : 20\n",
      "Step 463 : Crossing edge : 26\n",
      "Step 464 : Crossing edge : 25\n",
      "Step 465 : Crossing edge : 20\n",
      "Step 466 : Crossing edge : 20\n",
      "Step 467 : Crossing edge : 23\n",
      "Step 468 : Crossing edge : 21\n",
      "Step 469 : Crossing edge : 25\n",
      "Step 470 : Crossing edge : 20\n",
      "Step 471 : Crossing edge : 26\n",
      "Step 472 : Crossing edge : 20\n",
      "Step 473 : Crossing edge : 20\n",
      "Step 474 : Crossing edge : 20\n",
      "Step 475 : Crossing edge : 20\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-3-4d3360d2e5a6>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m     19\u001b[0m \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mlen\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mIntegerMatrix\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     20\u001b[0m     \u001b[0mgraph\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0maddMultipleEdges\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mIntegerMatrix\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mIntegerMatrix\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mi\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 21\u001b[0;31m \u001b[0mKargerMinCut\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mgraph\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[0;32m<ipython-input-2-12c4cdff3813>\u001b[0m in \u001b[0;36mKargerMinCut\u001b[0;34m(objectGraph)\u001b[0m\n\u001b[1;32m     31\u001b[0m     \u001b[0;31m#for _ in range(1):\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     32\u001b[0m         \u001b[0mobjGraph\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdeepcopy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mobjectGraph\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 33\u001b[0;31m         \u001b[0mcuts\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcrossingedges\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mRandomContractionAlgorithm\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mobjGraph\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     34\u001b[0m         \u001b[0;32mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Step {} : Crossing edge : {}\"\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mformat\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mij\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcrossingedges\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     35\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0mcrossingedges\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0mmin_cut\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-2-12c4cdff3813>\u001b[0m in \u001b[0;36mRandomContractionAlgorithm\u001b[0;34m(objGraph)\u001b[0m\n\u001b[1;32m     12\u001b[0m         \u001b[0;31m#print(\"Random no: {}\".format(randomedgeidx))\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     13\u001b[0m         \u001b[0;31m#print(\"Random edge: {}\".format(objGraph.edges()[randomedgeidx]))\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 14\u001b[0;31m         \u001b[0mobjGraph\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcontractEdge\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mobjGraph\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0medges\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mrandomedgeidx\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     15\u001b[0m         \u001b[0;31m#print(\"Edges: {}\".format(objGraph.edges()))\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     16\u001b[0m         \u001b[0;31m#print(\"Vertices: {}\".format(objGraph.vertices()))\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m<ipython-input-1-12a70ff6a1e5>\u001b[0m in \u001b[0;36mcontractEdge\u001b[0;34m(self, edge)\u001b[0m\n\u001b[1;32m     59\u001b[0m                             \u001b[0;31m#print(\"Comp list-list: {}\".format(list(edge[0]) + list(edge[1])))\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     60\u001b[0m                         \u001b[0;32melif\u001b[0m \u001b[0misinstance\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0medge\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mlist\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;32mand\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0misinstance\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0medge\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mlist\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 61\u001b[0;31m                             \u001b[0mnewedge0\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdeepcopy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0medge\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m     62\u001b[0m                             \u001b[0mnewedge1\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdeepcopy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0medge\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m     63\u001b[0m                             \u001b[0mnewedge0\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mnewedge1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/Users/aishwaya/anaconda2/lib/python2.7/copy.pyc\u001b[0m in \u001b[0;36mdeepcopy\u001b[0;34m(x, memo, _nil)\u001b[0m\n\u001b[1;32m    161\u001b[0m     \u001b[0mcopier\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0m_deepcopy_dispatch\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mget\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mcls\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    162\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0mcopier\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 163\u001b[0;31m         \u001b[0my\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mcopier\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmemo\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    164\u001b[0m     \u001b[0;32melse\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    165\u001b[0m         \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/Users/aishwaya/anaconda2/lib/python2.7/copy.pyc\u001b[0m in \u001b[0;36m_deepcopy_list\u001b[0;34m(x, memo)\u001b[0m\n\u001b[1;32m    228\u001b[0m     \u001b[0mmemo\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mid\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mx\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    229\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0ma\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mx\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 230\u001b[0;31m         \u001b[0my\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mappend\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mdeepcopy\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0ma\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mmemo\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    231\u001b[0m     \u001b[0;32mreturn\u001b[0m \u001b[0my\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    232\u001b[0m \u001b[0md\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0mlist\u001b[0m\u001b[0;34m]\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0m_deepcopy_list\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/Users/aishwaya/anaconda2/lib/python2.7/copy.pyc\u001b[0m in \u001b[0;36mdeepcopy\u001b[0;34m(x, memo, _nil)\u001b[0m\n\u001b[1;32m    149\u001b[0m     \"\"\"\n\u001b[1;32m    150\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 151\u001b[0;31m     \u001b[0;32mif\u001b[0m \u001b[0mmemo\u001b[0m \u001b[0;32mis\u001b[0m \u001b[0mNone\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    152\u001b[0m         \u001b[0mmemo\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;34m{\u001b[0m\u001b[0;34m}\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    153\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "import urllib3\n",
    "http = urllib3.PoolManager()\n",
    "\n",
    "# Test case\n",
    "r1 = http.request('GET', \"https://d18ky98rnyall9.cloudfront.net/_f370cd8b4d3482c940e4a57f489a200b_kargerMinCut.txt?Expires=1560643200&Signature=Drx6FbB0DYJOR8w4DZ2zCG7~DM-H5N898HtVfDi71wRUft8mNweUII0sOu-1tZxwvXUPNFCgYQ4WC9zrNqznKQMDszAACA50OWHc82ZNwC0nTVC8cfcxSYYUrwgJ7ec0Xg2KTnpk-4xLmuv5Lq-teK-tjew4B5mtb1QOxBHN718_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A\")\n",
    "IntegerMatrixStringJoin = r1.data.split('\\r\\n')\n",
    "IntegerMatrixString = []\n",
    "for i in range(len(IntegerMatrixStringJoin)):\n",
    "    IntegerMatrixString.append([IntegerMatrixStringJoin[i]])\n",
    "\n",
    "IntegerMatrix = []\n",
    "for i in range(len(IntegerMatrixString) - 1):\n",
    "    IntegerMatrixString[i] = IntegerMatrixString[i][0].split('\\t')\n",
    "    IntegerMatrixString[i].remove(IntegerMatrixString[i][-1])\n",
    "    IntegerArray = [int(j) for j in IntegerMatrixString[i]]\n",
    "    IntegerMatrix.append(IntegerArray)\n",
    "\n",
    "graph = Graph_UndirectedAdjList()\n",
    "for i in range(len(IntegerMatrix)):\n",
    "    graph.addMultipleEdges(IntegerMatrix[i][0], IntegerMatrix[i][1:])\n",
    "KargerMinCut(graph)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ans:  17"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}