data_structure.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Data Structure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Array"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Array:\n",
    "    def __init__(self, x):\n",
    "        self.data = list(x)\n",
    "        \n",
    "    def size(self):\n",
    "        return len(self.data)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        if not self.data:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def at(self,index):\n",
    "        if index >= len(self.data):\n",
    "            print(\"Array index out of range.\")\n",
    "        return self.data[index]\n",
    "\n",
    "    def push(self,item):\n",
    "        self.data.append(item)\n",
    "    \n",
    "    def insert(self, index, item):\n",
    "        self.data.insert(index, item)\n",
    "        \n",
    "    def pop(self):\n",
    "        return self.data.pop()\n",
    "    \n",
    "    def delete(self,index):\n",
    "        self.data.pop(index)\n",
    "        \n",
    "    def remove(self, item):\n",
    "        index_list = []\n",
    "        item_count = self.data.count(item)\n",
    "        for i in range(item_count):\n",
    "            index_list.append(self.data.index(item))\n",
    "            self.data.remove(item)\n",
    "        return index_list\n",
    "\n",
    "    def find(self, item):\n",
    "        if item in self.data:\n",
    "            return self.data.index(item)\n",
    "        else:\n",
    "            return -1\n",
    "        \n",
    "    def reverse(self):\n",
    "        temp = []\n",
    "        size = len(self.data)\n",
    "        for i in range(size):\n",
    "            temp.append(self.data[size-1-i])\n",
    "        self.data = temp\n",
    "        \n",
    "    def sort(self):\n",
    "        return self.data.sort()  \n",
    "    \n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "a_t = Array([1,2,3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linked List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "class listNode:     \n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "class LinkedList:        \n",
    "    def __init__(self):\n",
    "        self.head = None\n",
    "        \n",
    "    def size(self):\n",
    "        size = 0\n",
    "        head = self.head\n",
    "        while head:\n",
    "            size += 1\n",
    "            head = head.next\n",
    "        return size\n",
    "    \n",
    "    def empty(self):\n",
    "        if self.head:\n",
    "            return True \n",
    "        else:\n",
    "            False\n",
    "            \n",
    "    def value_at(self, index):\n",
    "        if not self.head:\n",
    "            print(\"Index out of range.\")\n",
    "        head = self.head\n",
    "        while index > 0:\n",
    "            if not head:\n",
    "                print(\"Index out of range.\")\n",
    "            head = head.next\n",
    "            index -= 1\n",
    "        return head.val\n",
    "    \n",
    "    def add(self, value):\n",
    "        new_node = listNode(value)\n",
    "        new_node.next = self.head\n",
    "        self.head = new_node\n",
    "        \n",
    "    def pop_front(self):\n",
    "        if not self.head:\n",
    "            print(\"Pop from empty list\")\n",
    "        value = self.head.val\n",
    "        self.head = self.head.next\n",
    "        return value\n",
    "    \n",
    "    def append(self, value):\n",
    "        new_node = listNode(value)\n",
    "        if not self.head:\n",
    "            self.head = new_node\n",
    "            return\n",
    "        head = self.head\n",
    "        while head.next:\n",
    "            head = head.next\n",
    "        head.next = new_node\n",
    "        \n",
    "    \n",
    "    def pop_back(self):\n",
    "        if not self.head:\n",
    "            print(\"Pop from empty list\")\n",
    "        if not self.head.next:\n",
    "            value = self.head.val\n",
    "            self.head = None\n",
    "            return value\n",
    "        head = self.head\n",
    "        while head.next.next:\n",
    "              head = head.next\n",
    "        value = head.next.val\n",
    "        head.next = None\n",
    "        return value\n",
    "    \n",
    "    \n",
    "    def front(self):\n",
    "        if not self.head:\n",
    "            print(\"Linked list is empty\")\n",
    "        return self.head.val\n",
    "    \n",
    "    def back(self):\n",
    "        if not self.head:\n",
    "            print(\"Linked list is empty\")\n",
    "        head = self.head\n",
    "        while head.next:\n",
    "            head = head.next\n",
    "        return head.val\n",
    "    \n",
    "    \n",
    "    def insert(self, index, value):\n",
    "        if not self.head:\n",
    "            print(\"Index out of range\")\n",
    "        head = self.head\n",
    "        new_node = listNode(value)\n",
    "        if index == 0:\n",
    "            new_node.next = head\n",
    "            self.head = new_node\n",
    "            return\n",
    "        while index - 1 > 0:\n",
    "            head = head.next\n",
    "            if not head:\n",
    "                print(\"Index out of range\")\n",
    "            index -= 1\n",
    "        temp = head.next\n",
    "        head.next = new_node\n",
    "        new_node.next = temp\n",
    "        \n",
    "        \n",
    "    def erase(self, index):\n",
    "        if not self.head:\n",
    "            print(\"Index out of range\")\n",
    "        head = self.head\n",
    "        if index == 0:\n",
    "            self.head = head.next\n",
    "        while index - 1 > 0:\n",
    "            index -= 1\n",
    "            head = head.next\n",
    "            if not head:\n",
    "                print(\"Index out of range\")\n",
    "        temp = head.next\n",
    "        head.next = temp.next\n",
    "        \n",
    "        \n",
    "    def reverse(self):\n",
    "        prev = None\n",
    "        head = self.head\n",
    "        while head:\n",
    "            temp = head.next\n",
    "            head.next = prev\n",
    "            prev = head\n",
    "            head = temp\n",
    "        self.head = prev\n",
    "        \n",
    "    \n",
    "    def remove(self,value):\n",
    "        if not self.head:\n",
    "            return\n",
    "        head = self.head\n",
    "        if head.val == value:\n",
    "            self.head = head.next\n",
    "            return\n",
    "        while head.next:\n",
    "            if head.next.val == value:\n",
    "                temp = head.next.next\n",
    "                head.next = temp\n",
    "                return\n",
    "            head = head.next\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Stack"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "        \n",
    "    def push(self, item):\n",
    "        self.data.append(item)\n",
    "    \n",
    "    def pop(self):\n",
    "        if self.data:\n",
    "            return self.data.pop()\n",
    "        else:\n",
    "            print(\"Pop from empty stack.\")\n",
    "    \n",
    "    def peek(self):\n",
    "        if self.data:\n",
    "            return self.data[-1]\n",
    "        else:\n",
    "            print(\"Stack is empty.\")\n",
    "            \n",
    "    def size(self): \n",
    "        return len(self.data)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        if not self.data:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "    \n",
    "    def enqueue(self, item):\n",
    "        self.data.append(item)\n",
    "        \n",
    "    def dequeue(self):\n",
    "        if self.data:\n",
    "            return self.data.pop(0)\n",
    "        else:\n",
    "            print(\"Queue is empty.\")\n",
    "        \n",
    "    def size(self):\n",
    "        return len(self.data)\n",
    "    \n",
    "    def is_empty(self):\n",
    "        if not self.data:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Circular Queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class CircularQueue:\n",
    "    def __init__(self, max_size = 6):\n",
    "        self.data = [None]*(max_size+1)\n",
    "        self.front = 0\n",
    "        self.rear = 0\n",
    "\n",
    "    def get_max_size(self):\n",
    "        return len(self.data) - 1\n",
    "    \n",
    "    \n",
    "    def enqueue(self, item):\n",
    "        if (self.rear+1) % len(self.data) == self.front:\n",
    "            print(\"Queue is full. Unable to enqueue.\")\n",
    "        self.data[self.rear] = item\n",
    "        self.rear = (self.rear+1) % len(self.data)\n",
    "        \n",
    "        \n",
    "    def dequeue(self):\n",
    "        if self.front == self.rear:\n",
    "            print(\"Queue is empty. Unable to dequeue.\")\n",
    "        item = self.data[self.front]\n",
    "        self.data[self.front] = None\n",
    "        self.front = (self.front + 1) % len(self.data)\n",
    "        return item\n",
    "    \n",
    "    def size(self):\n",
    "        return (self.rear - self.front + len(self.data)) % len(self.data)\n",
    "    \n",
    "    \n",
    "    def is_empty(self):\n",
    "        return self.front == self.rear\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Deque"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Deque:\n",
    "    def __init__(self):\n",
    "        self.data = []\n",
    "        \n",
    "    def is_empty(self):\n",
    "        return self.data == []\n",
    "    \n",
    "    def add_front(self, item):\n",
    "        self.data.insert(0,item)\n",
    "    \n",
    "    def add_rear(self,item):\n",
    "        self.data.append(item)\n",
    "        \n",
    "    def remove_front(self):\n",
    "        self.data.pop(0)\n",
    "        \n",
    "    def remove_rear(self):\n",
    "        self.data.pop()\n",
    "        \n",
    "    def size(self):\n",
    "        return len(self.data)\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "def preorder(root):\n",
    "    if root is None:\n",
    "        return None\n",
    "    print(root.val)\n",
    "    preorder(root.left)\n",
    "    preorder(root.right)\n",
    "    \n",
    "\n",
    "def inorder(root):\n",
    "    if root is None:\n",
    "        return None\n",
    "    inorder(root.left)\n",
    "    print(root.val)\n",
    "    inorder(root.right)\n",
    "    \n",
    "def postorder(root):\n",
    "    if root is None:\n",
    "        return None\n",
    "    postorder(root.left)\n",
    "    postorder(root.right)\n",
    "    print(root.val)\n",
    "    \n",
    "\n",
    "def levelorder(root):\n",
    "    if root is None:\n",
    "        return None\n",
    "    queue = [root]\n",
    "    while queue:\n",
    "        root = queue.pop(0)\n",
    "        print(root.val)\n",
    "        if root.left:\n",
    "            queue.append(root.left)\n",
    "        if root.right:\n",
    "            queue.append(root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = TreeNode(1)\n",
    "b = TreeNode(2)\n",
    "c = TreeNode(3)\n",
    "d = TreeNode(4)\n",
    "e = TreeNode(5)\n",
    "f = TreeNode(6)\n",
    "g = TreeNode(7)\n",
    " \n",
    "a.left = b\n",
    "a.right = c\n",
    "b.left = d\n",
    "b.right = e\n",
    "c.left = f\n",
    "c.right = g"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "5\n",
      "6\n",
      "7\n"
     ]
    }
   ],
   "source": [
    "levelorder(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Binary Search Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        \n",
    "        \n",
    "class Binary_Search_Tree:\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "    \n",
    "    def find_item(self,item):\n",
    "        if self.root is None:\n",
    "            return None\n",
    "        node = self.root\n",
    "        while node:\n",
    "            if node.val == item:\n",
    "                return node\n",
    "            elif node.val > item:\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = node.right\n",
    "\n",
    "        return None\n",
    "    \n",
    "    def find_max(self):\n",
    "        if self.root is None:\n",
    "            return None\n",
    "        node = self.root\n",
    "        while node.right:\n",
    "            node = node.right\n",
    "        return node\n",
    "    \n",
    "    def _find_max(self,node):\n",
    "        if node is None:\n",
    "            return None \n",
    "        while node.right:\n",
    "            node = node.right  \n",
    "        return node\n",
    "    \n",
    "    \n",
    "    def find_min(self):\n",
    "        if self.root is None:\n",
    "            return None\n",
    "        node = self.root\n",
    "        while node.left:\n",
    "            node = node.left\n",
    "        return node\n",
    "    \n",
    "    def _find_min(self,node):\n",
    "        if node is None:\n",
    "            return None   \n",
    "        while node.left:\n",
    "            node = node.left   \n",
    "        return node\n",
    "    \n",
    "    \n",
    "    def add_node(self,value):\n",
    "        if self.root is None:\n",
    "            self.root = TreeNode(value)\n",
    "        else:\n",
    "            self.root = self._add_node(value,self.root)\n",
    "    \n",
    "    def _add_node(self,value,node):\n",
    "        if node is None:\n",
    "            return TreeNode(value)\n",
    "        if value > node.val:\n",
    "            node.right = self._add_node(value,node.right)\n",
    "        elif value < node.val:\n",
    "            node.left = self._add_node(value,node.left)\n",
    "        else:\n",
    "            pass\n",
    "\n",
    "        return node\n",
    "    \n",
    "    def delete_node(self,value):\n",
    "        if self.root is None:\n",
    "            print('empty tree')\n",
    "        else:\n",
    "            self.root = self._delete_node(value,self.root)\n",
    "            \n",
    "    \n",
    "    def _delete_node(self,value,node):\n",
    "        if node is None:\n",
    "            print('key not in the tree')\n",
    "        elif value < node.val:\n",
    "            node.left = self._delete_node(value,node.left)\n",
    "        elif value > node.val:\n",
    "            node.right = self._delete_node(value,node.right)\n",
    "        else:\n",
    "            temp = self._find_min(node.rght)\n",
    "            node.val = temp.val\n",
    "            node.right = self._delete_node(temp.val,node.right)    \n",
    "        \n",
    "        return node\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## AVL Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.height = 1\n",
    "        \n",
    "class AVL_Tree:\n",
    "  \n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "    \n",
    "    def find(self,value):\n",
    "        if self.root is None:\n",
    "            return None\n",
    "        \n",
    "        node = self.root\n",
    "        while node:\n",
    "            if value == node.val:\n",
    "                return node\n",
    "            elif value > node.val:\n",
    "                node = node.right\n",
    "            else:\n",
    "                node = node.left\n",
    "            \n",
    "        return None\n",
    " \n",
    "    def find_min(self):\n",
    "        if self.root is None:\n",
    "            return None\n",
    "        \n",
    "        node = self.root\n",
    "        while node.left:\n",
    "            node = node.left\n",
    "            \n",
    "        return node\n",
    "   \n",
    "    def _find_min(self,node):\n",
    "        if node is None:\n",
    "            return None\n",
    "        \n",
    "        while node.left:\n",
    "            node = node.left\n",
    "            \n",
    "        return node\n",
    "    \n",
    "    \n",
    "    def find_max(self):\n",
    "        if self.root is None:\n",
    "            return None\n",
    "        \n",
    "        node = self.root\n",
    "        while node.right:\n",
    "            node = node.right\n",
    "            \n",
    "        return node\n",
    "    \n",
    "    def _find_max(self,node):\n",
    "        if node is None:\n",
    "            return None\n",
    "        \n",
    "        while node.right:\n",
    "            node = node.right\n",
    "            \n",
    "        return node\n",
    "    \n",
    "    \n",
    "    def get_height(self,node):\n",
    "        if node is None:\n",
    "            return 0\n",
    "        else:\n",
    "            return node.height\n",
    "        \n",
    "        \n",
    "    def single_right_rotate(self,node):\n",
    "        temp = node.left\n",
    "        node.left = temp.right\n",
    "        temp.right = node\n",
    "        node.height = max(self.get_height(node.right), self.get_height(node.left)) + 1\n",
    "        temp.height = max(self.get_height(temp.left), node.height) + 1\n",
    "        return temp\n",
    "    \n",
    "    def single_left_rotate(self,node):\n",
    "        temp = node.right\n",
    "        node.right = temp.left\n",
    "        temp.left = node\n",
    "        node.height = max(self.get_height(node.right), self.get_height(node.left)) + 1\n",
    "        temp.height = max(self.get_height(temp.right), node.height) + 1\n",
    "        return temp\n",
    "    \n",
    "    \n",
    "    def double_left_right_rotate(self,node):\n",
    "        node.left = self.single_left_rotate(node.left)\n",
    "        return self.single_right_rotate(node)\n",
    "    \n",
    "    def double_right_left_rotate(self,node):\n",
    "        node.right = self.single_right_rotate(node.right)\n",
    "        return self.single_left_rotate(node)\n",
    "    \n",
    "    def insert(self,value):\n",
    "        if self.root is None:\n",
    "            self.root = TreeNode(value)\n",
    "        else:\n",
    "            self.root = self._insert(value,self.root)\n",
    "    \n",
    "    def _insert(self,value,node):\n",
    "        if node is None:\n",
    "            node = TreeNode(value)\n",
    "        elif value < node.val:\n",
    "            node.left = self._insert(value,node.left)\n",
    "            if (self.get_height(node.left) - self.get_height(node.right)) == 2:\n",
    "                if value < node.left.val:\n",
    "                    node = self.single_right_rotate(node)\n",
    "                else:\n",
    "                    node = self.double_left_right_rotate(node)\n",
    "        elif value > node.val:\n",
    "            node.right = self._insert(value,node.right)\n",
    "            if (self.get_height(node.right) - self.get_height(node.left)) == 2:\n",
    "                if value > node.right.val:\n",
    "                    node = self.single_left_rotate(node)\n",
    "                else:\n",
    "                    node = self.double_right_left_rotate(node)\n",
    "                    \n",
    "        node.height = max(self.get_height(node.left),self.get_height(node.right)) + 1\n",
    "\n",
    "        return node\n",
    "    \n",
    "    def delete(self,value):\n",
    "        if self.root is None:\n",
    "            print('empty tree')\n",
    "        else:\n",
    "            self.root = self._delete(value,self.root)\n",
    "            \n",
    "    def _delete(self,value,node):\n",
    "        if node is None:\n",
    "            print('key not in the tree')\n",
    "        \n",
    "        elif value < node.val:\n",
    "            node.left = self._delete(value,node.left)\n",
    "            if(self.get_height(node.right) - self.get_height(node.left)) == 2:\n",
    "                if self.get_height(node.right.right) >= self.get_height(node.right.left):\n",
    "                    node = self.single_left_rotate(node)\n",
    "                else:\n",
    "                    node = self.double_right_left_rotate(node)\n",
    "                node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1\n",
    "        elif value > node.val:\n",
    "            node.right = self._delete(value,node.right)\n",
    "            if(self.get_height(node.left) - self.get_height(node.right)) == 2:\n",
    "                if self.get_height(node.left.left) >= self.get_height(node.left.right):\n",
    "                    node = self.single_right_rotate(node)\n",
    "                else:\n",
    "                    node = self.double_left_right_rotate(node)  \n",
    "                node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1\n",
    "        else:\n",
    "            if node.left and node.right:\n",
    "                if node.left.height <= node.right.height:\n",
    "                    min_node = self._find_min(node.right)\n",
    "                    node.val = min_node.val\n",
    "                    node.right = self._delete(node.val,node.right)\n",
    "                else:\n",
    "                    max_node = self._find_max(node.left)\n",
    "                    node.val = max_node.val\n",
    "                    node.left = self._delete(node.val,node.left)\n",
    "                node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1\n",
    "            else:\n",
    "                if node.right:\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    node = node.left\n",
    "        \n",
    "        \n",
    "        return node\n",
    "    \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Red-Black Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.parent = None\n",
    "        self.color = 'RED'\n",
    "        \n",
    "class Red_Black_Tree:\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "    \n",
    "    def find(self,value):\n",
    "        if self.root is None:\n",
    "            return None\n",
    "        \n",
    "        node = self.root\n",
    "        while node:\n",
    "            if value == node.val:\n",
    "                return node\n",
    "            elif value > node.val:\n",
    "                node = node.right\n",
    "            else:\n",
    "                node = node.left\n",
    "            \n",
    "        return None\n",
    "\n",
    "    def find_min(self):\n",
    "        if self.root is None:\n",
    "            return None\n",
    "        \n",
    "        node = self.root\n",
    "        while node.left:\n",
    "            node = node.left\n",
    "            \n",
    "        return node\n",
    "   \n",
    "    def _find_min(self,node):\n",
    "        if node is None:\n",
    "            return None\n",
    "        \n",
    "        while node.left:\n",
    "            node = node.left\n",
    "            \n",
    "        return node\n",
    "    \n",
    "    def find_max(self):\n",
    "        if self.root is None:\n",
    "            return None\n",
    "        \n",
    "        node = self.root\n",
    "        while node.right:\n",
    "            node = node.right\n",
    "            \n",
    "        return node\n",
    "    \n",
    "    def _find_max(self,node):\n",
    "        if node is None:\n",
    "            return None\n",
    "        \n",
    "        while node.right:\n",
    "            node = node.right\n",
    "            \n",
    "        return node\n",
    "    \n",
    "    \n",
    "    def transplant(self,node_u,node_v):\n",
    "        if not node_u.parent:\n",
    "            self.root = node_v\n",
    "        elif node_u == node_u.parent.left:\n",
    "            node_u.parent.left = node_v\n",
    "        elif node_u == node_u.parent.right:\n",
    "            node_u.parent.right = node_v\n",
    "            \n",
    "        if node_v:\n",
    "            node_v.parent = node_u.parent\n",
    "    \n",
    "    \n",
    "    def left_rotate(self,node):\n",
    "        parent = node.parent\n",
    "        right = node.right\n",
    "        node.right = right.left\n",
    "        if node.right:\n",
    "            node.right.parent = node\n",
    "        right.left = node\n",
    "        node.parent = right\n",
    "        right.parent = parent\n",
    "        if not parent:\n",
    "            self.root = right\n",
    "        else:\n",
    "            if parent.left == node:\n",
    "                parent.left = right\n",
    "            else:\n",
    "                parent.right = right\n",
    "    \n",
    "    def right_rotate(self,node):\n",
    "        parent = node.parent\n",
    "        left = node.left\n",
    "        node.left = left.right\n",
    "        if node.left:\n",
    "            node.left.parent = node\n",
    "        left.right = node\n",
    "        node.parent = left\n",
    "        left.parent = parent\n",
    "        if not parent:\n",
    "            self.root = left\n",
    "        else:\n",
    "            if parent.right == node:\n",
    "                parent.right = left\n",
    "            else:\n",
    "                parent.left = left\n",
    "    \n",
    "    def insert(self,value):\n",
    "        node_inserted = TreeNode(value)\n",
    "        temp_root = self.root\n",
    "        temp_node = None\n",
    "        while temp_root:\n",
    "            temp_node = temp_root\n",
    "            if value == temp_node.val:\n",
    "                print('key already in the tree')\n",
    "                return \n",
    "            elif value > temp_node.val:\n",
    "                temp_root = temp_root.right\n",
    "            else:\n",
    "                temp_root = temp_root.left\n",
    "        \n",
    "        if temp_node is None:\n",
    "            self.root = node_inserted\n",
    "            self.root.color = 'BLACK'\n",
    "        elif value < temp_node.val:\n",
    "            temp_node.left = node_inserted\n",
    "            node_inserted.parent = temp_node\n",
    "        else:\n",
    "            temp_node.right = node_inserted\n",
    "            node_inserted.parent = temp_node\n",
    "            \n",
    "        self.insert_fixup(node_inserted)\n",
    "    \n",
    "    \n",
    "    def insert_fixup(self,node):\n",
    "        if node.val == self.root.val:\n",
    "            return\n",
    "        while node.parent and node.parent.color == 'RED':\n",
    "            if node.parent == node.parent.parent.left:\n",
    "                node_aunt = node.parent.parent.right\n",
    "                if node_aunt and node_aunt.color == 'RED':\n",
    "                    node.parent.color = 'BLACK'\n",
    "                    node_aunt.color = 'BLACK'\n",
    "                    node.parent.parent.color = 'RED'\n",
    "                    node = node.parent.parent\n",
    "                    continue\n",
    "                elif node == node.parent.right:\n",
    "                    self.left_rotate(node.parent)\n",
    "                    node = node.left\n",
    "                \n",
    "                node.parent.color = 'BLACK'\n",
    "                node.parent.parent.color = 'RED'\n",
    "                self.right_rotate(node.parent.parent)\n",
    "                return\n",
    "            elif node.parent == node.parent.parent.right:\n",
    "                node_aunt = node.parent.parent.left\n",
    "                if node_aunt and node_aunt.color == 'RED':\n",
    "                    node.parent.color = 'BLACK'\n",
    "                    node_aunt.color = 'BLACK'\n",
    "                    node.parent.parent.color = 'RED'\n",
    "                    node = node.parent.parent\n",
    "                    continue\n",
    "                elif node == node.parent.left:\n",
    "                    self.right_rotate(node.parent)\n",
    "                    node = node.right\n",
    "                \n",
    "                node.parent.color = 'BLACK'\n",
    "                node.parent.parent.color = 'RED'\n",
    "                self.left_rotate(node.parent.parent)\n",
    "                return\n",
    "            \n",
    "        self.root.color = 'BLACK'\n",
    "        \n",
    "    def delete(self,value):\n",
    "        node = self.root\n",
    "        if node == None:\n",
    "            print(\"Tree empty\")\n",
    "            return\n",
    "        while node:\n",
    "            if node.val == value:\n",
    "                break\n",
    "            elif node.val < value:\n",
    "                node = node.right\n",
    "            elif node.val > value:\n",
    "                node = node.left\n",
    "        \n",
    "        if node == None:\n",
    "            print(\"value not in tree\")\n",
    "            return\n",
    "        \n",
    "        node_color = node.color\n",
    "        if not node.left:\n",
    "            temp_node = node.right\n",
    "            self.transplant(node, node.right)\n",
    "        elif not node.right:\n",
    "            temp_node = node.left\n",
    "            self.transplant(node, node.left)\n",
    "        else:\n",
    "            node_min = self._find_min(node.right)\n",
    "            node_color = node_min.color\n",
    "            temp_node = node_min.right\n",
    "            if node_min.parent != node:\n",
    "                self.transplant(node_min,node_min.right)\n",
    "                node_min.right = node.right\n",
    "                node_min.right.parent = node_min\n",
    "            self.transplant(node,node_min)\n",
    "            node_min.left = node.left\n",
    "            node_min.left.parent = node_min\n",
    "            node_min.color = node.color\n",
    "        \n",
    "        if node_color == 'BLACK':\n",
    "            self.delete_fixup(temp_node)\n",
    "    \n",
    "    \n",
    "    def delete_fixup(self,node):\n",
    "        while node != self.root and node.color == \"BLACK\":\n",
    "            if node == node.parent.left:\n",
    "                node_sibling = node.parent.right\n",
    "                if node_sibling.color == 'RED':\n",
    "                    node_sibling.color = 'BLACK'\n",
    "                    node.parent.color = 'RED'\n",
    "                    self.left_rotate(node.parent)\n",
    "                    node_sibling = node.parent.right\n",
    "                if (not node_sibling.left or node_sibling.left.color == \"BLACK\") and \\\n",
    "                        (not node_sibling.right or node_sibling.right.color == \"BLACK\"):\n",
    "                    if node.parent.color == 'RED':\n",
    "                        node.parent.color = 'BLACK'\n",
    "                        node_sibling.color = 'RED'\n",
    "                        break\n",
    "                    else: \n",
    "                        node_sibling.color = 'RED'\n",
    "                        node = node.parent\n",
    "                else:\n",
    "                    if not node_sibling.right or node_sibling.right.color == \"BLACK\":\n",
    "                        node_sibling.color = 'RED'\n",
    "                        node_sibling.left.color = 'BLACK'\n",
    "                        self.right_rotate(node_sibling)\n",
    "                        node_sibling = node.parent.right\n",
    "                \n",
    "                    node_sibling.color = node.parent.color\n",
    "                    node.parent.color = \"BLACK\"\n",
    "                    node_sibling.right.color = \"BLACK\"\n",
    "                    self.left_rotate(node.parent)\n",
    "                    break\n",
    "            else:\n",
    "                node_sibling = node.parent.left\n",
    "                if node_sibling.color == 'RED':\n",
    "                    node_sibling.color = 'BLACK'\n",
    "                    node.parent.color = 'RED'\n",
    "                    self.right_rotate(node.parent)\n",
    "                    node_sibling = node.parent.left\n",
    "                if (not node_sibling.left or node_sibling.left.color == \"BLACK\") and \\\n",
    "                        (not node_sibling.right or node_sibling.right.color == \"BLACK\"):\n",
    "                    if node.parent.color == 'RED':\n",
    "                        node.parent.color = 'BLACK'\n",
    "                        node_sibling.color = 'RED'\n",
    "                        break\n",
    "                    else: \n",
    "                        node_sibling.color = 'RED'\n",
    "                        node = node.parent\n",
    "                else:\n",
    "                    if not node_sibling.left or node_sibling.left.color == \"BLACK\":\n",
    "                        node_sibling.color = 'RED'\n",
    "                        node_sibling.right.color = 'BLACK'\n",
    "                        self.left_rotate(node_sibling)\n",
    "                        node_sibling = node.parent.left\n",
    "                \n",
    "                    node_sibling.color = node.parent.color\n",
    "                    node.parent.color = \"BLACK\"\n",
    "                    node_sibling.left.color = \"BLACK\"\n",
    "                    self.right_rotate(node.parent)\n",
    "                    break\n",
    "    \n",
    "        node.color = 'BLACK'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = Red_Black_Tree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "a.insert(20)\n",
    "a.insert(10)\n",
    "a.insert(30)\n",
    "a.insert(5)\n",
    "a.insert(7)\n",
    "a.insert(40)\n",
    "a.insert(50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "20\n",
      "7\n",
      "5\n",
      "10\n",
      "40\n",
      "30\n",
      "50\n"
     ]
    }
   ],
   "source": [
    "preorder(a.root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## B-tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BTreeNode:\n",
    "    def __init__(self,is_leaf=False):\n",
    "        self.is_leaf = is_leaf\n",
    "        self.keys = []\n",
    "        self.child = []\n",
    "        \n",
    "        \n",
    "class BTree:\n",
    "    def __init__(self,t):\n",
    "        self.root = BTreeNode(True)\n",
    "        self.t = t   # degree\n",
    "    \n",
    "    \n",
    "    def search_key(self,k,x=None):\n",
    "        if x is not None:\n",
    "            i = 0\n",
    "            while i < len(x.keys) and k > x.keys[i]:\n",
    "                i += 1\n",
    "            if i < len(x.keys) and k == x.keys[i]:\n",
    "                return (x,i)\n",
    "            elif x.is_leaf:\n",
    "                return None\n",
    "            else:\n",
    "                return self.search_key(k,x.child[i])\n",
    "        else:\n",
    "            return self.search_key(k,self.root)\n",
    "    \n",
    "\n",
    "    def insert(self,k):\n",
    "        root = self.root\n",
    "        if len(root.keys) == (2*self.t)-1:\n",
    "            temp = BTreeNode()\n",
    "            self.root = temp\n",
    "            temp.child.insert(0,root)\n",
    "            self.split_child(temp,0)\n",
    "            self.insert_non_full(temp,k)\n",
    "        else:\n",
    "            self.insert_non_full(root,k)\n",
    "            \n",
    "    def split_child(self,x,i):\n",
    "        t = self.t\n",
    "        y = x.child[i]\n",
    "        z = BTreeNode(y.is_leaf)\n",
    "        x.child.insert(i+1,z)\n",
    "        x.keys.insert(i,y.keys[t-1])\n",
    "        z.keys = y.keys[t:(2*t)-1]\n",
    "        y.keys = y.keys[0:t-1]\n",
    "        if not y.is_leaf:\n",
    "            z.child = y.child[t:2*t]\n",
    "            y.child = y.child[0:t]\n",
    "        \n",
    "     \n",
    "    def insert_non_full(self,x,k):\n",
    "        i = len(x.keys) - 1\n",
    "        if x.is_leaf:\n",
    "            x.keys.append(None)\n",
    "            while i>=0 and k<x.keys[i]:\n",
    "                x.keys[i+1] = x.keys[i]\n",
    "                i -= 1\n",
    "            x.keys[i+1] = k\n",
    "        else:\n",
    "            while i>=0 and k<x.keys[i]:\n",
    "                i -= 1\n",
    "            i += 1\n",
    "            if len(x.child[i].keys) == (2*self.t)-1:\n",
    "                self.split_child(x, i)\n",
    "                if k > x.keys[i]:\n",
    "                    i += 1\n",
    "            self.insert_non_full(x.child[i], k)\n",
    "            \n",
    "    def delete(self,x,k):\n",
    "        t = self.t\n",
    "        i = 0\n",
    "        while i < len(x.keys) and k > x.keys[i]:\n",
    "            i += 1\n",
    "        if x.is_leaf:\n",
    "            if i < len(x.keys) and x.keys[i] == k:\n",
    "                x.keys.pop(i)\n",
    "                return\n",
    "            return\n",
    "        \n",
    "        if i < len(x.keys) and x.keys[i] == k:\n",
    "            return self.delete_internal_node(x,k,i)\n",
    "        elif len(x.child[i].keys) >= t:\n",
    "            self.delete(x.child[i],k)\n",
    "        else:\n",
    "            if i != 0 and i+1 < len(x.child):\n",
    "                if len(x.child[i-1].keys) >= t:\n",
    "                    self.delete_sibling(x,i,i-1)\n",
    "                elif len(x.child[i+1].keys) >= t:\n",
    "                    self.delete_sibling(x,i,i+1)\n",
    "                else:\n",
    "                    self.delete_merge(x,i,i+1)\n",
    "            elif i == 0:\n",
    "                if len(x.child[i+1].keys) >= t:\n",
    "                    self.delete_sibling(x,i,i+1)\n",
    "                else:\n",
    "                    self.delete_merge(x,i,i+1)\n",
    "            elif i+1 == len(x.child):\n",
    "                if len(x.child[i-1].keys) >= t:\n",
    "                    self.delete_sibling(x,i,i-1)\n",
    "                else:\n",
    "                    self.delete_merge(x,i,i-1)\n",
    "            \n",
    "            self.delete(x.child[i],k)\n",
    "     \n",
    "    \n",
    "    def delete_internal_node(self,x,k,i):\n",
    "        t = self.t\n",
    "        if x.is_leaf:\n",
    "            if x.keys[i] == k:\n",
    "                x.keys.pop(i)\n",
    "                return\n",
    "            return\n",
    "        \n",
    "        if len(x.child[i].keys) >= t:\n",
    "            x.keys[i] = self.delete_predecessor(x.child[i])\n",
    "            return\n",
    "        elif len(x.child[i+1].keys) >= t:\n",
    "            x.keys[i] = self.delete_successor(x.child[i+1])\n",
    "            return\n",
    "        else:\n",
    "            self.delete_merge(x,i,i+1)\n",
    "            self.delete_internal_node(x.child[i],k,self.t-1)\n",
    "        \n",
    "        \n",
    "    def delete_predecessor(self,x):\n",
    "        if x.is_leaf:\n",
    "            return x.pop()\n",
    "        \n",
    "        n = len(x.keys) - 1\n",
    "        if len(x.child[n].keys) >= self.t:\n",
    "            self.delete_sibling(x,n+1,n)\n",
    "        else:\n",
    "            self.delete_merge(x,n,n+1)\n",
    "        \n",
    "        self.delete_predecessor(x.child[n])\n",
    "     \n",
    "    \n",
    "    def delete_successor(self,x):\n",
    "        if x.is_leaf:\n",
    "            return x.keys.pop(0)\n",
    "        \n",
    "        if len(x.child[1].keys) >= self.t:\n",
    "            self.delete_sibling(x,0,1)\n",
    "        else:\n",
    "            self.delete_merge(x,0,1)\n",
    "        \n",
    "        self.delete_successor(x.child[0])\n",
    "        \n",
    "    \n",
    "    def delete_merge(self,x,i,j):\n",
    "        cnode = x.child[i]\n",
    "        \n",
    "        if j > i:\n",
    "            rsnode = x.child[j]\n",
    "            cnode.keys.append(x.keys[i])\n",
    "            for k in range(len(rsnode.keys)):\n",
    "                cnode.keys.append(rsnode.keys[k])\n",
    "                if len(rsnode.child) > 0:\n",
    "                    cnode.child.append(rsnode.child[k])\n",
    "            if len(rsnode.child) > 0:\n",
    "                cnode.child.append(rsnode.child.pop())\n",
    "        \n",
    "            new = cnode\n",
    "            x.keys.pop(i)\n",
    "            x.child.pop(j)\n",
    "        else:\n",
    "            lsnode = x.child[j]\n",
    "            lsnode.keys.append(x.keys[j])\n",
    "            for i in range(len(cnode.keys)):\n",
    "                lsnode.keys.append(cnode.keys[i])\n",
    "                if len(lsnode.child) > 0:\n",
    "                    lsnode.child.append(cnode.child[i])\n",
    "            if len(lsnode.child) > 0:\n",
    "                lsnode.child.append(cnode.child.pop())\n",
    "                \n",
    "            new = lsnode\n",
    "            x.keys.pop(j)\n",
    "            x.child.pop(i)\n",
    "            \n",
    "        if x == self.root and len(x.keys) == 0:\n",
    "            self.root = new\n",
    "    \n",
    "    \n",
    "    def delete_sibling(self,x,i,j):\n",
    "        cnode = x.child[i]\n",
    "        if i < j:\n",
    "            rsnode = x.child[j]\n",
    "            cnode.keys.append(x.keys[i])\n",
    "            x.keys[i] = rsnode.keys[0]\n",
    "            if len(rsnode.child) > 0:\n",
    "                cnode.child.append(rsnode.child[0])\n",
    "                rsnode.child.pop(0)\n",
    "            rsnode.keys.pop(0)\n",
    "        else:\n",
    "            lsnode = x.child[j]\n",
    "            cnode.keys.insert(0,x.keys[i-1])\n",
    "            x.keys[i-1] = lsnode.keys.pop()\n",
    "            if len(lsnode.child) > 0:\n",
    "                cnode.child.insert(0,lsnode.child.pop())\n",
    "\n",
    "                \n",
    "    def print_tree(self,x,l=0):\n",
    "        print(\"Level\",l,': ',end=\"\")\n",
    "        for i in x.keys:\n",
    "            print(i, end=\" \")\n",
    "        print()\n",
    "        l += 1\n",
    "        if len(x.child) > 0:\n",
    "            for i in x.child:\n",
    "                self.print_tree(i, l)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Level 0 : 3 \n",
      "Level 1 : 1 \n",
      "Level 2 : 0 \n",
      "Level 2 : 2 \n",
      "Level 1 : 5 8 \n",
      "Level 2 : 4 \n",
      "Level 2 : 7 \n",
      "Level 2 : 9 \n"
     ]
    }
   ],
   "source": [
    "B = BTree(2)\n",
    "for i in range(10):\n",
    "    B.insert(i)\n",
    "B.delete(B.root,6)\n",
    "B.print_tree(B.root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Huffman Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TreeNode:\n",
    "    def __init__(self, x, y):\n",
    "        self.val = x\n",
    "        self.weight = y\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "        \n",
    "'''\n",
    "        src = [('a', 8), ('b', 5), ('c', 3), ('d', 3), \n",
    "        ('e', 8), ('f', 6), ('g', 2), ('h', 5), ('i', 9), \n",
    "        ('j', 5), ('k', 7), ('l', 5), ('m', 10), ('n', 9)]\n",
    "'''        \n",
    "        \n",
    "class Huffman_Tree:\n",
    "    def __init__(self, src):\n",
    "        self.codes = {}\n",
    "        self.src = [TreeNode(item[0],item[1]) for item in src]\n",
    "        self.root = self.create_huffman_tree(self.src)\n",
    "        \n",
    "    def create_huffman_tree(self,src):\n",
    "        min_2, src_left = self.min_2(src)\n",
    "        left = min_2[0]\n",
    "        right = min_2[1]\n",
    "        \n",
    "        sum_LR = left.weight + right.weight\n",
    "        father = TreeNode(None,sum_LR)\n",
    "        father.left = left\n",
    "        father.right = right\n",
    "        if len(src_left) == 0:\n",
    "            return father\n",
    "        src_left.append(father)\n",
    "        \n",
    "        return self.create_huffman_tree(src_left)\n",
    "        \n",
    "        \n",
    "    def min_2(self, src):\n",
    "        src = sorted(src, key = lambda node: node.weight)\n",
    "        res = src[:2]\n",
    "        src_left = src[2:]\n",
    "        return res, src_left\n",
    "    \n",
    "    def encoding(self):\n",
    "        init_code = ''\n",
    "        self._encoding(self.root,init_code)\n",
    "        \n",
    "    def _encoding(self,root,code):\n",
    "        node = root\n",
    "        if node is None:\n",
    "            return\n",
    "        if not node.left and not node.right:\n",
    "            self.codes[node.val] = code\n",
    "            return\n",
    "\n",
    "        self._encoding(node.left,code+'0')\n",
    "        self._encoding(node.right,code+'1')\n",
    "    \n",
    "    def decoding(self,val):\n",
    "        if val not in self.codes.keys():\n",
    "            print(\"val not available\")\n",
    "            return\n",
    "        \n",
    "        print(self.codes[val])\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "src = [('a', 8), ('b', 5), ('c', 3), ('d', 3), \n",
    "        ('e', 8), ('f', 6), ('g', 2), ('h', 5), ('i', 9), \n",
    "        ('j', 5), ('k', 7), ('l', 5), ('m', 10), ('n', 9)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = Huffman_Tree(src)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "t.encoding()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10110\n"
     ]
    }
   ],
   "source": [
    "t.decoding('g')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Heap (MaxHeap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "class MaxHeap:\n",
    "    def __init__(self,array):\n",
    "        self.data = [None] + array\n",
    "        index = self.get_size() // 2\n",
    "        while index > 0:\n",
    "            self.sift_down(index)\n",
    "            index -= 1\n",
    "    \n",
    "    def is_empty(self):\n",
    "        return len(self.data) == 1\n",
    "    \n",
    "    def get_size(self):\n",
    "        return len(self.data) - 1\n",
    "    \n",
    "    def get_max(self):\n",
    "        if self.is_empty():\n",
    "            return None\n",
    "        else:\n",
    "            return self.data[1]\n",
    "        \n",
    "    def insert(self,val):\n",
    "        self.data.append(val)\n",
    "        index = self.get_size()\n",
    "        while index > 1 and self.data[index] > self.data[index//2]:\n",
    "            self.data[index], self.data[index//2] = self.data[index//2], self.data[index]\n",
    "            index = index // 2\n",
    "    \n",
    "    def sift_down(self,index):\n",
    "        while 2*index <= self.get_size():\n",
    "            child = 2 * index\n",
    "            if 2*index+1 <= self.get_size() and self.data[2*index+1] > self.data[2*index]:\n",
    "                child = 2 * index + 1\n",
    "            if self.data[index] < self.data[child]:\n",
    "                self.data[index], self.data[child] = self.data[child], self.data[index]\n",
    "                index = child\n",
    "            else:\n",
    "                break\n",
    "    \n",
    "    def remove(self):\n",
    "        if self.is_empty():\n",
    "            print(\"cannot remove from an empty heap\")\n",
    "            return\n",
    "        self.data[1], self.data[self.get_size()] = self.data[self.get_size()], self.data[1]\n",
    "        self.data.pop()\n",
    "        self.sift_down(1)\n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "array = [1,2,3,4,5,6,7]\n",
    "heap = MaxHeap(array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[7, 5, 6, 4, 2, 1, 3]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "heap.data[1:]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Trie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Trie:\n",
    "    def __init__(self):\n",
    "        self.root = {}\n",
    "        self.end = 'end'\n",
    "    \n",
    "    def insert(self,word):\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if not c in node:\n",
    "                node[c] = {}\n",
    "            node = node[c]\n",
    "        node[self.end] = True\n",
    "        \n",
    "        \n",
    "    def search(self,word):\n",
    "        node = self.root\n",
    "        for c in word:\n",
    "            if not c in node:\n",
    "                return False\n",
    "            node = node[c]\n",
    "        \n",
    "        if self.end not in node:\n",
    "            return False\n",
    "        \n",
    "        return True\n",
    "    \n",
    "    def startsWith(self,prefix):\n",
    "        node = self.root\n",
    "        for c in prefix:\n",
    "            if not c in node:\n",
    "                return False\n",
    "            node = node[c]\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "t = Trie()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "t.insert('ash')\n",
    "t.insert('as')\n",
    "t.insert('ice')\n",
    "t.insert('icey')\n",
    "t.insert('kodak')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': {'s': {'end': True, 'h': {'end': True}}},\n",
       " 'i': {'c': {'e': {'end': True, 'y': {'end': True}}}},\n",
       " 'k': {'o': {'d': {'a': {'k': {'end': True}}}}}}"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "t.root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "True\n",
      "False\n"
     ]
    }
   ],
   "source": [
    "print(t.search('ash'))\n",
    "print(t.search('icey'))\n",
    "print(t.search('tray'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "print(t.startsWith('ice'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Suffix Tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Node:\n",
    "    def __init__(self,lab):\n",
    "        self.lab = lab \n",
    "        self.out = {}\n",
    "\n",
    "class Suffix_Tree:\n",
    "    def __init__(self,s):\n",
    "        s += '$'\n",
    "        self.root = Node(None)\n",
    "        self.root.out[s[0]]= Node(s)\n",
    "        for i in range(1,len(s)):\n",
    "            cur = self.root\n",
    "            j = i\n",
    "            suf = s[i:]\n",
    "            while j < len(s):\n",
    "                if s[j] not in cur.out:\n",
    "                    cur.out[s[j]] = Node(suf)\n",
    "                    break\n",
    "                else:\n",
    "                    z = 0\n",
    "                    while z < len(cur.out[s[j]].lab) and cur.out[s[j]].lab[z] == suf[z]:\n",
    "                        z += 1\n",
    "                    if z == len(cur.out[s[j]].lab):\n",
    "                        cur = cur.out[s[j]]\n",
    "                        j += z\n",
    "                    else:\n",
    "                        mid = Node(suf[:z])\n",
    "                        mid.out[suf[z]] = Node(suf)\n",
    "                        mid.out[cur.out[s[j]].lab[z]] = cur.out[s[j]]\n",
    "                        cur.out[s[j]] = mid\n",
    "                        break\n",
    "\n",
    "    def has_substring(self,pat):\n",
    "        cur = self.root\n",
    "        i = 0\n",
    "        while i < len(pat):\n",
    "            c = pat[i]\n",
    "            if c not in cur.out:\n",
    "                return False\n",
    "            child = cur.out[pat[i]]\n",
    "            lab = child.lab\n",
    "            z = 0\n",
    "            while z < len(lab) and z < len(pat) and pat[z] == lab[z]:\n",
    "                z += 1\n",
    "            if z == len(lab):\n",
    "                cur = child\n",
    "                i = z\n",
    "            elif z == len(pat):\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "    \n",
    "    def has_suffix(self,suf):\n",
    "        cur = self.root\n",
    "        i = 0\n",
    "        while i < len(suf):\n",
    "            c = suf[i]\n",
    "            if c not in cur.out:\n",
    "                return False\n",
    "            child = cur.out[suf[i]]\n",
    "            lab = child.lab\n",
    "            z = 0\n",
    "            while z < len(lab) and z < len(suf) and suf[z] == lab[z]:\n",
    "                z += 1\n",
    "            if z == len(lab):\n",
    "                cur = child\n",
    "                i = z\n",
    "            elif z == len(suf):\n",
    "                if lab[z] == '$':\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        if '$' in child.out:\n",
    "            return True\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "ST = Suffix_Tree('banana')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ST.has_substring('anan')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ST.has_suffix('nana')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Union-Find"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Union_Find:\n",
    "    def __init__(self,array):\n",
    "        self.data = array\n",
    "        self.parent = list(range(len(array)))\n",
    "        self.size = [1] * len(array)\n",
    "        self.count = len(array)\n",
    "        \n",
    "    def find(self,val):\n",
    "        index = self.data.index(val)\n",
    "        while index != self.parent[index]:\n",
    "            index = self.parent[index]\n",
    "        return index\n",
    "    \n",
    "    def union(self,val1,val2):\n",
    "        root1 = self.find(val1)\n",
    "        root2 = self.find(val2)\n",
    "        if root1 == root2:\n",
    "            return\n",
    "        \n",
    "        if self.size[root1] > self.size[root2]:\n",
    "            self.parent[root2] = root1\n",
    "            self.size[root1] += self.size[root2]\n",
    "        else:\n",
    "            self.parent[root1] = root2\n",
    "            self.size[root2] += self.size[root1]\n",
    "        \n",
    "        self.count -= 1\n",
    "        \n",
    "    def is_connected(self,val1,val2):\n",
    "        return self.find(val1) == self.find(val2)\n",
    "    \n",
    "    def _count(self):\n",
    "        return self.count      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "array = ['John','Scott','Grant','Tom','Miles','James','Nile','Noah','Ryan','David']\n",
    "uf = Union_Find(array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "uf.union('John','Scott')\n",
    "uf.union('John','Grant')\n",
    "uf.union('Ryan','Noah')\n",
    "uf._count()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "uf.find('Noah')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "uf.is_connected('Noah','Ryan')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Hash Table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "class listNode:\n",
    "    def __init__(self,key,value):\n",
    "        self.key = key\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "class Hash_Table:\n",
    "    def __init__(self,N):\n",
    "        self.size = N\n",
    "        self.table = [None] * N\n",
    "    \n",
    "    def prime(self, value):\n",
    "        for i in range(2, value // 2 + 1):\n",
    "            if value % i == 0:\n",
    "                return False\n",
    "        return True\n",
    " \n",
    "    def max_prime(self, value):\n",
    "        for i in range(value, 2, -1):\n",
    "            if self.prime(i):\n",
    "                return i\n",
    "\n",
    "    \n",
    "    def hash_code(self,key):\n",
    "        p = self.max_prime(self.size)\n",
    "        return key % p\n",
    "    \n",
    "    def insert(self,key,value):\n",
    "        index = self.hash_code(key)\n",
    "        head = self.table[index]\n",
    "        if not head:\n",
    "            self.table[index] = listNode(key,value)\n",
    "        else:\n",
    "            while head.next:\n",
    "                head = head.next    \n",
    "            head.next = listNode(key,value)\n",
    "            \n",
    "    def find(self,key):\n",
    "        index = self.hash_code(key)\n",
    "        head = self.table[index]\n",
    "        if not head:\n",
    "            return None\n",
    "        else:\n",
    "            while head:\n",
    "                if head.key == key:\n",
    "                    return head.value\n",
    "                head = head.next\n",
    "            return None\n",
    "        \n",
    "    def remove(self,key):\n",
    "        index = self.hash_code(key)\n",
    "        head = self.table[index]\n",
    "        if not head:\n",
    "            return None\n",
    "        else:\n",
    "            prev = None\n",
    "            while head:\n",
    "                if head.key == key:\n",
    "                    next_node = head.next\n",
    "                    if prev:\n",
    "                        prev.next = next_node\n",
    "                        return head.value\n",
    "                    else:\n",
    "                        self.table[index] = head.next\n",
    "                        return head.value\n",
    "                else:\n",
    "                    prev = head\n",
    "                    head = head.next\n",
    "            \n",
    "            return None\n",
    "            "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### UDG implemented by adjacency matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "class UDG_am:\n",
    "    def __init__(self,vertex):\n",
    "        self.vertex = vertex\n",
    "        self.graph=[[0]*vertex for i in range(vertex)]\n",
    "\n",
    "    def insert(self,u,v):\n",
    "        self.graph[u-1][v-1] = 1\n",
    "        # if DG, comment the code below\n",
    "        self.graph[v-1][u-1] = 1\n",
    "        \n",
    "    def show_graph(self):\n",
    "        for i in self.graph:\n",
    "            for j in i:\n",
    "                print(j,end = ' ')\n",
    "            print('')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 0 0 1 0 \n",
      "0 0 0 1 1 \n",
      "0 0 0 0 1 \n",
      "1 1 0 0 1 \n",
      "0 1 1 1 0 \n"
     ]
    }
   ],
   "source": [
    "graph = UDG_am(5)\n",
    "graph.insert(1, 4)\n",
    "graph.insert(4, 2)\n",
    "graph.insert(4, 5)\n",
    "graph.insert(2, 5)\n",
    "graph.insert(5, 3)\n",
    "graph.show_graph()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### UDG implemented by adjacency list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "class UDG_al:\n",
    "    def __init__(self):\n",
    "        self.nodes = []\n",
    "        self.edges = {}\n",
    "        \n",
    "    def insert(self,a,b):\n",
    "        if not(a in self.nodes):\n",
    "            self.nodes.append(a)\n",
    "            self.edges[a] = list()\n",
    "        if not (b in self.nodes):\n",
    "            self.nodes.append(b)\n",
    "            self.edges[b] = list()\n",
    "        self.edges[a].append(b)\n",
    "        # if DG, comment the code below\n",
    "        self.edges[b].append(a)\n",
    "        \n",
    "    def succ(self,a):\n",
    "        return self.edges[a]\n",
    "    \n",
    "    def show_nodes(self):\n",
    "        return self.nodes\n",
    "    \n",
    "    def show_edges(self):\n",
    "        return self.edges\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'0': ['1', '2'],\n",
       " '1': ['0', '2', '3'],\n",
       " '2': ['0', '1', '4', '6'],\n",
       " '3': ['1', '4'],\n",
       " '4': ['2', '3', '5'],\n",
       " '5': ['4', '6'],\n",
       " '6': ['2', '5']}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = UDG_al()\n",
    "graph.insert('0','1')\n",
    "graph.insert('0','2')\n",
    "graph.insert('1','2')\n",
    "graph.insert('1','3')\n",
    "graph.insert('2','4')\n",
    "graph.insert('2','6')\n",
    "graph.insert('3','4')\n",
    "graph.insert('4','5')\n",
    "graph.insert('5','6')\n",
    "graph.show_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/g1.png\" width=500 height=500 />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### DFS with UDG implemented by adjacency list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dfs_graph(G,s,S=None,res=None):\n",
    "    if S is None:\n",
    "        S=set()\n",
    "    if res is None:\n",
    "        res=[]\n",
    "    res.append(s)\n",
    "    S.add(s)\n",
    "    for u in G[s]:\n",
    "        if u in S:\n",
    "            continue\n",
    "        S.add(u)\n",
    "        dfs_graph(G,u,S,res)\n",
    "\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0', '1', '2', '4', '3', '5', '6']"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dfs_graph(graph.show_edges(), '0')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### BFS with UDG implemented by adjacency list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bfs_graph(G,s):\n",
    "    res = []\n",
    "    queue = [s]\n",
    "    res.append(s)\n",
    "    while queue:\n",
    "        v = queue.pop(0)\n",
    "        for w in G[v]:\n",
    "            if w not in res:\n",
    "                res.append(w)\n",
    "                queue.append(w)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0', '1', '2', '3', '4', '6', '5']"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "bfs_graph(graph.show_edges(), '0')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Weighted Undirected Graph implemented by adjacency list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "class WUDG_al:\n",
    "    def __init__(self):\n",
    "        self.nodes = []\n",
    "        self.edges = {}\n",
    "        \n",
    "    def insert(self,a,b,weight):\n",
    "        if not(a in self.nodes):\n",
    "            self.nodes.append(a)\n",
    "            self.edges[a] = list()\n",
    "        if not (b in self.nodes):\n",
    "            self.nodes.append(b)\n",
    "            self.edges[b] = list()\n",
    "        self.edges[a].append([b,weight])\n",
    "        # if DG, comment the code below\n",
    "        self.edges[b].append([a,weight])\n",
    "        \n",
    "    def succ(self,a):\n",
    "        return self.edges[a]\n",
    "    \n",
    "    def show_nodes(self):\n",
    "        return self.nodes\n",
    "    \n",
    "    def show_edges(self):\n",
    "        return self.edges\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'1': [['2', 6], ['4', 5], ['3', 1]],\n",
       " '2': [['1', 6], ['3', 5], ['5', 3]],\n",
       " '3': [['1', 1], ['2', 5], ['4', 7], ['5', 5], ['6', 4]],\n",
       " '4': [['1', 5], ['3', 7], ['6', 2]],\n",
       " '5': [['2', 3], ['3', 5], ['6', 6]],\n",
       " '6': [['3', 4], ['4', 2], ['5', 6]]}"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = WUDG_al()\n",
    "graph.insert('1','2',6)\n",
    "graph.insert('1','4',5)\n",
    "graph.insert('1','3',1)\n",
    "graph.insert('2','3',5)\n",
    "graph.insert('2','5',3)\n",
    "graph.insert('3','4',7)\n",
    "graph.insert('3','5',5)\n",
    "graph.insert('3','6',4)\n",
    "graph.insert('4','6',2)\n",
    "graph.insert('5','6',6)\n",
    "graph.show_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/g2.png\" width=400 height=400 />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Minimum Spanning Tree (Prim's algorithm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Prim(G,s):\n",
    "    MST = dict()\n",
    "    vertex_num = 1\n",
    "    temp = [i.copy() for i in G[s]]\n",
    "    for i in temp:\n",
    "        i.insert(0,s)\n",
    "    edges_list = temp\n",
    "    vertex_list = [s]\n",
    "    while vertex_num < len(G):\n",
    "        vertex1 = sorted(edges_list,key = lambda x:x[2])[0][0]\n",
    "        vertex2 = sorted(edges_list,key = lambda x:x[2])[0][1]\n",
    "        weight = sorted(edges_list,key = lambda x:x[2])[0][2]\n",
    "        vertex_list.append(vertex2)\n",
    "        temp = [i.copy() for i in G[vertex2]]\n",
    "        for i in temp:\n",
    "            i.insert(0,vertex2)\n",
    "        edges_list += temp\n",
    "        edges_list_temp = edges_list.copy()\n",
    "        for edge in edges_list_temp:\n",
    "            if (edge[0] == vertex2 and edge[1] in vertex_list) or (edge[1] == vertex2 and edge[0] in vertex_list):\n",
    "                edges_list.remove(edge)\n",
    "        \n",
    "        if not (vertex1 in MST):\n",
    "            MST[vertex1] = []\n",
    "        if not (vertex2 in MST):\n",
    "            MST[vertex2] = []\n",
    "            \n",
    "        MST[vertex1].append([vertex2,weight])\n",
    "        MST[vertex2].append([vertex1,weight])\n",
    "        vertex_num += 1\n",
    "        \n",
    "    return MST\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'1': [['3', 1]],\n",
       " '2': [['3', 5], ['5', 3]],\n",
       " '3': [['1', 1], ['6', 4], ['2', 5]],\n",
       " '4': [['6', 2]],\n",
       " '5': [['2', 3]],\n",
       " '6': [['3', 4], ['4', 2]]}"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Prim(graph.show_edges(),'1')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Minimum Spanning Tree (Kruskal's algorithm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Kruskal(G):\n",
    "    MST = dict()\n",
    "    edges_list = []\n",
    "    edges_list_temp = []\n",
    "    for key in G:\n",
    "        for edge in G[key]:\n",
    "            temp = [key,edge[0]]\n",
    "            temp.reverse()\n",
    "            if temp not in edges_list_temp:\n",
    "                edges_list_temp.append([key,edge[0]])\n",
    "                edges_list.append([key,edge[0],edge[1]])\n",
    "    \n",
    "    edges_list = sorted(edges_list,key = lambda x:x[2])\n",
    "    set_idx = dict()\n",
    "    for key in G.keys():\n",
    "        set_idx[key] = key\n",
    "        \n",
    "    edge_num = 0\n",
    "    for edge in edges_list:\n",
    "        if set_idx[edge[0]] != set_idx[edge[1]]:\n",
    "            edge_num += 1\n",
    "            temp = set_idx[edge[0]]\n",
    "            for key,item in set_idx.items():\n",
    "                if item == temp:\n",
    "                    set_idx[key] = set_idx[edge[1]]\n",
    "                    \n",
    "            if not (edge[0] in MST):\n",
    "                MST[edge[0]] = []\n",
    "            if not (edge[1] in MST):\n",
    "                MST[edge[1]] = []\n",
    "            \n",
    "            MST[edge[0]].append([edge[1],edge[2]])\n",
    "            MST[edge[1]].append([edge[0],edge[2]])\n",
    "\n",
    "            if edge_num == len(G) - 1:\n",
    "                break\n",
    "                \n",
    "    return MST\n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'1': [['3', 1]],\n",
       " '2': [['5', 3], ['3', 5]],\n",
       " '3': [['1', 1], ['6', 4], ['2', 5]],\n",
       " '4': [['6', 2]],\n",
       " '5': [['2', 3]],\n",
       " '6': [['4', 2], ['3', 4]]}"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Kruskal(graph.show_edges())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### DG implemented by adjacency list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DG_al:\n",
    "    def __init__(self):\n",
    "        self.nodes = []\n",
    "        self.edges = {}\n",
    "        \n",
    "    def insert(self,a,b):\n",
    "        if not(a in self.nodes):\n",
    "            self.nodes.append(a)\n",
    "            self.edges[a] = list()\n",
    "        if not (b in self.nodes):\n",
    "            self.nodes.append(b)\n",
    "            self.edges[b] = list()\n",
    "        self.edges[a].append(b)\n",
    "        \n",
    "    def succ(self,a):\n",
    "        return self.edges[a]\n",
    "    \n",
    "    def show_nodes(self):\n",
    "        return self.nodes\n",
    "    \n",
    "    def show_edges(self):\n",
    "        return self.edges\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'0': [],\n",
       " '1': ['0'],\n",
       " '2': ['1'],\n",
       " '3': ['1'],\n",
       " '4': [],\n",
       " '5': ['4', '2'],\n",
       " '6': ['4', '3'],\n",
       " '7': ['5', '6']}"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = DG_al()\n",
    "graph.insert('7','5')\n",
    "graph.insert('7','6')\n",
    "graph.insert('5','4')\n",
    "graph.insert('6','4')\n",
    "graph.insert('5','2')\n",
    "graph.insert('6','3')\n",
    "graph.insert('2','1')\n",
    "graph.insert('3','1')\n",
    "graph.insert('1','0')\n",
    "graph.show_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/g3.png\" width=500 height=500 />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Topological sorting"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def topological_sort(G):\n",
    "    in_degree = dict()\n",
    "    for i in G.keys():\n",
    "        in_degree[i] = 0\n",
    "        for value in G.values():\n",
    "            if i in value:\n",
    "                in_degree[i] += 1\n",
    "    queue = []\n",
    "    visited = []\n",
    "    res = []\n",
    "    for i in range(len(G)):\n",
    "        for j in in_degree:\n",
    "            if j not in visited:\n",
    "                if in_degree[j] == 0:\n",
    "                    queue.append(j)\n",
    "                    visited.append(j)\n",
    "                \n",
    "        vertex = queue.pop(0)\n",
    "        for k in G[vertex]:\n",
    "            in_degree[k] -= 1\n",
    "\n",
    "        res.append(vertex)\n",
    "        \n",
    "    if len(res) != len(G):\n",
    "        print(\"the graph is cyclic\")\n",
    "        return \n",
    "    \n",
    "    return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['7', '5', '6', '2', '4', '3', '1', '0']"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "topological_sort(graph.show_edges())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### WDG implemented by adjacency list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "class WDG_al:\n",
    "    def __init__(self):\n",
    "        self.nodes = []\n",
    "        self.edges = {}\n",
    "        \n",
    "    def insert(self,a,b,weight):\n",
    "        if not(a in self.nodes):\n",
    "            self.nodes.append(a)\n",
    "            self.edges[a] = list()\n",
    "        if not (b in self.nodes):\n",
    "            self.nodes.append(b)\n",
    "            self.edges[b] = list()\n",
    "        self.edges[a].append([b,weight])\n",
    "        \n",
    "    def succ(self,a):\n",
    "        return self.edges[a]\n",
    "    \n",
    "    def show_nodes(self):\n",
    "        return self.nodes\n",
    "    \n",
    "    def show_edges(self):\n",
    "        return self.edges\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'0': [['2', 5], ['3', 3]],\n",
       " '1': [['4', 4]],\n",
       " '2': [['3', 3], ['1', 3], ['4', 3]],\n",
       " '3': [['1', 5]],\n",
       " '4': []}"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = WDG_al()\n",
    "graph.insert('0','2',5)\n",
    "graph.insert('0','3',3)\n",
    "graph.insert('2','3',3)\n",
    "graph.insert('3','1',5)\n",
    "graph.insert('2','1',3)\n",
    "graph.insert('2','4',3)\n",
    "graph.insert('1','4',4)\n",
    "graph.show_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/g4.png\" width=500 height=500 />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Maximum Flow (Edmonds Karp's algorithm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bfs_augmenting_path(src,sink,parent,G):\n",
    "    visited = {k:False for k in G.keys()}\n",
    "    queue = []\n",
    "    queue.append(src)\n",
    "    visited[src] = True\n",
    "    \n",
    "    while queue:\n",
    "        u = queue.pop(0)\n",
    "        for i in G[u]:\n",
    "            node = i[0]\n",
    "            residual_flow = i[1]\n",
    "            if visited[node] == False and residual_flow > 0:\n",
    "                queue.append(node)\n",
    "                visited[node] = True\n",
    "                parent[node] = u\n",
    "                \n",
    "    if visited[sink]:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "        \n",
    "    \n",
    "def Edmonds_Karp(src,sink,G):\n",
    "    parent = {k:None for k in G.keys()}\n",
    "    max_flow = 0\n",
    "    \n",
    "    G_residual = dict()\n",
    "    G_residual = {k:[] for k in G.keys()}\n",
    "\n",
    "    for k,v in G.items():\n",
    "        for i in v:\n",
    "            G_residual[k].append([i[0],i[1]])\n",
    "            G_residual[i[0]].append([k,0])\n",
    "    \n",
    "    \n",
    "    while bfs_augmenting_path(src,sink,parent,G_residual):\n",
    "        path_flow = float('Inf')\n",
    "        temp = sink\n",
    "        while(temp != src):\n",
    "            for i in G_residual[parent[temp]]:\n",
    "                node = i[0]\n",
    "                if node == temp:\n",
    "                    residual_flow = i[1]\n",
    "                    path_flow = min(path_flow,residual_flow)\n",
    "                    break\n",
    "            \n",
    "            temp = parent[temp]\n",
    "        \n",
    "        max_flow += path_flow\n",
    "        v = sink\n",
    "        while(v != src):\n",
    "            u = parent[v]\n",
    "            for i in G_residual[u]:\n",
    "                if i[0] == v:\n",
    "                    i[1] -= path_flow\n",
    "                    break\n",
    "            for i in G_residual[v]:\n",
    "                if i[0] == u:\n",
    "                    i[1] += path_flow\n",
    "                    break\n",
    "            v = parent[v]\n",
    "        \n",
    "    return max_flow\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum Flow from '0' to '4': 7\n"
     ]
    }
   ],
   "source": [
    "print(\"Maximum Flow from '0' to '4':\",Edmonds_Karp('0','4',graph.show_edges()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Maximum Bipartite Matching"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'0': ['3', '4'],\n",
       " '1': ['4', '5'],\n",
       " '2': ['3', '4', '6'],\n",
       " '3': [],\n",
       " '4': [],\n",
       " '5': [],\n",
       " '6': []}"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = DG_al()\n",
    "graph.insert('0','3')\n",
    "graph.insert('0','4')\n",
    "graph.insert('1','4')\n",
    "graph.insert('1','5')\n",
    "graph.insert('2','3')\n",
    "graph.insert('2','4')\n",
    "graph.insert('2','6')\n",
    "graph.show_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/g7.png\" width=200 height=100 />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bipartite_matching(G):\n",
    "    G = {k:[i for i in G[k]] for k in G}\n",
    "    G['src'] = []\n",
    "    G['sink'] = []\n",
    "    for k in G:\n",
    "        if len(G[k]) != 0 and k != 'src' and k != 'sink':\n",
    "            G[k] = [[j,1] for j in G[k]]\n",
    "            G['src'].append([k,1])\n",
    "        elif len(G[k]) == 0 and k != 'src' and k != 'sink':\n",
    "            G[k].append(['sink',1])\n",
    "    \n",
    "    return Edmonds_Karp('src','sink',G)\n",
    "\n",
    "def bfs_augmenting_path(src,sink,parent,G):\n",
    "    visited = {k:False for k in G.keys()}\n",
    "    queue = []\n",
    "    queue.append(src)\n",
    "    visited[src] = True\n",
    "    \n",
    "    while queue:\n",
    "        u = queue.pop(0)\n",
    "        for i in G[u]:\n",
    "            node = i[0]\n",
    "            residual_flow = i[1]\n",
    "            if visited[node] == False and residual_flow > 0:\n",
    "                queue.append(node)\n",
    "                visited[node] = True\n",
    "                parent[node] = u\n",
    "                \n",
    "    if visited[sink]:\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def Edmonds_Karp(src,sink,G):\n",
    "    parent = {k:None for k in G.keys()}\n",
    "    max_flow = 0\n",
    "    \n",
    "    G_residual = dict()\n",
    "    G_residual = {k:[] for k in G.keys()}\n",
    "\n",
    "    for k,v in G.items():\n",
    "        for i in v:\n",
    "            G_residual[k].append([i[0],i[1]])\n",
    "            G_residual[i[0]].append([k,0])\n",
    "    \n",
    "    \n",
    "    while bfs_augmenting_path(src,sink,parent,G_residual):\n",
    "        path_flow = float('Inf')\n",
    "        temp = sink\n",
    "        while(temp != src):\n",
    "            for i in G_residual[parent[temp]]:\n",
    "                node = i[0]\n",
    "                if node == temp:\n",
    "                    residual_flow = i[1]\n",
    "                    path_flow = min(path_flow,residual_flow)\n",
    "                    break\n",
    "            \n",
    "            temp = parent[temp]\n",
    "        \n",
    "        max_flow += path_flow\n",
    "        v = sink\n",
    "        while(v != src):\n",
    "            u = parent[v]\n",
    "            for i in G_residual[u]:\n",
    "                if i[0] == v:\n",
    "                    i[1] -= path_flow\n",
    "                    break\n",
    "            for i in G_residual[v]:\n",
    "                if i[0] == u:\n",
    "                    i[1] += path_flow\n",
    "                    break\n",
    "            v = parent[v]\n",
    "        \n",
    "    return max_flow\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum Bipartite Matching: 3\n"
     ]
    }
   ],
   "source": [
    "print('Maximum Bipartite Matching:',bipartite_matching(graph.show_edges()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Critical Path"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'0': [['1', 2], ['2', 15]],\n",
       " '1': [['4', 19], ['3', 10]],\n",
       " '2': [['1', 4], ['4', 11]],\n",
       " '3': [['5', 6]],\n",
       " '4': [['5', 5]],\n",
       " '5': []}"
      ]
     },
     "execution_count": 91,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = WDG_al()\n",
    "graph.insert('0','1',2)\n",
    "graph.insert('0','2',15)\n",
    "graph.insert('2','1',4)\n",
    "graph.insert('1','4',19)\n",
    "graph.insert('2','4',11)\n",
    "graph.insert('1','3',10)\n",
    "graph.insert('3','5',6)\n",
    "graph.insert('4','5',5)\n",
    "graph.show_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/g5.png\" width=500 height=500 />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {},
   "outputs": [],
   "source": [
    "def _topological_sort_CP(G):\n",
    "    in_degree = dict()\n",
    "    for i in G.keys():\n",
    "        in_degree[i] = 0\n",
    "        for value in G.values():\n",
    "            if i in [v[0] for v in value]:\n",
    "                in_degree[i] += 1\n",
    "    queue = []\n",
    "    visited = []\n",
    "    res = []\n",
    "    for i in range(len(G)):\n",
    "        for j in in_degree:\n",
    "            if j not in visited:\n",
    "                if in_degree[j] == 0:\n",
    "                    queue.append(j)\n",
    "                    visited.append(j)\n",
    "                \n",
    "        vertex = queue.pop(0)\n",
    "        for k in [v[0] for v in G[vertex]]:\n",
    "            in_degree[k] -= 1\n",
    "\n",
    "        res.append(vertex)\n",
    "        \n",
    "    if len(res) != len(G):\n",
    "        print(\"the graph is cyclic\")\n",
    "        return \n",
    "    \n",
    "    return res\n",
    "\n",
    "def critical_path(G):\n",
    "    topo_seq = _topological_sort_CP(G)\n",
    "    ve = {k:0 for k in G.keys()}\n",
    "    for i in topo_seq:\n",
    "        for j in G[i]:\n",
    "            if ve[i]+j[1] > ve[j[0]]:\n",
    "                ve[j[0]] = ve[i]+j[1]\n",
    "    \n",
    "    in_degree = dict()\n",
    "    in_degree = {k:[] for k in G.keys()}\n",
    "    for k,v in G.items():\n",
    "        for i in v:\n",
    "            in_degree[i[0]].append([k,i[1]])\n",
    "    \n",
    "    vl = {k:ve[topo_seq[-1]] for k in G.keys()}\n",
    "    for i in topo_seq[::-1]:\n",
    "        for j in in_degree[i]:\n",
    "            if vl[i]-j[1] < vl[j[0]]:\n",
    "                vl[j[0]] = vl[i]-j[1]\n",
    "    \n",
    "    c_p = []\n",
    "    for i in topo_seq:\n",
    "        for j in G[i]:\n",
    "            if ve[i] == vl[j[0]] - j[1]:\n",
    "                c_p.append([i,j[0],j[1]])\n",
    "    \n",
    "    src = topo_seq[0]\n",
    "    sink = topo_seq[-1]\n",
    "    temp = src\n",
    "    res = []\n",
    "    c_p_sum = 0\n",
    "    while temp != sink:\n",
    "        for i in c_p:\n",
    "            if i[0] == temp:\n",
    "                res.append(i[0])\n",
    "                temp = i[1]\n",
    "                if temp == sink:\n",
    "                    res.append(temp)    \n",
    "                c_p_sum += i[2]\n",
    "                break\n",
    "                \n",
    "    return res,c_p_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "one critical path: ['0', '2', '1', '4', '5']\n",
      "shortest duration: 43\n"
     ]
    }
   ],
   "source": [
    "c_p,c_p_sum = critical_path(graph.show_edges())\n",
    "print(\"one critical path:\",c_p)\n",
    "print('shortest duration:',c_p_sum)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### shortest path between any two vertices (Dijkstra's algorithm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'0': [['1', 4], ['2', 4]],\n",
       " '1': [['0', 4], ['2', 2]],\n",
       " '2': [['0', 4], ['1', 2], ['3', 3], ['5', 6], ['4', 1]],\n",
       " '3': [['2', 3], ['5', 2]],\n",
       " '4': [['2', 1], ['5', 3]],\n",
       " '5': [['2', 6], ['3', 2], ['4', 3]]}"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = WUDG_al()\n",
    "graph.insert('0','1',4)\n",
    "graph.insert('0','2',4)\n",
    "graph.insert('1','2',2)\n",
    "graph.insert('2','3',3)\n",
    "graph.insert('2','5',6)\n",
    "graph.insert('2','4',1)\n",
    "graph.insert('3','5',2)\n",
    "graph.insert('4','5',3)\n",
    "graph.show_edges()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src=\"img/g6.png\" width=500 height=500 />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "import heapq\n",
    "def Dijkstra(src,sink,G):\n",
    "    heap = [(0,src)]\n",
    "    visited = []\n",
    "    while heap:\n",
    "        (cost,u) = heapq.heappop(heap)\n",
    "        if u in visited:\n",
    "            continue\n",
    "        visited.append(u)\n",
    "        if u == sink:\n",
    "            return cost\n",
    "        for v,c in G[u]:\n",
    "            if v in visited:\n",
    "                continue\n",
    "            updated = cost + c\n",
    "            heapq.heappush(heap,(updated,v))\n",
    "            \n",
    "    return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "shortest path from '0' to '5': 8\n"
     ]
    }
   ],
   "source": [
    "print(\"shortest path from '0' to '5':\",Dijkstra('0','5',graph.show_edges()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### shortest path between all the pairs of vertices (Floyd-Warshall algorithm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Floyd_Warshall(G):\n",
    "    adj_matrix = []\n",
    "    temp = sorted(list(G.keys()))\n",
    "    for i in temp:\n",
    "        t_l = []\n",
    "        for j in temp:\n",
    "            if j in [s[0] for s in G[i]]:\n",
    "                for n in G[i]:\n",
    "                    if j == n[0]:        \n",
    "                        t_l.append(n[1])\n",
    "            else:\n",
    "                if j == i:\n",
    "                    t_l.append(0)\n",
    "                else:\n",
    "                    t_l.append(float('Inf'))\n",
    "        adj_matrix.append(t_l)\n",
    "\n",
    "    cost = list(map(lambda i: list(map(lambda j: j, i)), adj_matrix))\n",
    "    for k in range(len(G)):\n",
    "        for i in range(len(G)):\n",
    "            for j in range(len(G)):\n",
    "                cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])\n",
    "    \n",
    "    for i in cost:\n",
    "        for j in i:\n",
    "            print(j,end = ' ')\n",
    "        print('')\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "shortest path between all the pairs of vertices:\n",
      "0 4 4 7 5 8 \n",
      "4 0 2 5 3 6 \n",
      "4 2 0 3 1 4 \n",
      "7 5 3 0 4 2 \n",
      "5 3 1 4 0 3 \n",
      "8 6 4 2 3 0 \n"
     ]
    }
   ],
   "source": [
    "print(\"shortest path between all the pairs of vertices:\")\n",
    "Floyd_Warshall(graph.show_edges())"
   ]
  },
  {
   "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}