Prims_and_Kruskals_MST_algorithms.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Most students confuse SPT and MST algorithms. Here is the difference:\n",
    "\n",
    "#### MST: The minimum spanning tree \n",
    "Prim's and Kruskal's algorithms will be analyzed in this notebook to find MST. These algorithms work only for undirected graphs. Prim's algorithm requires a source vertex to be defined. However, Kruskal's does not require any source vertex to be defined. Prim's algorithm finds the minimal weight spanning tree starting from a given node while continuing to visit each node. Kruskal's algorithm finds minimal weight spanning tree starting from the shortest edges of the nodes that has not been visited while continuing to visit each node\n",
    "\n",
    "A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together. \n",
    "\n",
    "#### SPT: Shortest path tree\n",
    "Check the Djikstra and Bellman-Ford algorithms in this depository to find SPT from single source.\n",
    "Dijkstra and Bellman Ford are both for finding all the shortest paths from a defined single start node to all other nodes. They can be used for directed or undirected graphs. \n",
    "\n",
    "#### Running times of MST & SPT algorithms:\n",
    "DJKSTRA with heapq: O(E*logV), Prims: O(E*log V), KRUSKAL: (E*logE)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "directed graph\n",
      "[[0 1 0 0 0 0 0]\n",
      " [4 0 0 2 0 0 5]\n",
      " [0 0 0 3 2 4 6]\n",
      " [2 0 2 0 0 0 5]\n",
      " [0 0 0 2 0 0 0]\n",
      " [0 0 0 5 0 0 0]\n",
      " [0 0 0 0 0 0 0]] \n",
      "\n",
      "adj list of a directed graph where all connections can be seen in u, v, w format\n",
      "[[0, 1, 1], [1, 0, 4], [1, 3, 2], [1, 6, 5], [2, 3, 3], [2, 4, 2], [2, 5, 4], [2, 6, 6], [3, 0, 2], [3, 2, 2], [3, 6, 5], [4, 3, 2], [5, 3, 5]] \n",
      "\n",
      "undirected graph\n",
      "[[0. 0. 0. 0. 8. 0. 9. 3. 0. 0.]\n",
      " [0. 0. 9. 0. 0. 3. 0. 3. 2. 8.]\n",
      " [0. 9. 0. 0. 3. 0. 7. 1. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 3. 3. 9. 0. 0.]\n",
      " [8. 0. 3. 0. 0. 9. 0. 2. 0. 8.]\n",
      " [0. 3. 0. 3. 9. 0. 6. 0. 2. 5.]\n",
      " [9. 0. 7. 3. 0. 6. 0. 2. 2. 3.]\n",
      " [3. 3. 1. 9. 2. 0. 2. 0. 2. 0.]\n",
      " [0. 2. 0. 0. 0. 2. 2. 2. 0. 8.]\n",
      " [0. 8. 0. 0. 8. 5. 3. 0. 8. 0.]] \n",
      "\n",
      "dictionary view of connections of an undirected graph without the weights\n",
      "{0: [4, 6, 7], 1: [2, 5, 7, 8, 9], 2: [1, 4, 6, 7], 3: [5, 6, 7], 4: [0, 2, 5, 7, 9], 5: [1, 3, 4, 6, 8, 9], 6: [0, 2, 3, 5, 7, 8, 9], 7: [0, 1, 2, 3, 4, 6, 8], 8: [1, 5, 6, 7, 9], 9: [1, 4, 5, 6, 8]} \n",
      "\n",
      "undirected graph where connections can be seen once\n",
      "[[0. 0. 8. 0. 2. 0. 7. 5. 2. 0.]\n",
      " [0. 0. 3. 0. 3. 8. 9. 8. 0. 0.]\n",
      " [0. 0. 0. 0. 1. 0. 0. 0. 5. 0.]\n",
      " [0. 0. 0. 0. 8. 3. 0. 0. 2. 2.]\n",
      " [0. 0. 0. 0. 0. 8. 2. 1. 2. 3.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0. 0. 8.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]] \n",
      "\n",
      "dictionary view of a connections of an undirected graph where connections can be seen once without the weights\n",
      "{0: [4, 6, 7], 1: [2, 5, 7, 8, 9], 2: [1, 4, 6, 7], 3: [5, 6, 7], 4: [0, 2, 5, 7, 9], 5: [1, 3, 4, 6, 8, 9], 6: [0, 2, 3, 5, 7, 8, 9], 7: [0, 1, 2, 3, 4, 6, 8], 8: [1, 5, 6, 7, 9], 9: [1, 4, 5, 6, 8]} \n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Prepare all the test sets for directed graphs, undirected graphs, adjacency lists, and dictionary of connections \n",
    "\n",
    "import numpy as np\n",
    "np.random.seed(0)\n",
    "\n",
    "# Create a directed graph with random integers from 0 to 7, that is size (7,7)\n",
    "probability_set = [0.7, 0.05, 0.05, 0.05, 0.05, 0.05, 0.05]\n",
    "weight_list = np.arange(0,7)\n",
    "directed_graph = np.random.choice(weight_list, p = probability_set, size = (7,7))\n",
    "size = 7\n",
    "for i in range(len(directed_graph)):\n",
    "    for j in range(len(directed_graph[i])):\n",
    "        if i == j: \n",
    "            directed_graph[i][j] = 0\n",
    "print('directed graph')\n",
    "print(directed_graph, '\\n')\n",
    "\n",
    "\n",
    "# create an adjeceny list from a directed graph\n",
    "adj_list = []\n",
    "for i in range(len(directed_graph)): # each row\n",
    "    for j in range(len(directed_graph[i])): # each column\n",
    "        if directed_graph[i][j] == 0:\n",
    "            continue\n",
    "        adj_list.append([i, j, directed_graph[i][j], ]) # i, w, v\n",
    "print('adj list of a directed graph where all connections can be seen in u, v, w format')\n",
    "print(adj_list, '\\n')\n",
    "\n",
    "\n",
    "# create an undirected graph in matrix form (where a---b == b---a)\n",
    "size = 10\n",
    "undirected_graph_matrix = np.zeros([size, size])\n",
    "probability_set = [0.5, 0.05, 0.1, 0.1, 0.03, 0.03, 0.03, 0.01, 0.1, 0.05]\n",
    "vertex_list = np.arange(0,10)\n",
    "for i in range(size): # each vertex\n",
    "    for j in range(size): # immediate connections of each vertex\n",
    "        random_weight = np.random.choice(vertex_list, p = probability_set)\n",
    "        undirected_graph_matrix[i][j] = random_weight\n",
    "        undirected_graph_matrix[j][i] = random_weight\n",
    "        if i == j:\n",
    "            undirected_graph_matrix[i][j] = 0   \n",
    "print('undirected graph')\n",
    "print(undirected_graph_matrix, '\\n')   \n",
    "\n",
    "\n",
    "# create a dictionary to view just the connections of an undirected graph without the weights\n",
    "all_connections = {}\n",
    "for i in range(len(undirected_graph_matrix)): # for each key make a list for values\n",
    "    all_connections[i] =  []  \n",
    "    for j,v in enumerate(undirected_graph_matrix[i]): # each item in the values list\n",
    "        if v == 0:\n",
    "            continue\n",
    "        else:\n",
    "            all_connections[i].append(j)\n",
    "print('dictionary view of connections of an undirected graph without the weights')\n",
    "print(all_connections, '\\n')\n",
    "\n",
    "\n",
    "# create an undirected graph in a matrix format where connections can be seen once\n",
    "size = 10\n",
    "undirected_graph_matrix2 = np.zeros([size, size])\n",
    "probability_set = [0.5, 0.05, 0.1, 0.1, 0.03, 0.03, 0.03, 0.01, 0.1, 0.05]\n",
    "vertex_list = np.arange(0,10)\n",
    "k = -1\n",
    "for i in range(size): # each vertex\n",
    "    k += 1\n",
    "    for j in range(k, size): # immediate connections of each vertex\n",
    "        random_weight = np.random.choice(vertex_list, p = probability_set)\n",
    "        undirected_graph_matrix2[i][j] = random_weight\n",
    "        if i == j:\n",
    "            undirected_graph_matrix2[i][j] = 0   \n",
    "print('undirected graph where connections can be seen once')\n",
    "print(undirected_graph_matrix2, '\\n')    \n",
    "\n",
    "\n",
    "# create a dictionary from an undirected graph where connections can be seen for once\n",
    "all_connections2 = {}\n",
    "for i in range(len(undirected_graph_matrix)): # for each key make a list for values\n",
    "    all_connections2[i] =  []  \n",
    "    for j,v in enumerate(undirected_graph_matrix[i]): # each item in the values list\n",
    "        if v == 0:\n",
    "            continue\n",
    "        else:\n",
    "            all_connections2[i].append(j)\n",
    "print('dictionary view of a connections of an undirected graph where connections can be seen once without the weights')\n",
    "print(all_connections2, '\\n')\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Given an undirected graph, determine if it contains cycle:\n",
    "\n",
    "Approach 1: DFS from an arbitrary vertex and keep going until you see a market vertex but this has a potential danger since it traverses back and forth and sees the already seen vertices, you may not count the node where it is seen. The worst case would be O(V+E)\n",
    "\n",
    "Approach 2: Weighted Quick Union UF object:\n",
    "For each edge, check if the two vertices are connected, if not union them. Iterate through all vertices. If they are already connected, it means there is a cycle. Worst case is O(V + Elog*V) if path compressionn is applied"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "graph contains cyclic connection\n",
      "True\n",
      "[0 0 0 0 2 2 0]\n"
     ]
    }
   ],
   "source": [
    "# Detect if there is any cycles in an undirected graph where connections can be seen once\n",
    "# Prepare the test set as dict of connections \n",
    "test_graph_cycle = {0: [1], 1: [3, 6], 2: [4, 5], 3: [2], 4: [0], 5: [], 6: []} # 2--4--0 cycle is added\n",
    "\n",
    "class Graph: \n",
    "    def __init__(self, graph): \n",
    "        self.graph = graph # default dictionary to store graph in adj list format\n",
    "        self.parent = np.arange(0, len(self.graph))\n",
    "         \n",
    "            \n",
    "    def isCyclic(self):  \n",
    "        for k,v in self.graph.items(): \n",
    "            for each_value in v: \n",
    "                x = self.find_parent(k)  \n",
    "                y = self.find_parent(each_value) \n",
    "                if x == y: \n",
    "                    print('graph contains cyclic connection')\n",
    "                    return True \n",
    "                else: # union them (assign the item's parent in the value to the key's parent)\n",
    "                    self.parent[y] = x \n",
    "\n",
    "    def find_parent(self, i): \n",
    "        if self.parent[i] != i: # has no parent return the index\n",
    "            return self.find_parent(self.parent[i])\n",
    "        else: # has a parent return the parent's index\n",
    "            return self.parent[i] \n",
    "  \n",
    "\n",
    "    \n",
    "# Create a graph given in the above diagram \n",
    "g = Graph(test_graph_cycle) \n",
    "# test the class\n",
    "print(g.isCyclic())\n",
    "# view the parent list after all vertices are seen\n",
    "print(g.parent)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None\n",
      "[0 0 0 0 0 0 0] [2. 0. 1. 0. 0. 0. 0.]\n"
     ]
    }
   ],
   "source": [
    "# Apply path compression and union by rank method on an acyclic directed graph and detect cycles\n",
    "# Prepare a test set as a dictionary view of an acyclic undirected graph where connections seen once\n",
    "\n",
    "test_conn = test_graph_cycle = {0: [1], 1: [3, 6], 2: [4, 5], 3: [2], 4: [], 5: [], 6: []}\n",
    "    \n",
    "class Graph2():\n",
    "    def __init__(self, graph):\n",
    "        self.graph = graph \n",
    "        self.parent = np.arange(0, len(graph)) # initialize the parent of the vertex to itself \n",
    "        self.rank = np.zeros(len(graph)) # all ranks start from zero for each vertex\n",
    "                \n",
    "        \n",
    "    def is_graph_cyclic(self):\n",
    "        for k,v in self.graph.items(): # for each vertex\n",
    "            k_parent = self.find_parent(k)\n",
    "            for j in v: # for each connection of each vertex\n",
    "                j_parent = self.find_parent(j)\n",
    "                if k_parent == j_parent:\n",
    "                    return True\n",
    "                else:\n",
    "                    self.union(k_parent, j_parent)\n",
    "        \n",
    "        \n",
    "    def find_parent(self, vertex):\n",
    "        if self.parent[vertex] != vertex:\n",
    "            self.parent[vertex] = self.find_parent(self.parent[vertex])\n",
    "        return self.parent[vertex]\n",
    "             \n",
    "    \n",
    "    def union(self, u, v): # path compression and union by rank \n",
    "        if self.rank[u] > self.rank[v]:\n",
    "            self.parent[v] = u\n",
    "        elif self.rank[u] < self.rank[v]:\n",
    "            self.parent[u] = v\n",
    "        else: # if the ranks are the same\n",
    "            self.parent[v] = u\n",
    "            self.rank[u] += 1\n",
    "            \n",
    "\n",
    "            \n",
    "gtest = Graph2(test_conn)\n",
    "print(gtest.is_graph_cyclic())\n",
    "# view the parent and rank after all vertices are visited\n",
    "print(gtest.parent, gtest.rank)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0. 0. 0. 0. 8. 0. 9. 3. 0. 0.]\n",
      " [0. 0. 9. 0. 0. 3. 0. 3. 2. 8.]\n",
      " [0. 9. 0. 0. 3. 0. 7. 1. 0. 0.]\n",
      " [0. 0. 0. 0. 0. 3. 3. 9. 0. 0.]\n",
      " [8. 0. 3. 0. 0. 9. 0. 2. 0. 8.]\n",
      " [0. 3. 0. 3. 9. 0. 6. 0. 2. 5.]\n",
      " [9. 0. 7. 3. 0. 6. 0. 2. 2. 3.]\n",
      " [3. 3. 1. 9. 2. 0. 2. 0. 2. 0.]\n",
      " [0. 2. 0. 0. 0. 2. 2. 2. 0. 8.]\n",
      " [0. 8. 0. 0. 8. 5. 3. 0. 8. 0.]]\n",
      "[[2, 7, 1.0], [7, 2, 1.0], [1, 8, 2.0], [4, 7, 2.0], [5, 8, 2.0], [6, 7, 2.0], [6, 8, 2.0], [7, 4, 2.0], [7, 6, 2.0], [7, 8, 2.0], [8, 1, 2.0], [8, 5, 2.0], [8, 6, 2.0], [8, 7, 2.0], [0, 7, 3.0], [1, 5, 3.0], [1, 7, 3.0], [2, 4, 3.0], [3, 5, 3.0], [3, 6, 3.0], [4, 2, 3.0], [5, 1, 3.0], [5, 3, 3.0], [6, 3, 3.0], [6, 9, 3.0], [7, 0, 3.0], [7, 1, 3.0], [9, 6, 3.0], [5, 9, 5.0], [9, 5, 5.0], [5, 6, 6.0], [6, 5, 6.0], [2, 6, 7.0], [6, 2, 7.0], [0, 4, 8.0], [1, 9, 8.0], [4, 0, 8.0], [4, 9, 8.0], [8, 9, 8.0], [9, 1, 8.0], [9, 4, 8.0], [9, 8, 8.0], [0, 6, 9.0], [1, 2, 9.0], [2, 1, 9.0], [3, 7, 9.0], [4, 5, 9.0], [5, 4, 9.0], [6, 0, 9.0], [7, 3, 9.0]]\n",
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "# Prepare an undirected graph in matrix form where connections can be seen once to write Kruskal's\n",
    "\n",
    "test_matrix = undirected_graph_matrix\n",
    "print(undirected_graph_matrix)\n",
    "\n",
    "# represent the matrix connection as an adjacency list\n",
    "adj_list = []\n",
    "for i in range(len(test_matrix)):\n",
    "    for j in range(len(test_matrix[i])):\n",
    "        if i != j and test_matrix[i][j] != 0:\n",
    "            adj_list.append([i,j, test_matrix[i][j]]) # the representation is source, target, weight as u, v, w\n",
    "print(sorted(adj_list, key = lambda x: x[2]))\n",
    "\n",
    "\n",
    "# view thnumber of vertices:\n",
    "V = list(set([i[0] for i in adj_list] + [i[1] for i in adj_list]))\n",
    "print(V)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[2, 7, 1.0], [1, 8, 2.0], [4, 7, 2.0], [5, 8, 2.0], [6, 7, 2.0], [6, 8, 2.0], [0, 7, 3.0], [3, 5, 3.0], [6, 9, 3.0]]\n"
     ]
    }
   ],
   "source": [
    "# Write Kruskals to find the MST of a given adjacency list representation of an undirected graph \n",
    "\n",
    "class Kruskals_MST():\n",
    "    def __init__(self, connections): # the connections format is [[u,v,w], ..] as adjacency list\n",
    "        self.connections = sorted(connections, key = lambda item : item[2]) \n",
    "        # assign the parents list to indices of vertices\n",
    "        self.parent = np.arange(len(test_matrix))\n",
    "        # initial ranks are assigned to 0\n",
    "        self.rank = np.zeros(len(test_matrix))\n",
    "        \n",
    "        \n",
    "    def find_parent(self, item):\n",
    "        if self.parent[item] != item:\n",
    "            return self.find_parent(self.parent[item])\n",
    "        else:\n",
    "            return item\n",
    "        \n",
    "       \n",
    "    def create_MST(self):\n",
    "        self.MST = []\n",
    "        i = 0 # each item's index that will be in the MST\n",
    "        e = 0 # each item in connections list\n",
    "        while i < (len(self.parent) - 1) and e < len(self.connections):\n",
    "            # MST can only have V-1 number of items in it. This length will cover to visit all vertices\n",
    "            u, v, w = self.connections[e]\n",
    "            u_parent = self.find_parent(u)\n",
    "            v_parent = self.find_parent(v)\n",
    "            if u_parent != v_parent:\n",
    "                self.MST.append(self.connections[e])\n",
    "                self.union(u_parent, v_parent)\n",
    "                i += 1\n",
    "            e +=1\n",
    "        return self.MST\n",
    "   \n",
    "        \n",
    "    def union(self, vertex1, vertex2): # union by rank and path compression\n",
    "        if self.rank[vertex1] > self.rank[vertex2]:\n",
    "            self.parent[vertex2] = self.parent[vertex1]\n",
    "        elif self.rank[vertex1] < self.rank[vertex2]: \n",
    "            self.parent[vertex1] = self.parent[vertex2]\n",
    "        else: # only increase the rank of one of the vertices if both have the same rank\n",
    "            self.parent[vertex1] = self.parent[vertex2]\n",
    "            self.rank[vertex1] += 1\n",
    "        \n",
    "        \n",
    "test_kruskals = Kruskals_MST(adj_list)\n",
    "print(test_kruskals.create_MST())\n",
    "# print(test_kruskals.parent)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "result: [[0, 7, 3.0], [7, 2, 1.0], [7, 4, 2.0], [7, 6, 2.0], [7, 8, 2.0], [8, 1, 2.0], [8, 5, 2.0], [6, 3, 3.0], [6, 9, 3.0]]\n"
     ]
    }
   ],
   "source": [
    "# Apply prims algorithm to find the MST from a defined starting vertex of the test graph\n",
    "# input is unsorted adj list\n",
    "\n",
    "test_matrix = undirected_graph_matrix\n",
    "\n",
    "def Prims(vertex, adj_list): \n",
    "  \n",
    "    # initialize empty edges array and empty MST\n",
    "    MST = []\n",
    "    edges = []\n",
    "    visited = []\n",
    "\n",
    "    # run prims algorithm until we create an MST that contains every vertex from the graph\n",
    "    while len(MST) < len(test_matrix) - 1:\n",
    "    \n",
    "        # mark this vertex as visited, vertex = 0 is initially chosen.\n",
    "        visited.append(vertex)\n",
    "\n",
    "        # add each edge to list of potential edges\n",
    "        for r in range(0, len(adj_list)): # this loop will only append the current vertex's connections. \n",
    "            edge = adj_list[r]\n",
    "            if edge[0] == vertex and edge[2] != 0:\n",
    "                edges.append(edge)\n",
    "        # find edge with the smallest weight to a vertex that has not yet been visited\n",
    "        minEdge = [None,None,np.inf]\n",
    "        for e in range(0, len(edges)):\n",
    "            if edges[e][2] < minEdge[2] and edges[e][1] not in visited:\n",
    "                minEdge = edges[e]\n",
    "        \n",
    "        # push min edge to MST\n",
    "        MST.append(minEdge)\n",
    "        # start at new vertex and reset min edge\n",
    "        vertex = minEdge[1]\n",
    "        # remove the used edge from the edges list\n",
    "        edges.remove(minEdge)\n",
    "        \n",
    "        \n",
    "    return MST \n",
    "  \n",
    "# pass the # of vertices and the graph to run prims algorithm \n",
    "#%timeit prims(0, adj_list)\n",
    "print('result:', Prims(0, adj_list))"
   ]
  },
  {
   "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}