Lab-06 Minimum Spanning Trees - Solved.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Minimum Spanning Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this assignment, we will implement the two minimum spanning tree algorithms: Prim's and Kruskal's."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Graph Class\n",
    "\n",
    "The following class is used for inputting the graphs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graph:\n",
    "    def __init__(self, edges, directed=False):\n",
    "        self.adj_list = {}\n",
    "        self.directed = directed\n",
    "        print(\"length:\",len(edges))\n",
    "        for u, v, k in edges:\n",
    "            self.add_edge(u, v, k)\n",
    "            \n",
    "    def _add_edge_single(self, u, v, k):\n",
    "        \"\"\"Internal function. Do not use directly.\n",
    "        Add a single edge to the graph.\n",
    "        \"\"\"\n",
    "        if u not in self.adj_list:\n",
    "            self.adj_list[u] = []\n",
    "        self.adj_list[u].append((v, k))        \n",
    "                \n",
    "    def add_edge(self, u, v, k):\n",
    "        \"\"\"Add an edge to the graph. Add the reverse edge \n",
    "        when the graph is undirected.\"\"\"\n",
    "        self._add_edge_single(u, v, k)\n",
    "        if not self.directed:\n",
    "            self._add_edge_single(v, u, k)\n",
    "    \n",
    "    def neighbors(self, u):\n",
    "        \"\"\"Return the list of neighbors and the \n",
    "        corresponding weights of u\"\"\"\n",
    "        return self.adj_list[u]\n",
    "    \n",
    "    \n",
    "    def vertices(self):\n",
    "        \"\"\"Return the set of vertices of the graph\"\"\"\n",
    "        return self.adj_list.keys()\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prim's Algorithm\n",
    "\n",
    "Implement the Prim's algorithm in the following cell. Return a hash with nodes as keys and the corresponding parents as values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add any functions/classes as necessary.\n",
    "\n",
    "# q : (parent , weight)\n",
    "q={}\n",
    "\n",
    "def extract_min():\n",
    "    \n",
    "    global q\n",
    "    l=[]\n",
    "#     l(weight,vertex_name)\n",
    "    for i in q:\n",
    "        l.append((q[i][1],i))\n",
    "        \n",
    "\n",
    "    mn = min(l)\n",
    "    print(\"min\",mn[1])\n",
    "\n",
    "    return(mn[1])\n",
    "\n",
    "def prim(g, s):\n",
    "    # Your code here\n",
    "    global q\n",
    "    p = {}\n",
    "    \n",
    "    q[s] = (None,0)\n",
    "    \n",
    "    for i in g.vertices()-[s]:\n",
    "        q[i]= (None,float('inf'))\n",
    "\n",
    "       \n",
    "    while q:\n",
    "        print(\"q\" ,q)\n",
    "        u = extract_min()\n",
    "        print(\"u \" ,u)\n",
    "        parent = q[u][0]\n",
    "        q.pop(u)\n",
    "        print(\"======================\")\n",
    "        print(\"new q \",q)\n",
    "        p[u] = parent\n",
    "        \n",
    "        for v in g.neighbors(u):\n",
    "\n",
    "            if v[0] in q:\n",
    "                node = q[v[0]]\n",
    "                if(node[1] > v[1]):\n",
    "                    q[v[0]] = (u , v[1])\n",
    "\n",
    "                \n",
    "                \n",
    "    for i in p:\n",
    "        print(i, \":\" , p[i])\n",
    "    return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "length: 14\n",
      "q {0: (None, 0), 1: (None, inf), 2: (None, inf), 3: (None, inf), 4: (None, inf), 5: (None, inf), 6: (None, inf), 7: (None, inf), 8: (None, inf)}\n",
      "min 0\n",
      "u  0\n",
      "======================\n",
      "new q  {1: (None, inf), 2: (None, inf), 3: (None, inf), 4: (None, inf), 5: (None, inf), 6: (None, inf), 7: (None, inf), 8: (None, inf)}\n",
      "q {1: (0, 4), 2: (None, inf), 3: (None, inf), 4: (None, inf), 5: (None, inf), 6: (None, inf), 7: (0, 8), 8: (None, inf)}\n",
      "min 1\n",
      "u  1\n",
      "======================\n",
      "new q  {2: (None, inf), 3: (None, inf), 4: (None, inf), 5: (None, inf), 6: (None, inf), 7: (0, 8), 8: (None, inf)}\n",
      "q {2: (1, 8), 3: (None, inf), 4: (None, inf), 5: (None, inf), 6: (None, inf), 7: (0, 8), 8: (None, inf)}\n",
      "min 2\n",
      "u  2\n",
      "======================\n",
      "new q  {3: (None, inf), 4: (None, inf), 5: (None, inf), 6: (None, inf), 7: (0, 8), 8: (None, inf)}\n",
      "q {3: (2, 7), 4: (None, inf), 5: (2, 4), 6: (None, inf), 7: (0, 8), 8: (2, 2)}\n",
      "min 8\n",
      "u  8\n",
      "======================\n",
      "new q  {3: (2, 7), 4: (None, inf), 5: (2, 4), 6: (None, inf), 7: (0, 8)}\n",
      "q {3: (2, 7), 4: (None, inf), 5: (2, 4), 6: (8, 6), 7: (8, 7)}\n",
      "min 5\n",
      "u  5\n",
      "======================\n",
      "new q  {3: (2, 7), 4: (None, inf), 6: (8, 6), 7: (8, 7)}\n",
      "q {3: (2, 7), 4: (5, 10), 6: (5, 2), 7: (8, 7)}\n",
      "min 6\n",
      "u  6\n",
      "======================\n",
      "new q  {3: (2, 7), 4: (5, 10), 7: (8, 7)}\n",
      "q {3: (2, 7), 4: (5, 10), 7: (6, 1)}\n",
      "min 7\n",
      "u  7\n",
      "======================\n",
      "new q  {3: (2, 7), 4: (5, 10)}\n",
      "q {3: (2, 7), 4: (5, 10)}\n",
      "min 3\n",
      "u  3\n",
      "======================\n",
      "new q  {4: (5, 10)}\n",
      "q {4: (3, 9)}\n",
      "min 4\n",
      "u  4\n",
      "======================\n",
      "new q  {}\n",
      "0 : None\n",
      "1 : 0\n",
      "2 : 1\n",
      "8 : 2\n",
      "5 : 2\n",
      "6 : 5\n",
      "7 : 6\n",
      "3 : 2\n",
      "4 : 3\n"
     ]
    }
   ],
   "source": [
    "# Test cell (from CLRS)\n",
    "\n",
    "graph = Graph([(0, 1, 4), (0, 7, 8), (1, 2, 8), (1, 7, 11), (2, 3, 7), (2, 8, 2), (2, 5, 4), (3, 4, 9), (3, 5, 14), (4, 5, 10), (5, 6, 2), (6, 7, 1), (6, 8, 6), (7, 8, 7)])\n",
    "\n",
    "def check_parents(mst, parents, n):\n",
    "    for i in range(n):\n",
    "        if mst[i] != parents[i]:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "mst = prim( graph , 0 )\n",
    "sol1 = [None, 0, 1, 2, 3, 2, 5, 6, 2]\n",
    "sol2 = [None, 0, 5, 2, 3, 6, 7, 0, 2]\n",
    "\n",
    "assert check_parents(mst, sol1, 9) or check_parents(mst, sol2, 9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Kruskal's Algorithm\n",
    "\n",
    "Next we implement the Kruskal's Minimum Spanning Tree algorithm. For doing that, we first need to implment the Union and Find algorithms."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# the Union Find algorithms\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, nodes):\n",
    "        # nodes is a list of nodes. Associate an identifier for each node.\n",
    "        self.set = {}\n",
    "        for i in nodes:\n",
    "            self.set[i] = i\n",
    "            \n",
    "        \n",
    "    def find(self, u):\n",
    "        # Return the representative element (identifier/label) for u\n",
    "        return self.set[u]\n",
    "        \n",
    "    def union(self, u, v):\n",
    "        # Make the representative elements correponding to u and v the same.\n",
    "        x = self.find(u)\n",
    "        y = self.find(v)\n",
    "        self.set[v] = self.set[u]\n",
    "        for i in self.set:\n",
    "            if(self.set[i] == x):\n",
    "                self.set[i] =y\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7 7\n"
     ]
    }
   ],
   "source": [
    "# Test\n",
    "\n",
    "nodes = [2, 3, 4, 5, 6, 7]\n",
    "uf = UnionFind(nodes)\n",
    "\n",
    "for i in range(len(nodes)):\n",
    "    for j in range(i+1, len(nodes)):\n",
    "        assert uf.find(nodes[i]) != uf.find(nodes[j])\n",
    "        \n",
    "\n",
    "uf.union(4, 7)\n",
    "print(uf.find(4), uf.find(7))\n",
    "assert uf.find(4) == uf.find(7)\n",
    "\n",
    "uf.union(4, 2)\n",
    "\n",
    "assert uf.find(4) == uf.find(2) and uf.find(4) == uf.find(7)\n",
    "\n",
    "assert uf.find(4) != uf.find(5)\n",
    "assert uf.find(4) != uf.find(6)\n",
    "assert uf.find(4) != uf.find(3)\n",
    "\n",
    "uf.union(3, 5)\n",
    "\n",
    "assert uf.find(3) == uf.find(5)\n",
    "assert uf.find(4) != uf.find(3)\n",
    "assert uf.find(6) != uf.find(3)\n",
    "\n",
    "uf.union(5, 2)\n",
    "\n",
    "for k in [3, 4, 5, 7]:\n",
    "    assert uf.find(k) == uf.find(2)\n",
    "    \n",
    "assert uf.find(2) != uf.find(6)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the UnionFind class, implement the Kruskal's algorithm in the following cell. Output the __set__ of edges included in the MST. Return the edges as pairs $(u, v)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Add any functions/classes as necessary.\n",
    "\n",
    "def insertion_sort(alist):\n",
    "    for i, kv in enumerate(alist):\n",
    "        for j in range(i-1, -1, -1):\n",
    "            if(alist[j][0] > kv[0]):\n",
    "                alist[j+1]= alist[j]\n",
    "            else:\n",
    "                break\n",
    "\n",
    "            alist[j]=kv    \n",
    "    return alist \n",
    "\n",
    "def kruskal(g):\n",
    "    mst_edges = set()\n",
    "    # Your code here\n",
    "    edges=[]\n",
    "    \n",
    "    \n",
    "    make_set = UnionFind([u for u in g.adj_list])\n",
    "    \n",
    "    print(g.adj_list)\n",
    "    for u in g.adj_list:\n",
    "        for v in g.neighbors(u):\n",
    "            edges.append((v[1],u,v[0]))\n",
    "    edges = insertion_sort(edges)\n",
    "\n",
    "    \n",
    "    for i in edges:\n",
    "        if make_set.find(i[1]) != make_set.find(i[2]):\n",
    "\n",
    "            mst_edges.add((i[1], i[2]))\n",
    "            make_set.union(i[1], i[2])\n",
    "        \n",
    "\n",
    "    # Return the MST.\n",
    "    print(\"edges : \",mst_edges)\n",
    "    return mst_edges\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{0: [(1, 4), (7, 8)], 1: [(0, 4), (2, 8), (7, 11)], 7: [(0, 8), (1, 11), (6, 1), (8, 7)], 2: [(1, 8), (3, 7), (8, 2), (5, 4)], 3: [(2, 7), (4, 9), (5, 14)], 8: [(2, 2), (6, 6), (7, 7)], 5: [(2, 4), (3, 14), (4, 10), (6, 2)], 4: [(3, 9), (5, 10)], 6: [(5, 2), (7, 1), (8, 6)]}\n",
      "edges :  {(0, 1), (5, 6), (2, 8), (7, 6), (0, 7), (2, 3), (2, 5), (3, 4)}\n"
     ]
    },
    {
     "ename": "AssertionError",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-7-fc80b4dbbdeb>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0msol2\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mset\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m1\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m1\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m2\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m8\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m5\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m2\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m3\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m4\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m6\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m7\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0;36m6\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0;36m5\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      6\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 7\u001b[0;31m \u001b[0;32massert\u001b[0m \u001b[0mmst\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0msol1\u001b[0m \u001b[0;32mor\u001b[0m \u001b[0mmst\u001b[0m \u001b[0;34m==\u001b[0m \u001b[0msol2\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      8\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mAssertionError\u001b[0m: "
     ]
    }
   ],
   "source": [
    "# Test for Kruskal's \n",
    "\n",
    "mst = kruskal( graph )\n",
    "sol1 = set([(0, 1), (0, 7), (2, 8), (2, 5), (2, 3), (3, 4), (6, 7), (6, 5)])\n",
    "sol2 = set([(0, 1), (1, 2), (2, 8), (2, 5), (2, 3), (3, 4), (6, 7), (6, 5)])\n",
    "\n",
    "assert mst == sol1 or mst == sol2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}