minimum spanning tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Minimum Spanning Tree\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "Minimum spanning tree is a subset of a graph, where every vertex is connected to at least one other vertex, but at most connected to two other vertices, that indicates no cycle, and the total weight of the graph is the minimum possible. Lol, long definition!\n",
    "\n",
    "&nbsp;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "os.chdir('K:/ecole/github')\n",
    "\n",
    "#graph adt\n",
    "#check the below link for more details\n",
    "# https://github.com/je-suis-tm/graph-theory/blob/master/graph.py\n",
    "import graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#we need an undirected graph\n",
    "#in another word, vertices with edge connections \n",
    "#are mutually connected to each other\n",
    "ADT=graph.graph()\n",
    "\n",
    "ADT.append(1,2,6)\n",
    "ADT.append(1,3,5)\n",
    "ADT.append(2,1,6)\n",
    "ADT.append(2,4,8)\n",
    "ADT.append(2,6,3)\n",
    "ADT.append(3,1,5)\n",
    "ADT.append(3,4,2)\n",
    "ADT.append(3,5,7)\n",
    "ADT.append(4,2,8)\n",
    "ADT.append(4,3,2)\n",
    "ADT.append(4,5,7)\n",
    "ADT.append(5,3,3)\n",
    "ADT.append(5,4,7)\n",
    "ADT.append(5,7,9)\n",
    "ADT.append(6,2,3)\n",
    "ADT.append(6,7,5)\n",
    "ADT.append(7,5,9)\n",
    "ADT.append(7,6,5)\n",
    "ADT.append(7,8,13)\n",
    "ADT.append(8,7,13)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](./preview/minimum%20spanning%20tree%20origin.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prim's Algorithm\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "Prim's algorithm is perfect for a minimum spanning tree problem. The algorithm is somewhat similar to BFS. We start from one vertex and check its child vertices. In BFS, we pop vertices by left to right order. In Prim, we only pop the vertex with minimum weight and ignore the rest. When all available vertices have been popped, we obtain a minimum spanning tree.\n",
    "\n",
    "Details of Prim's algorithm can be found in the following link\n",
    "\n",
    "http://interactivepython.org/runestone/static/pythonds/Graphs/PrimsSpanningTreeAlgorithm.html\n",
    "\n",
    "\n",
    "Details of BFS can be found in the following link\n",
    "\n",
    "https://github.com/je-suis-tm/graph-theory/blob/master/BFS%20DFS%20on%20DCG.ipynb\n",
    "\n",
    "&nbsp;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "#different starting point may end up with a different tree\n",
    "def prim(ADT,start):\n",
    "    \"\"\"Prim's Algorithm to find a minimum spanning tree\"\"\"\n",
    "    \n",
    "    #we use a dictionary instead of a list as queue\n",
    "    #cuz we need to pop the vertex with minimum weight on the edge\n",
    "    queue={}\n",
    "    queue[start]=0\n",
    "    \n",
    "    #route keeps track of how we travel from one vertex to another\n",
    "    route={}\n",
    "    route[start]=start\n",
    "    \n",
    "    #result is a list that keeps the order of vertices we have visited\n",
    "    result=[]\n",
    "    \n",
    "    while queue:\n",
    "                \n",
    "        #note that when we have two vertices with the same minimum weights\n",
    "        #the dictionary would pop the one with the smallest key\n",
    "        current=min(queue,key=queue.get)\n",
    "        queue.pop(current)\n",
    "        result.append(current)\n",
    "        ADT.visit(current)\n",
    "        \n",
    "        #BFS\n",
    "        for i in ADT.edge(current):\n",
    "            if i not in queue and ADT.go(i)==0:\n",
    "                queue[i]=ADT.weight(current,i)\n",
    "                route[i]=current\n",
    "                \n",
    "            #every time we find a smaller weight\n",
    "            #we need to update the smaller weight in queue\n",
    "            if i in queue and queue[i]>ADT.weight(current,i):\n",
    "                queue[i]=ADT.weight(current,i)\n",
    "                route[i]=current               \n",
    "    \n",
    "    #create minimum spanning tree\n",
    "    subset=graph.graph()\n",
    "    for i in result:\n",
    "        if i!=start:\n",
    "            subset.append(route[i],i,ADT.weight(route[i],i))\n",
    "            subset.append(i,route[i],ADT.weight(route[i],i))\n",
    "\n",
    "    return subset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: {3: 5, 2: 6},\n",
       " 3: {1: 5, 4: 2, 5: 7},\n",
       " 4: {3: 2},\n",
       " 2: {1: 6, 6: 3},\n",
       " 6: {2: 3, 7: 5},\n",
       " 7: {6: 5, 8: 13},\n",
       " 5: {3: 7},\n",
       " 8: {7: 13}}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MST=prim(ADT,1)\n",
    "\n",
    "ADT.clear(whole=True)\n",
    "\n",
    "MST.reveal()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](./preview/minimum%20spanning%20tree%20subset.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Kruskal's Algorithm\n",
    "\n",
    "&nbsp;\n",
    "\n",
    "Kruskal is another algorithm to get minimum spanning tree. Unlike Prim, Kruskal cannot select where to expand the tree. Kruskal requires all edges in the graph ADT to be sorted. Those edges are stored inside a queue by ascending order. The algorithm iterates through the queue and picks out the edge with the smallest weight, as long as the edge doesn't create a cycle in the subset, the edge will be added into the subset. When the iteration stops, a minimum spanning tree is born.\n",
    "\n",
    "&nbsp;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#use disjoint set to detect cycle\n",
    "def trace_root(disjointset,target):\n",
    "    \"\"\"Use recursion to trace root in a disjoint set\"\"\"\n",
    "\n",
    "    if disjointset[target]!=target:\n",
    "        trace_root(disjointset,disjointset[target])\n",
    "    else:\n",
    "        return target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "#unlike prim, kruskal does not require starting vertex\n",
    "#it always starts with the edge with the minimum weight\n",
    "def kruskal(ADT):\n",
    "    \"\"\"Kruskal's Algorithm to find the minimum spanning tree\"\"\"\n",
    "    \n",
    "    #use dictionary to sort edges by weight\n",
    "    D={}  \n",
    "    for i in ADT.vertex():\n",
    "        for j in ADT.edge(i):\n",
    "            \n",
    "            #convert edge into string\n",
    "            #as the graph is bidirected\n",
    "            #we only need one edge for each pair of two vertices\n",
    "            if f'{j}-{i}' not in D.keys():\n",
    "                D[f'{i}-{j}']=ADT.weight(i,j)\n",
    "                \n",
    "    sort_edge_by_weight=sorted(D.items(), key=lambda x:x[1])    \n",
    "    \n",
    "    result=[]\n",
    "    \n",
    "    #to achieve minimum spanning tree\n",
    "    #we need to avoid cycles\n",
    "    #here we use disjointset to detect cycle\n",
    "    #for more details, you can go to geeksforgeeks\n",
    "    # https://www.geeksforgeeks.org/union-find/\n",
    "    disjointset={}\n",
    "    \n",
    "    #lets skip the part where default=-1\n",
    "    for i in ADT.vertex():\n",
    "        disjointset[i]=i\n",
    "        \n",
    "    for i in sort_edge_by_weight:\n",
    "        \n",
    "        parent=int(i[0].split('-')[0])\n",
    "        child=int(i[0].split('-')[1])\n",
    "                \n",
    "        #first we need to check disjoint set\n",
    "        #if it already has indicated cycle\n",
    "        #trace_root function will go to infinite loops\n",
    "        if disjointset[parent]!=disjointset[child]:\n",
    "            \n",
    "            #if we trace back to the root of the tree\n",
    "            #and it indicates no cycle\n",
    "            #we update the disjoint set and add edge into result\n",
    "            if trace_root(disjointset,parent)!=trace_root(disjointset,child):\n",
    "                disjointset[child]=parent\n",
    "                result.append([parent,child])                \n",
    "                \n",
    "    #create minimum spanning tree\n",
    "    subset=graph.graph()\n",
    "    for i in result:\n",
    "        subset.append(i[0],i[1],ADT.weight(i[0],i[1]))\n",
    "        subset.append(i[1],i[0],ADT.weight(i[0],i[1]))\n",
    "\n",
    "    return subset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{3: {4: 2, 1: 5, 5: 7},\n",
       " 4: {3: 2},\n",
       " 2: {6: 3, 1: 6},\n",
       " 6: {2: 3, 7: 5},\n",
       " 1: {3: 5, 2: 6},\n",
       " 7: {6: 5, 8: 13},\n",
       " 5: {3: 7},\n",
       " 8: {7: 13}}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MST=kruskal(ADT)\n",
    "\n",
    "ADT.clear(whole=True)\n",
    "\n",
    "MST.reveal()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](./preview/minimum%20spanning%20tree%20subset.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Borůvka's Algorithm\n",
    "&nbsp;\n",
    "\n",
    "Borůvka is the oldest algorithm for minimum spanning tree. The logic is very similar to Kruskal. We can almost say Kruskal is based upon Borůvka. Basically for each vertex, we try to find its edge with the minimum weight\n",
    "after the first iteration. We will end up with a few connected components. The second iteration is similar to the first. For each pair of connected components, we try to find the edge with minimum weight to connect. After two rounds of iterations, we are left with a minimum spanning tree.\n",
    "\n",
    "&nbsp;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "#borůvka requires another algorithm to detect connected components\n",
    "#here i use dfs\n",
    "def boruvka(ADT):    \n",
    "    \"\"\"Borůvka's Algorithm to find the minimum spanning tree\"\"\"\n",
    "    \n",
    "    subset=graph.graph()\n",
    "    \n",
    "    #get the edge with minimum weight for each vertex\n",
    "    for i in ADT.vertex():\n",
    "        minimum=float('inf')\n",
    "        target=None\n",
    "        for j in ADT.edge(i):\n",
    "            if ADT.weight(i,j)<minimum:\n",
    "                minimum=ADT.weight(i,j)\n",
    "                target=[i,j]\n",
    "        \n",
    "        #as the graph is undirected\n",
    "        #we append both edges\n",
    "        subset.append(target[0],target[1],ADT.weight(target[0],target[1]))\n",
    "        subset.append(target[1],target[0],ADT.weight(target[0],target[1]))\n",
    "\n",
    "    \n",
    "    #use dfs topological sort to find connected components\n",
    "    #details of topological sort can be found in the following link\n",
    "    # https://github.com/je-suis-tm/graph-theory/blob/master/topological%20sort.ipynb\n",
    "    connected_components=[]\n",
    "    for i in subset.vertex():\n",
    "        \n",
    "        #avoid duplicates of connected components\n",
    "        #use jump to break out of multiple loops\n",
    "        jump=False\n",
    "        for j in connected_components:\n",
    "            if i in j:\n",
    "                jump=True\n",
    "                break\n",
    "        if jump:\n",
    "            continue\n",
    "        connected_components.append(list(graph.dfs_topo_sort(subset,i)))\n",
    "    \n",
    "    #connect 2 connected components with minimum weight\n",
    "    #same logic as the first iteration\n",
    "    for i in range(len(connected_components)):\n",
    "        for j in range(i+1,len(connected_components)):\n",
    "            minimum=float('inf')\n",
    "            target=None\n",
    "            for k in connected_components[i]:\n",
    "                for l in ADT.edge(k):\n",
    "                    if l in connected_components[j]:\n",
    "                        if ADT.weight(k,l)<minimum:\n",
    "                            minimum=ADT.weight(k,l)\n",
    "                            target=[k,l]\n",
    "            \n",
    "            subset.append(target[0],target[1],minimum)\n",
    "            subset.append(target[1],target[0],minimum)\n",
    "                  \n",
    "    return subset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1: {3: 5, 2: 6},\n",
       " 3: {1: 5, 4: 2, 5: 3},\n",
       " 2: {6: 3, 1: 6},\n",
       " 6: {2: 3, 7: 5},\n",
       " 4: {3: 2},\n",
       " 5: {3: 3},\n",
       " 7: {6: 5, 8: 13},\n",
       " 8: {7: 13}}"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MST=boruvka(ADT)\n",
    "\n",
    "ADT.clear(whole=True)\n",
    "\n",
    "MST.reveal()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](./preview/minimum%20spanning%20tree%20subset.jpg)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Time Complexity Comparison\n",
    "&nbsp;\n",
    "\n",
    "See how Prim revolutionized the minimum spanning tree?\n",
    "\n",
    "&nbsp;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "45.6 µs ± 523 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "MST=graph.prim(ADT,1)\n",
    "\n",
    "ADT.clear(whole=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "61 µs ± 723 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "MST=graph.kruskal(ADT)\n",
    "\n",
    "ADT.clear(whole=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "64.1 µs ± 1.01 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)\n"
     ]
    }
   ],
   "source": [
    "%%timeit\n",
    "\n",
    "MST=graph.boruvka(ADT)\n",
    "\n",
    "ADT.clear(whole=True)"
   ]
  },
  {
   "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}