Code for Kruskal.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "compare_dsu = []\n",
    "compare_veb = []\n",
    "compare_fib = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7667\n",
      "7667\n"
     ]
    }
   ],
   "source": [
    "V = None\n",
    "E = None\n",
    "EdgeList = []\n",
    "my_file=open('/home/neil/Documents/IIITH/sem1/APS/CS3000-Project/infile.txt','r')\n",
    "read_data = my_file.readlines()\n",
    "#print(read_data)\n",
    "my_file.close()\n",
    "#print(read_data)\n",
    "E = int(read_data[0])\n",
    "V = int(read_data[1])\n",
    "for i in range(2,3*E+2,3):\n",
    "    u = int(read_data[i])\n",
    "    v = int(read_data[i+1])\n",
    "    w = int(read_data[i+2])\n",
    "    lst=[]\n",
    "    lst.append(w)\n",
    "    lst.append(u)\n",
    "    lst.append(v)\n",
    "    #print(lst)\n",
    "    EdgeList.append(lst)\n",
    "EdgeList.sort(key = lambda x: x[0],reverse=True)\n",
    "print(len(EdgeList))\n",
    "print (E)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "import math\n",
    "import time \n",
    "import random\n",
    "from collections import defaultdict\n",
    "\n",
    "BASE = 2\n",
    "\n",
    "class vEBLeaf(object):\n",
    "    def __init__(self, word_size):\n",
    "        self.word_size = word_size\n",
    "        self.values = [False, False]\n",
    "\n",
    "    def min(self):\n",
    "        for i in range(2):\n",
    "            if self.values[i]:\n",
    "                return i\n",
    "        return None\n",
    "    \n",
    "    def max(self):\n",
    "        for i in range(1, -1, -1):\n",
    "            if self.values[i]:\n",
    "                return i\n",
    "        return None\n",
    "\n",
    "    def insert(self, x):\n",
    "        self.values[x] = True\n",
    "\n",
    "    def delete(self, x):\n",
    "        self.values[x]= False\n",
    "\n",
    "class vEBTree(object):\n",
    "    def __init__(self, word_size):\n",
    "        self.min_ = self.max_ = None\n",
    "        self.word_size =  word_size\n",
    "        self.summary_size = int(self.word_size/2)\n",
    "        self.u = 1<<self.summary_size\n",
    "        self.cluster = [None]*(self.u)\n",
    "        self.mask = self.u - 1\n",
    "        self.summary = vEB.of_size(self.summary_size)\n",
    "\n",
    "    def __contains__(self,x):\n",
    "        if self.min() is None:\n",
    "            return False\n",
    "        elif self.min() == x:\n",
    "            return True\n",
    "        else:\n",
    "            high = self.high(x)\n",
    "            low = self.low(x)\n",
    "            if self.cluster[high] is None:\n",
    "                return False\n",
    "            else:\n",
    "                return low in self.cluster[high]\n",
    "    \n",
    "    def __iter__(self):\n",
    "        if self.min() is None:\n",
    "            return \n",
    "        yield self.min()\n",
    "\n",
    "        current = self.min()\n",
    "        while current != self.max():\n",
    "            current = self.successor(current)\n",
    "            yield current\n",
    "\n",
    "    def high(self, x):\n",
    "        return x>>int(self.summary_size)\n",
    "\n",
    "    def low(self, x):\n",
    "        return x&(self.mask)\n",
    "\n",
    "    def index(self, i, j):\n",
    "        return (i<<self.summary_size) | j\n",
    "\n",
    "    def insert(self, x):\n",
    "        if self.min() is None:\n",
    "            self.min_ = self.max_ = x\n",
    "            return\n",
    "        if x == self.min():\n",
    "            return\n",
    "        if x<self.min():\n",
    "            self.min_, x = x, self.min_\n",
    "        if x>self.max():\n",
    "            self.max_ = x\n",
    "\n",
    "        cluster_index = x>>int(self.summary_size)\n",
    "        element_index = x&(self.mask)\n",
    "#         clustr = self.cluster[cluster_index]\n",
    "        if self.cluster[cluster_index] is None:\n",
    "             self.cluster[cluster_index] = vEB.of_size(self.summary_size)\n",
    "\n",
    "        if self.cluster[cluster_index].min() is None:\n",
    "            self.summary.insert(cluster_index)\n",
    "\n",
    "        self.cluster[cluster_index].insert(element_index)\n",
    "\n",
    "    def max(self):\n",
    "        return self.max_\n",
    "    def min(self):\n",
    "        return self.min_\n",
    "    \n",
    "    def delete(self, x):\n",
    "        if self.min() is None or x<self.min():\n",
    "            return\n",
    "            \n",
    "        if x == self.min():\n",
    "            if self.summary is None or self.summary.min() is None:\n",
    "                self.min_ = self.max_ = None\n",
    "                return\n",
    "            cluster_index = self.summary.min()\n",
    "            element_index = self.cluster[cluster_index].min()\n",
    "\n",
    "            x = self.min_ = (cluster_index<<self.summary_size) | element_index\n",
    "\n",
    "        cluster_index = x>>int(self.summary_size)\n",
    "        element_index = x&(self.mask)\n",
    "#         clustr = self.cluster[cluster_index]\n",
    "\n",
    "        if self.cluster[cluster_index] is None:\n",
    "            return \n",
    "        self.cluster[cluster_index].delete(element_index)\n",
    "\n",
    "        if self.cluster[cluster_index].min() is None:\n",
    "            self.cluster[cluster_index]=None\n",
    "            self.summary.delete(cluster_index)\n",
    "\n",
    "        if x==self.max():\n",
    "            \n",
    "            if self.summary.max() is None:\n",
    "                self.max_ = self.min()\n",
    "            else:\n",
    "                cluster_index = self.summary.max()\n",
    "                element_index = self.cluster[cluster_index].max()\n",
    "                self.max_ = (cluster_index<<self.summary_size) | element_index\n",
    "\n",
    "class vEB(object):\n",
    "    @classmethod\n",
    "    def of_size(cls, word_size):\n",
    "        return vEBLeaf(word_size) if word_size<BASE else vEBTree(word_size)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.36895600000000073\n",
      "0.15292200000000022\n",
      "2403701840554\n"
     ]
    }
   ],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "nodes = defaultdict(list)\n",
    "class edge:\n",
    "    def __init__(self,u,v):\n",
    "        self.u = u\n",
    "        self.v = v\n",
    "class UnionFind:\n",
    "    def __init__(self, N):\n",
    "        self.rank = [0 for i in range(N+1)]\n",
    "        self.p = [0 for i in range(N+1)]\n",
    "        for i in range(N+1):\n",
    "            self.p[i] = i\n",
    "\n",
    "    def findSet(self, i):\n",
    "        if (self.p[i] == int(i)):\n",
    "            return i\n",
    "        else:\n",
    "            self.p[i] = self.findSet(self.p[i])\n",
    "            return self.p[i]\n",
    "\n",
    "    def isSameSet(self, i, j):\n",
    "        return self.findSet(i) == self.findSet(j)\n",
    "\n",
    "    def unionSet(self, i, j):\n",
    "        if not self.isSameSet(i, j):\n",
    "            x = self.findSet(i)\n",
    "            y = self.findSet(j)\n",
    "            if self.rank[x] > self.rank[y] :\n",
    "                self.p[y] = x\n",
    "            else:\n",
    "                self.p[x] = y\n",
    "                if self.rank[x] == self.rank[y] :\n",
    "                    self.rank[y] += 1\n",
    "\n",
    "def kruskal_veb(h: vEB):\n",
    "    time_start = time.clock()\n",
    "    mst_cost = 0\n",
    "    global EdgeList\n",
    "    UF = UnionFind(V)\n",
    "    for i in range(E):\n",
    "        # x, y, z = EdgeList[i]\n",
    "        temp = h.min()\n",
    "        y=0\n",
    "        z=0\n",
    "        if nodes[temp] and len(nodes[temp])>0:\n",
    "            tmp = nodes[temp][0]\n",
    "            nodes[temp].pop(0)\n",
    "            #nodes.pop(temp,None)\n",
    "            #print(tmp[0])\n",
    "            y = tmp.u\n",
    "            z = tmp.v\n",
    "            #tmp.pop(0)\n",
    "            #tmp.pop(0)\n",
    "            #print(tmp)\n",
    "            #print (y)\n",
    "            #print (z)\n",
    "            if len(nodes[temp])==0:\n",
    "                h.delete(temp)\n",
    "                cnt=0\n",
    "        #print(\"In Kruskal {0}, {1}\".format(y,z))\n",
    "        if not UF.isSameSet(y, z):\n",
    "            #print(mst_cost)\n",
    "            mst_cost += temp\n",
    "            UF.unionSet(y,z)\n",
    "            #print(mst_cost)\n",
    "            #print(temp)\n",
    "    time_elapsed = (time.clock() - time_start)\n",
    "    print(time_elapsed)\n",
    "    compare_veb.append((time_elapsed, E))\n",
    "    return mst_cost\n",
    "\n",
    "\n",
    "if __name__==\"__main__\":\n",
    "    #run your code\n",
    "    global compare_veb\n",
    "    global V\n",
    "    global E\n",
    "    global EdgeList\n",
    "    global compare\n",
    "    ts = time.clock()\n",
    "    h = vEB.of_size(32)\n",
    "    for i in range(E):\n",
    "        w, u, v = EdgeList[i]\n",
    "        h.insert(w)\n",
    "        nodes[w].append(edge(u,v))\n",
    "#         nodes[w].append(u)\n",
    "#         nodes[w].append(v)\n",
    "    print(time.clock()-ts)\n",
    "    print(kruskal_veb(h))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2403701840554\n",
      "0.08616699999999966\n"
     ]
    }
   ],
   "source": [
    "class UnionFind:\n",
    "    def __init__(self, N):\n",
    "        self.rank = [0 for i in range(N+1)]\n",
    "        self.p = [0 for i in range(N+1)]\n",
    "        for i in range(N+1):\n",
    "            self.p[i] = i\n",
    "\n",
    "    def findSet(self, i):\n",
    "        if (self.p[i] == int(i)):\n",
    "            #print(i)\n",
    "            return i\n",
    "        else:\n",
    "            self.p[i] = self.findSet(self.p[i])\n",
    "            return self.p[i]\n",
    "\n",
    "    def isSameSet(self, i, j):\n",
    "        return self.findSet(i) == self.findSet(j)\n",
    "\n",
    "    def unionSet(self, i, j):\n",
    "        if not self.isSameSet(i, j):\n",
    "            x = self.findSet(i)\n",
    "            y = self.findSet(j)\n",
    "            if self.rank[x] > self.rank[y] :\n",
    "                self.p[y] = x\n",
    "            else:\n",
    "                self.p[x] = y\n",
    "                if self.rank[x] == self.rank[y] :\n",
    "                    self.rank[y] += 1\n",
    "\n",
    "def mergeSort(nlist):\n",
    "    #print(\"Splitting \",nlist)\n",
    "    if len(nlist)>1:\n",
    "        mid = len(nlist)//2\n",
    "        lefthalf = nlist[:mid]\n",
    "        righthalf = nlist[mid:]\n",
    "\n",
    "        mergeSort(lefthalf)\n",
    "        mergeSort(righthalf)\n",
    "        i=j=k=0       \n",
    "        while i < len(lefthalf) and j < len(righthalf):\n",
    "            if lefthalf[i][0] < righthalf[j][0]:\n",
    "                nlist[k]=lefthalf[i]\n",
    "                i=i+1\n",
    "            else:\n",
    "                nlist[k]=righthalf[j]\n",
    "                j=j+1\n",
    "            k=k+1\n",
    "\n",
    "        while i < len(lefthalf):\n",
    "            nlist[k]=lefthalf[i]\n",
    "            i=i+1\n",
    "            k=k+1\n",
    "\n",
    "        while j < len(righthalf):\n",
    "            nlist[k]=righthalf[j]\n",
    "            j=j+1\n",
    "            k=k+1\n",
    "            \n",
    "def kruskal_sort():\n",
    "    mst_cost = 0\n",
    "    global V\n",
    "    global E\n",
    "    global EdgeList\n",
    "    UF = UnionFind(V)\n",
    "    for i in range(E):\n",
    "        x, y, z = EdgeList[i]\n",
    "        #print(\"In Kruskal {0}, {1}\".format(y,z))\n",
    "        if not UF.isSameSet(y, z):\n",
    "            #print(mst_cost)\n",
    "            mst_cost += x\n",
    "            UF.unionSet(y,z)\n",
    "            #print(mst_cost)\n",
    "            #print(x)\n",
    "    return mst_cost\n",
    "\n",
    "\n",
    "if __name__==\"__main__\":\n",
    "    time_start = time.clock()\n",
    "    global compare_dsu\n",
    "    global EdgeList\n",
    "    global V\n",
    "    global E\n",
    "    mergeSort(EdgeList)\n",
    "    #print(EdgeList)\n",
    "    print (kruskal_sort())\n",
    "    time_elapsed = (time.clock() - time_start)\n",
    "    print(time_elapsed)\n",
    "    compare_dsu.append((time_elapsed, E))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "## Fib Heap\n",
    "class FibHeap:\n",
    "    def __init__(self):\n",
    "        self.n = 0\n",
    "        self.min = None\n",
    "        self.root = []\n",
    "\n",
    "## Fib Heap intenalTree\n",
    "class Node:\n",
    "    def __init__(self, val, x: int, y: int):\n",
    "        self.degree = 0\n",
    "        self.parent = None\n",
    "        self.child = []\n",
    "        self.mark = False\n",
    "        self.key = val\n",
    "        self.right = self\n",
    "        self.x = x\n",
    "        self.y = y\n",
    "\n",
    "def makeNode():\n",
    "    return Node()\n",
    "\n",
    "\n",
    "def makeFibHeap():\n",
    "    return FibHeap()\n",
    "\n",
    "##Insert\n",
    "def FibHeapInsert(h: FibHeap, node: Node):\n",
    "    if(h.min == None):\n",
    "        h.root = [node]\n",
    "        h.min = node\n",
    "    else:\n",
    "        h.root.append(node)\n",
    "        h.root[len(h.root)-2].right = node\n",
    "        h.root[len(h.root)-1].right = h.root[0]\n",
    "        if(node.key < h.min.key):\n",
    "            h.min = node\n",
    "    h.n = h.n + 1\n",
    "#     print(\"printing root list\")\n",
    "#     for x in h.root:\n",
    "#         print(x.key)\n",
    "\n",
    "def D(n: int):\n",
    "    #     print(\"log value = {0}\".format(int(math.log2(n))+1))\n",
    "    return int(math.log2(n))+1\n",
    "\n",
    "def FibHeapLink(h: FibHeap, y, x):\n",
    "    #     print(\"In link, root size {0}\".format(len(h.root)))\n",
    "    #     print(\"In link, x = {0}, y = {1}\".format(x.key, y.key))\n",
    "    h.root.remove(y)\n",
    "    x.child.append(y)\n",
    "    x.degree = x.degree+1\n",
    "    y.mark = False\n",
    "#     print(\"In link, abcd root size {0}\".format(len(h.root)))\n",
    "\n",
    "\n",
    "def consolidate(h: FibHeap):\n",
    "    A = [None for i in range(0,D(h.n)+1)]\n",
    "    #     print(\"In consolodate, root size {0}\".format(len(h.root)))\n",
    "    #     for w in h.root:\n",
    "    #         print(\"Test consolodate, w= {0}\".format(w.key))\n",
    "    #         print(\"Test consolodate, w= {0}\".format(w.degree))\n",
    "    #     for i in range(0,len(h.root)):\n",
    "    i = 0\n",
    "    while(i < len(h.root)):\n",
    "        #         print(\"In beginning i = {0}, root len {1}\".format(i, len(h.root)))\n",
    "        w = h.root[i]\n",
    "        #         print(\"In consolodate, w= {0}\".format(w.key))\n",
    "        x = w\n",
    "        d = x.degree\n",
    "        #         print(\"x degree = {0}\".format(x.degree))\n",
    "        while not A[d] == None:\n",
    "            #             print(\"In while x degree = {0}\".format(x.degree))\n",
    "            y = A[d]\n",
    "            if x.key > y.key:\n",
    "                temp = x\n",
    "                x = y\n",
    "                y = temp\n",
    "            FibHeapLink(h, y, x)\n",
    "            A[d] = None\n",
    "            d = d+1\n",
    "            i = i-1\n",
    "        A[d] = x\n",
    "        i = i+1\n",
    "    for w in A:\n",
    "        h.min = None\n",
    "    for i in range(0, D(h.n)+1):\n",
    "        if not A[i] == None:\n",
    "            if h.min == None:\n",
    "                h.root = [A[i]]\n",
    "                h.min = A[i]\n",
    "            else:\n",
    "                h.root.append(A[i])\n",
    "                if(A[i].key < h.min.key):\n",
    "                    h.min = A[i]\n",
    "\n",
    "\n",
    "##Extract min\n",
    "def FibExtractMin(h: FibHeap):\n",
    "    z = h.min\n",
    "    if(not z == None):\n",
    "        for x in z.child:\n",
    "            h.root.append(x)\n",
    "            x.parent = None\n",
    "        h.root.remove(z)\n",
    "        if(z == z.right):\n",
    "            h.min = None\n",
    "        else:\n",
    "            h.min = z.right\n",
    "            #             print(\"before consolodate {0}\".format(h.min.key))\n",
    "            #             print(\"before consolodate root size {0}\".format(len(h.root)))\n",
    "            consolidate(h)\n",
    "        #             print(\"after consolodate root size {0}\".format(len(h.root)))\n",
    "        h.n = h.n - 1\n",
    "    return z"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.11650500000000008\n",
      "2403701840554\n"
     ]
    }
   ],
   "source": [
    "class UnionFind:\n",
    "    def __init__(self, N):\n",
    "        self.rank = [0 for i in range(N+1)]\n",
    "        self.p = [0 for i in range(N+1)]\n",
    "        for i in range(N+1):\n",
    "            self.p[i] = i\n",
    "\n",
    "    def findSet(self, i: int):\n",
    "        if (self.p[i] == i):\n",
    "            return i\n",
    "        else:\n",
    "            self.p[i] = self.findSet(self.p[i])\n",
    "            return self.p[i]\n",
    "\n",
    "    def isSameSet(self, i, j):\n",
    "        return self.findSet(i) == self.findSet(j)\n",
    "\n",
    "    def unionSet(self, i, j):\n",
    "        if not self.isSameSet(i, j):\n",
    "            x = self.findSet(i)\n",
    "            y = self.findSet(j)\n",
    "            if self.rank[x] > self.rank[y] :\n",
    "                self.p[y] = x\n",
    "            else:\n",
    "                self.p[x] = y\n",
    "                if self.rank[x] == self.rank[y] :\n",
    "                    self.rank[y] += 1\n",
    "\n",
    "def Kruskal_fib(h: FibHeap):\n",
    "    time_start = time.clock()\n",
    "    global compare_fib\n",
    "    mst_cost = 0\n",
    "    global EdgeList\n",
    "    UF = UnionFind(V)\n",
    "    for i in range(E):\n",
    "        # x, y, z = EdgeList[i]\n",
    "        temp = FibExtractMin(h)\n",
    "        x = temp.key\n",
    "        y = temp.x\n",
    "        z = temp.y\n",
    "        #print(\"In Kruskal {0}, {1}\".format(y,z))\n",
    "        if not UF.isSameSet(y, z):\n",
    "            mst_cost += x\n",
    "            UF.unionSet(y,z)\n",
    "    time_elapsed = (time.clock() - time_start)\n",
    "    print(time_elapsed)\n",
    "    compare_fib.append((time_elapsed, E))\n",
    "    return mst_cost\n",
    "\n",
    "if __name__==\"__main__\":\n",
    "    h = makeFibHeap()\n",
    "    global V\n",
    "    global E\n",
    "    global EdgeList\n",
    "    for i in range(E):\n",
    "        w, u, v = EdgeList[i]\n",
    "        FibHeapInsert(h, Node(w, u, v))\n",
    "    print(Kruskal_fib(h))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(0.09048599999999851, 7667)]\n",
      "[(0.689781, 7667)]\n",
      "[(0.11240799999999851, 7667)]\n"
     ]
    }
   ],
   "source": [
    "print (compare_dsu)\n",
    "print (compare_veb)\n",
    "print (compare_fib)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "# compare_dsu.sort(key = lambda x: x[1])\n",
    "# compare_veb.sort(key = lambda x: x[1])\n",
    "# compare_fib.sort(key = lambda x: x[1])\n",
    "# with open('compare_dsu_rsorted.txt', 'w') as f:\n",
    "#     for x,y in compare_dsu:\n",
    "#         f.write(\"{0} {1}\\n\".format(x,y))\n",
    "# with open('compare_veb_rsorted.txt', 'w') as f:\n",
    "#     for x,y in compare_veb:\n",
    "#         f.write(\"{0} {1}\\n\".format(x,y))\n",
    "# with open('compare_fib_rsorted.txt', 'w') as f:\n",
    "#     for x,y in compare_fib:\n",
    "#         f.write(\"{0} {1}\\n\".format(x,y))\n",
    "# len(compare_dsu)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.legend.Legend at 0x7f855311a400>"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAY4AAAEKCAYAAAAFJbKyAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4xLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvDW2N/gAAIABJREFUeJzt3Xt4VdWd//H3x4BctSA3FVAoQ7ECEiWATlFh8ILagqi1UOq1FapQf+qUX2GmgmKdx1urtdoLVmxtrXiZqsxURZ1CbR0pBEQtCCVcHIOORFCpUhThO3+cTTxgQs4OOTlJ/Lye5zzsvfbae38XJ+TLWmtfFBGYmZnlar9CB2BmZo2LE4eZmaXixGFmZqk4cZiZWSpOHGZmlooTh5mZpeLEYWZmqThxmJlZKk4cZmaWSrNCB5APHTt2jB49ehQ6DDOzRmXJkiVvRUSnmuo1ycTRo0cPSktLCx2GmVmjIunVXOp5qMrMzFJx4jAzs1ScOMzMLJUmOcdhZvm3fft2ysvL2bZtW6FDsZRatmxJt27daN68ea32d+Iws1opLy/ngAMOoEePHkgqdDiWo4hg06ZNlJeX07Nnz1odw0NVZlYr27Zto0OHDk4ajYwkOnTosE89RScOM6s1J43GaV+/NycOMzNLxYnDzBqtoqIiiouL6du3LwMGDOD73/8+O3fuBGDr1q2MHz+e/v37069fP4YOHcp7773H+vXr6dev327Hueaaa7jlllsK0YRGyZPjZtZotWrVimXLlgGwceNGvvrVr7JlyxauvfZafvjDH9KlSxdefvllAFatWlXrq4hsd+5xmFmT0LlzZ2bNmsUdd9xBRPDGG2/QtWvXyu19+vShRYsWBYyw6XCPw8z22bX/sZwVr2+p02MeeeiBzPhS31T7fPazn2XHjh1s3LiRiy++mFNOOYWHH36YESNGcMEFF9C7d+86jfHTyj0OM2uSiouLWbt2LVOmTGHz5s0MGjSIV155pdorinyFWO7c4zCzfZa2Z5Ava9eupaioiM6dOwPQtm1bzjrrLM466yz2228/Hn/8cSZOnMjbb7+9236bN2+u9c1wn0bucZhZk1BRUcE3v/lNJk+ejCSee+65ygTx4YcfsmLFCg4//HDatm3LIYccwu9//3sgkzSefPJJhg4dWsjwGxX3OMys0fr73/9OcXEx27dvp1mzZpx33nlcddVVAKxZs4ZLL72UiGDnzp2cccYZnH322QDce++9TJo0qbLujBkz6NWrV8Ha0dg4cZhZo7Vjx45qt51//vmcf/75VW478sgjmT9/fr7CavI8VGVmZqnkNXFIulLSckl/kXS/pJaSekr6s6QySQ9I2j+p2yJZL0u298g6zrSkfJWkU/MZs5mZ7V3eEoekrsDlQElE9AOKgLHAjcCtEfEPwNvA15Ndvg68nZTfmtRD0pHJfn2BkcCPJRXlK24zM9u7fA9VNQNaSWoGtAbeAP4JeDjZ/kvgzGR5dLJOsn2EMhdWjwbmRMQHEbEOKAMG5zluMzOrRt4SR0RsAG4B/odMwngXWAK8ExEfJdXKgV3PBOgKvJbs+1FSv0N2eRX7VJI0QVKppNKKioq6b5CZmQH5HapqT6a30BM4FGhDZqgpLyJiVkSURERJp06d8nUaM7NPvXwOVZ0ErIuIiojYDvwW+ALQLhm6AugGbEiWNwDdAZLtnwE2ZZdXsY+ZfUoNHz6cefPm7VZ22223cemll7J+/XpatWpFcXFx5efee+8FoEePHvTv35/i4mL69+/PY4899oljDxkyhOLiYg477DA6depUeYz169dX7n/UUUdx4okn8uqrr1but+sx77s+N9xwAwDDhg2jT58+leXnnHNOHv9m6kFE5OUDDAGWk5nbEJn5i28BDwFjkzo/BS5LlicBP02WxwIPJst9gReBFmR6L2uBor2de+DAgWFm+bVixYqCnv9nP/tZXHjhhbuVDRkyJP7whz/EunXrom/fvlXud/jhh0dFRUVERKxcuTIOO+ywas9xzz33xKRJk6rdf/r06fGNb3yjclubNm2qPM6JJ54YixcvrrlR9aiq7w8ojRx+v+dzjuPPZCa5lwIvk+ndzAK+A1wlqYzMHMbdyS53Ax2S8quAqclxlgMPAiuAJ4FJEVH9XT9m9qlwzjnn8Lvf/Y4PP/wQgPXr1/P6669z/PHH53yMLVu20L59+1rHcNxxx7Fhw6dvACSvd45HxAxgxh7Fa6niqqiI2AZ8uZrjXA9cX+cBmlndeGIq/O/LdXvMg/vDaTdUu/mggw5i8ODBPPHEE4wePZo5c+Zw7rnnVj7lds2aNRQXF1fW/9GPflSZVIYPH05EsHbtWh588MFah/jkk09y5plnVq7vegTKLtOmTeMrX/kKAOPHj6dVq1YAnHzyydx88821Pm+h+ZEjZtZojRs3jjlz5lQmjrvvvrtyW69evSrfDrin+fPn07FjR9asWcOIESMYNmwYbdu2zfm8w4cPZ/PmzbRt25brrruusjz7jYR7uu+++ygpKcn5HA2ZE4eZ7bu99AzyafTo0Vx55ZUsXbqUrVu3MnDgwFT79+rViy5durBixQoGD8799rD58+fTrl07xo8fz4wZM/jBD36QNvRGzc+qMrNGq23btgwfPpyLL76YcePGpd5/48aNrFu3jsMPPzz1vs2aNeO2227j3nvvZfPmzan3b8zc4zCzRm3cuHGMGTOGOXPm7Fa+5xzHxRdfzOWXXw5khpqKiorYvn07N9xwA126dKnVuQ855BDGjRvHnXfeydVXX/2JOY6RI0dWXpKbPcfRsWNHnnnmmVqdsyFQ5gqspqWkpCRKS0sLHYZZk/bKK6/w+c9/vtBhWC1V9f1JWhIRNU7EeKjKzMxSceIwM7NUnDjMzCwVJw4zM0vFicPMzFJx4jAzs1ScOMys0drzMebr16+ntLS08n6Na665hltuuaXAUX5s+vTpVd6/ceGFF/Lwww/vVpbmESj1zTcAmlmjVdWzoXr06NFgnwk1c+bMQodQJ9zjMLMmZcGCBXzxi1+sXH/xxRc57rjj6N27N3fddReQeQ/RlClT6NevH/379+eBBx6o3HfYsGGcc845HHHEEYwfP37X+4WYOXMmgwYNol+/fkyYMKGyvKysjJNOOokBAwZwzDHHsGbNGgBuvPFG+vfvz4ABA5g6dSpQdc8iFzfffDODBg3iqKOOYsaMjx84fuaZZzJw4ED69u3LrFmzKsvbtm3LlVdeSd++fRkxYgR1/Tpt9zjMbJ/duOhGVm5eWafHPOKgI/jO4O/stU72Iz569uzJI4888ok6L730EgsXLuT999/n6KOP5owzzuD5559n2bJlvPjii7z11lsMGjSIE044AYAXXniB5cuXc+ihh/KFL3yB5557jqFDhzJ58mSmT58OwHnnncd//ud/8qUvfYnx48czdepUxowZw7Zt29i5cydPPPEEjz32GH/+859p3bp1Ts+ymjJlCt/73vc+Uf7UU0+xevVqFi1aREQwatQonn32WU444QRmz57NQQcdxN///ncGDRrE2WefTYcOHXj//fcpKSnh1ltvZebMmVx77bXccccdNcaQKycOM2u09vYY811Gjx5Nq1ataNWqFcOHD2fRokX86U9/Yty4cRQVFdGlSxdOPPFEFi9ezIEHHsjgwYPp1q0bQOW8ydChQ5k/fz433XQTW7duZfPmzfTt25dhw4axYcMGxowZA0DLli0BeOaZZ7joooto3bo1kHl3SE1uvvnm3V4pu2uO46mnnuKpp57i6KOPBuC9995j9erVnHDCCdx+++2VyfK1115j9erVdOjQgf3226/yPSBf+9rXOOuss3L+O81F3hKHpD7AA1lFnwWmA/PJvDK2LbAeGB8RW5J9pgFfB3YAl0fEvKR8JPBDoAj4eUQU5hnOZlalmnoGhbTrxU7Vre+pRYsWlctFRUV89NFHbNu2jcsuu4zS0lK6d+/ONddcw7Zt2/IS754igmnTpjFx4sTdyhcsWMAzzzzD888/T+vWrRk2bFi1MdXU5rTy+erYVRFRHBHFwEBgK/AI8HNgakT0T9anAEg6ksy7xvsCI4EfSyqSVATcCZwGHAmMS+qamdXoscceY9u2bWzatIkFCxYwaNAgjj/+eB544AF27NhBRUUFzz777F7fx7HrF3LHjh157733KucpDjjgALp168ajjz4KwAcffMDWrVs5+eSTueeee9i6dSvAPj12/dRTT2X27Nm89957AGzYsIGNGzfy7rvv0r59e1q3bs3KlStZuHBh5T47d+6sjPE3v/kNQ4cOrfX5q1JfQ1UjgDUR8aqkzwHPJuVPA/OAq4HRwJyI+ABYl7x7fNc3WRYRawEkzUnqrqin2M2sETvqqKMYPnw4b731FldffTWHHnooY8aM4fnnn2fAgAFI4qabbuLggw9m5cqq52natWvHJZdcQr9+/Tj44IMZNGhQ5bZf/epXTJw4kenTp9O8eXMeeughRo4cybJlyygpKWH//ffn9NNP59/+7d9qFf8pp5zCK6+8wnHHHQdkhrB+/etfM3LkSH7605/y+c9/nj59+nDsscdW7tOmTRsWLVrE9773PTp37lw5+V9X6uWx6pJmA0sj4g5J/w3cFBGPSroKuDYiDpB0B7AwIn6d7HM38ERyiJER8Y2k/DxgSERMru58fqy6Wf75seoNV9u2bSt7KNVp0I9Vl7Q/MAp4KCm6GLhM0hLgAODDOjrPBEmlkkrr+tIzMzP7WH0MVZ1GprfxJkBErAROAUiGrc5I6m0Aumft1y0pYy/llSJiFjALMj2OOozfzKxRqam3sa/q4wbAccD9u1YkdU7+3A/4LpkrrADmAmMltZDUE+gNLAIWA70l9Ux6L2OTumZWYE3xDaKfBvv6veU1cUhqA5wM/DareJykvwIrgdeBewAiYjnwIJlJ7yeBSRGxIyI+AiaTmUR/BXgwqWtmBdSyZUs2bdrk5NHIRASbNm2qvOekNvzOcTOrle3bt1NeXl5v9zNY3WnZsiXdunWjefPmu5XnOjnuO8fNrFaaN29Oz549Cx2GFYAfcmhmZqk4cZiZWSpOHGZmlooTh5mZpeLEYWZmqThxmJlZKk4cZmaWihOHmZml4sRhZmapOHGYmVkqThxmZpaKE4eZmaXixGFmZqk4cZiZWSpOHGZmlooTh5mZpZK3xCGpj6RlWZ8tkq6QVCxpYVJWKmlwUl+SbpdUJuklScdkHesCSauTzwX5itnMzGqWtzcARsQqoBhAUhGwAXgEuAu4NiKekHQ6cBMwDDgN6J18hgA/AYZIOgiYAZQAASyRNDci3s5X7GZmVr36GqoaAayJiFfJ/PI/MCn/DPB6sjwauDcyFgLtJB0CnAo8HRGbk2TxNDCynuI2M7M91Nc7x8cC9yfLVwDzJN1CJnH9Y1LeFXgta5/ypKy6cjMzK4C89zgk7Q+MAh5Kii4FroyI7sCVwN11dJ4JyZxJaUVFRV0c0szMqlAfQ1WnAUsj4s1k/QLgt8nyQ8DgZHkD0D1rv25JWXXlu4mIWRFREhElnTp1qsPwzcwsW30kjnF8PEwFmTmNE5PlfwJWJ8tzgfOTq6uOBd6NiDeAecApktpLag+ckpSZmVkB5HWOQ1Ib4GRgYlbxJcAPJTUDtgETkvLHgdOBMmArcBFARGyWdB2wOKk3MyI25zNuMzOrniKi0DHUuZKSkigtLS10GGZmjYqkJRFRUlM93zluZmapOHGYmVkqThxmZpaKE4eZmaXixGFmZqk4cZiZWSpOHGZmlooTh5mZpeLEYWZmqThxmJlZKk4cZmaWihOHmZml4sRhZmapOHGYmVkqThxmZpaKE4eZmaXixGFmZqnklDgkfVnSAcnydyX9VtIxNezTR9KyrM8WSVdIeiCrbL2kZVn7TJNUJmmVpFOzykcmZWWSpta2sWZmtu9yfef41RHxkKShwEnAzcBPgCHV7RARq4BiAElFwAbgkYi4bVcdSd8H3k2WjwTGAn2BQ4FnJH0uqXonmXeXlwOLJc2NiBU5t9LMzOpMrkNVO5I/zwBmRcTvgP1TnGcEsCYiXt1VIEnAucD9SdFoYE5EfBAR64AyYHDyKYuItRHxITAnqWtmZgWQa+LYIOlnwFeAxyW1SLEvZHoS9+9RdjzwZkSsTta7Aq9lbS9PyqorNzOzAsj1l/+5wDzg1Ih4BzgImJLLjpL2B0YBD+2xaRyfTCa1JmmCpFJJpRUVFXV1WDMz20NOiSMitgIbgaFJ0UfA6ur32M1pwNKIeHNXgaRmwFnAA1n1NgDds9a7JWXVle8Z46yIKImIkk6dOuUYmpmZpZXrVVUzgO8A05Ki5sCvczxHVT2Lk4CVEVGeVTYXGCuphaSeQG9gEbAY6C2pZ9J7GZvUNTOzAsj1qqoxwNHAUoCIeH3X5bl7I6kNmauhJu6x6RNzHhGxXNKDwAoyPZpJEbEjOc5kMkNlRcDsiFieY9xmZlbHck0cH0ZESAqoTAg1ioj3gQ5VlF9YTf3rgeurKH8ceDzHWM3MLI9ynRx/MLmqqp2kS4BngLvyF5aZmTVUOfU4IuIWSScDW4A+wPSIeDqvkZmZWYOU61AVSaJwsjAz+5TLKXFI+hsQexS/C5QC/xwRa+s6MDMza5hy7XHcRuaO7d8AInNVVC8yV1nNBoblIzgzM2t4cp0cHxURP4uIv0XEloiYReYu8geA9nmMz8zMGphcE8dWSedK2i/5nAtsS7btOYRlZmZNWK6JYzxwHpnHjryZLH9NUitgcp5iMzOzBijXy3HXAl+qZvOf6i4cMzNr6PaaOCT9iL0MRUXE5XUekZmZNWg1DVWVAkuAlsAxZJ6Iu5rMm/3SvMjJzMyaiL32OCLilwCSLgWGRsRHyfpPgT/mPzwzM2tocp0cbw8cmLXeFl+Ga2b2qZTrDYA3AEslLSBzA+AJwDV5isnMzBqwXHscvwCmA0cB/w6cCLySp5jMzKwBy7XH8WNgJ9AqIuZKak8mgQzKW2RmZtYg5Zo4hkTEMZJeAIiIt5PXuJqZ2adMrkNV2yUVkdzTIakTmR5ItST1kbQs67NF0hXJtm9JWilpuaSbsvaZJqlM0ipJp2aVj0zKyiRNTd1KMzOrM7n2OG4HHgE6S7oeOAf47t52iIhVZO73IEk6G4BHJA0HRgMDIuIDSZ2TOkeSeepuX+BQ4BlJn0sOdyeZd5eXA4slzY2IFbk308zM6kqujxy5T9ISYASZq6rOjIg0k+MjgDUR8aqkm4EbIuKD5NgbkzqjgTlJ+TpJZcDgZFvZrnd+SJqT1HXiMDMrgDRvAFwJrKzlecYC9yfLnwOOT3ou24BvR8RioCuwMGuf8qQM4LU9yofseQJJE4AJAIcddlgtwzQzs5rkOsdRa8kk+ijgoaSoGXAQcCwwBXhQkvb1PBExKyJKIqKkU6dO+3o4MzOrRs49jn1wGrA0It5M1suB30ZEAIsk7QQ6kpkD6Z61X7ekjL2Um5lZPct7jwMYx8fDVACPAsMBksnv/YG3gLnAWEktJPUEegOLgMVAb0k9k97L2KSumZkVQF57HJLakLkaamJW8WxgtqS/AB8CFyS9j+WSHiQz6f0RMCkidiTHmQzMA4qA2RGxPJ9xm5lZ9ZT5nd20lJSURGlpaaHDMDNrVCQtiYiSmurVx1CVmZk1IU4cZmaWihOHmZml4sRhZmapOHGYmVkqThxmZpaKE4eZmaXixGFmZqk4cZiZWSpOHGZmlooTh5mZpeLEYWZmqThxmJlZKk4cZmaWihOHmZml4sRhZmap5C1xSOojaVnWZ4ukKyRdI2lDVvnpWftMk1QmaZWkU7PKRyZlZZKm5itmMzOrWd5eHRsRq4BiAElFwAbgEeAi4NaIuCW7vqQjybxPvC9wKPBM8k5ygDvJvIK2HFgsaW5ErMhX7GZmVr28vnM8ywhgTUS8Kqm6OqOBORHxAbBOUhkwONlWFhFrASTNSeo6cZiZFUB9zXGMBe7PWp8s6SVJsyW1T8q6Aq9l1SlPyqorNzOzAsh74pC0PzAKeCgp+gnQi8ww1hvA9+voPBMklUoqraioqItDmplZFeqjx3EasDQi3gSIiDcjYkdE7ATu4uPhqA1A96z9uiVl1ZXvJiJmRURJRJR06tQpD80wMzOon8QxjqxhKkmHZG0bA/wlWZ4LjJXUQlJPoDewCFgM9JbUM+m9jE3qmplZAeR1clxSGzJXQ03MKr5JUjEQwPpd2yJiuaQHyUx6fwRMiogdyXEmA/OAImB2RCzPZ9xmZlY9RUShY6hzJSUlUVpaWugwzMwaFUlLIqKkpnq+c9zMzFJx4jAzs1ScOMzMLBUnDjMzS8WJw8zMUnHiMDOzVJw4zMwsFScOMzNLxYnDzMxSceIwM7NUnDjMzCwVJw4zM0vFicPMzFJx4jAzs1ScOMzMLBUnDjMzS8WJw8zMUslb4pDUR9KyrM8WSVdkbf9nSSGpY7IuSbdLKpP0kqRjsupeIGl18rkgXzGbmVnN8vbO8YhYBRQDSCoCNgCPJOvdgVOA/8na5TSgd/IZAvwEGCLpIGAGUELmPeVLJM2NiLfzFbuZmVWvvoaqRgBrIuLVZP1W4P+TSQS7jAbujYyFQDtJhwCnAk9HxOYkWTwNjKynuM3MbA/1lTjGAvcDSBoNbIiIF/eo0xV4LWu9PCmrrtzMzAogb0NVu0jaHxgFTJPUGvgXMsNUdX2eCcAEgMMOO6yuD29mZon66HGcBiyNiDeBXkBP4EVJ64FuwFJJB5OZA+metV+3pKy68t1ExKyIKImIkk6dOuWlIWZmVj+JYxzJMFVEvBwRnSOiR0T0IDPsdExE/C8wFzg/ubrqWODdiHgDmAecIqm9pPZkeivz6iFuMzOrQl6HqiS1AU4GJuZQ/XHgdKAM2ApcBBARmyVdByxO6s2MiM15CNfMzHKQ18QREe8DHfayvUfWcgCTqqk3G5hd1/GZmVl6vnPczMxSceIwM7NUnDjMzCwVJw4zM0vFicPMzFJx4jAzs1ScOMzMLBUnDjMzS8WJw8zMUnHiMDOzVJw4zMwsFScOMzNLxYnDzMxSceIwM7NUnDjMzCwVJw4zM0vFicPMzFLJW+KQ1EfSsqzPFklXSLpO0ktJ2VOSDk3qS9LtksqS7cdkHesCSauTzwX5itnMzGqWt1fHRsQqoBhAUhGwAXgEeDsirk7KLwemA98ETgN6J58hwE+AIZIOAmYAJUAASyTNjYi38xW7mZlVr76GqkYAayLi1YjYklXehkwyABgN3BsZC4F2kg4BTgWejojNSbJ4GhhZT3Gbmdke8tbj2MNY4P5dK5KuB84H3gWGJ8Vdgdey9ilPyqorNzOzAsh7j0PS/sAo4KFdZRHxrxHRHbgPmFxH55kgqVRSaUVFRV0c0szMqlAfQ1WnAUsj4s0qtt0HnJ0sbwC6Z23rlpRVV76biJgVESURUdKpU6c6CdzMzD6pPhLHOHYfpuqdtW00sDJZngucn1xddSzwbkS8AcwDTpHUXlJ74JSkzMzMCiCvcxyS2gAnAxOzim+Q1AfYCbxK5ooqgMeB04EyYCtwEUBEbJZ0HbA4qTczIjbnM24zM6ueIqLmWo1MSUlJlJaWFjoMM7NGRdKSiCipqZ7vHDczs1ScOMzMLBUnDjMzS8WJw8zMUnHiMDOzVJw4zMwsFScOMzNLxYnDzMxSceIwM7NUmuSd45IqyDzOpC51BN6q42MWQlNpB7gtDVVTaUtTaQfk3pbDI6LGp8Q2ycSRD5JKc7kVv6FrKu0At6WhaiptaSrtgLpvi4eqzMwsFScOMzNLxYkjd7MKHUAdaSrtALeloWoqbWkq7YA6bovnOMzMLBX3OMzMLBUnjiySRkpaJalM0tQqtp8gaamkjySdU4gYc5VDW66StELSS5L+S9LhhYgzFzm05ZuSXpa0TNKfJB1ZiDhzUVNbsuqdLSkkNcirenL4Ti6UVJF8J8skfaMQceYil+9E0rnJv5flkn5T3zHmKofv5das7+Svkt6p1Ykiwp/McF0RsAb4LLA/8CJw5B51egBHAfcC5xQ65n1sy3CgdbJ8KfBAoePeh7YcmLU8Cniy0HHXti1JvQOAZ4GFQEmh467ld3IhcEehY62jtvQGXgDaJ+udCx33vvx8ZdX/FjC7Nudyj+Njg4GyiFgbER8Cc4DR2RUiYn1EvETmfekNWS5tmR8RW5PVhUC3eo4xV7m0ZUvWahugoU7c1diWxHXAjcC2+gwuhVzb0Rjk0pZLgDsj4m2AiNhYzzHmKu33Mg64vzYncuL4WFfgtaz18qSsMUrblq8DT+Q1otrLqS2SJklaA9wEXF5PsaVVY1skHQN0j4jf1WdgKeX683V2MhT6sKTu9RNaarm05XPA5yQ9J2mhpJH1Fl06Of+7T4amewK/r82JnDg+5SR9DSgBbi50LPsiIu6MiF7Ad4DvFjqe2pC0H/AD4J8LHUsd+A+gR0QcBTwN/LLA8eyLZmSGq4aR+V/6XZLaFTSifTcWeDgidtRmZyeOj20Asv9X1C0pa4xyaoukk4B/BUZFxAf1FFtaab+XOcCZeY2o9mpqywFAP2CBpPXAscDcBjhBXuN3EhGbsn6mfg4MrKfY0srl56scmBsR2yNiHfBXMomkoUnzb2UstRymAjw5njVR1AxYS6b7tmtiqW81dX9Bw54cr7EtwNFkJtJ6FzreOmhL76zlLwGlhY57X3/GkvoLaJiT47l8J4dkLY8BFhY67n1oy0jgl8lyRzLDQR0KHXttf76AI4D1JPfx1ebjHkciIj4CJgPzgFeAByNiuaSZkkYBSBokqRz4MvAzScsLF3H1cmkLmaGptsBDyaV5cwsU7l7l2JbJyWWSy4CrgAsKFO5e5diWBi/HdlyefCcvkplzurAw0e5djm2ZB2yStAKYD0yJiE2Fibh6KX6+xgJzIskiteE7x83MLBX3OMzMLBUnDjMzS8WJw8zMUnHiMDOzVJw4zMwsFScOa3QktZN0Wdb6oZIezsN5Ru3tCbZ1cVxJ10j6drL8i11PXZb084bylF9JPST9pdBxWMPRrNABmNVCO+Ay4McAEfE6UOePuY+IuUCd39+Sy3EjosE+htzMPQ5rjG4VTkVFAAACp0lEQVQAeiU3Lt6c/T/i5D0Qj0p6WtJ6SZOTd4+8kDyg7qCkXi9JT0paIumPko7Y8yTJse5Iln8h6XZJ/y1prap4H0sSx8qk7l8l3SfppOTheKslDd7zuNWRtEBSiaSi5Hh/UeadI1fuLX5JXSQ9IunF5POPSflVyTH+IumKrHhfkXRXcrPeU5JaJdsG7joGMKm2X5Q1TU4c1hhNBdZERHFETKliez/gLGAQcD2wNSKOBp4Hzk/qzAK+FREDgW+T9F5qcAgwFPgimeRVlX8Avk/msQ5HAF9N9vk28C85nGNPxUDXiOgXEf2Be2qI/3bgDxExADgGWC5pIHARMITM868ukXR0Ur83mUeG9wXeAc5Oyu9Jjj+gFjFbE+ehKmuK5kfE34C/SXqXzJNaAV4GjpLUFvhHMo9b2bVPixyO+2hE7ARWSOpSTZ11EfEyQPJImv+KiJD0MpkXgaW1FvispB8BvwOeqiH+fyJJjpF58um7koYCj0TE+0lcvwWOJzNcti4iliX7LgF6JE9+bRcRzyblvwJOq0Xs1kQ5cVhTlP2k351Z6zvJ/MzvB7wTEcX7cFzlUKeqc6cSEW9LGgCcCnwTOBe4gtrFX5XseHcArergmNbEeajKGqO/kXkEea1E5o2B6yR9GUAZDXJIRlJHYL+I+Hcy7xk5pob4/4vMq4BJ5kc+A/wROFNSa0ltyDyt9o/VnTMi3gHeSXoqAOPz0TZrvJw4rNFJnkz6XDLRW9sXUI0Hvp5M/i6n4b76tCuZ93MsA34NTEvKq4v//wHDk6GxJWTeOb2UzKsAFgF/Bn4eES/UcN6LgDuT81bXu7JPKT8d18zMUnGPw8zMUnHiMDOzVJw4zMwsFScOMzNLxYnDzMxSceIwM7NUnDjMzCwVJw4zM0vl/wBizmI3IxfgqwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "%matplotlib inline\n",
    "plt.ylabel('edges')\n",
    "plt.xlabel('time in millisecond')\n",
    "list1 = []\n",
    "list2 = []\n",
    "for x,y in compare_dsu:\n",
    "    #print(x)\n",
    "    #print(y)\n",
    "    list1.append(x)\n",
    "    list2.append(y)\n",
    "plt.plot(list1, list2, label=\"DSU\")\n",
    "list1 = []\n",
    "list2 = []\n",
    "for x,y in compare_veb:\n",
    "    #print(x)\n",
    "    #print(y)\n",
    "    list1.append(x)\n",
    "    list2.append(y)\n",
    "plt.plot(list1, list2, label=\"VEB TREE\")\n",
    "list1 = []\n",
    "list2 = []\n",
    "for x,y in compare_fib:\n",
    "    #print(x)\n",
    "    #print(y)\n",
    "    list1.append(x)\n",
    "    list2.append(y)\n",
    "plt.plot(list1, list2, label=\"Fibonacci Heap\")\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}