Graphs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Network of points connected with lines<br>\n",
    "Points - Nodes, Vertices<br>\n",
    "Lines - Edges, Relationships"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Sum of degrees of all nodes in indirected graph = 2*no. of edges\n",
    "- Sum of indegrees in directed graph = Sum of outdegree in directed graph = no. of edges\n",
    "- Time Complexity of BFS = O(E) = O(v^2) as for each node we are storing it's connected nodes (degree) so total time complexity = sum of degrees = O(E)\n",
    "- Time Complexity of DFS = O(E) = O(v^2) similiarly\n",
    "- To check cycle we will run DFS/ BFS and if we reached to already visited node (not parent in case of undirected then there exist a cycle)\n",
    "- Space Complexity : O(n) for both BFS and DFS\n",
    "- DFS : Recursion/ Stack , BFS : Queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import deque\n",
    "import heapq"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_adj(edges) :\n",
    "    numOfNodes = 1 + max([e[1] for e in edges] + [e[0] for e in\n",
    "    edges])\n",
    "    adj = [[0] * numOfNodes for _ in range(numOfNodes) ]\n",
    "    for e in edges:\n",
    "        adj[e[0]][e[1]] = 1\n",
    "    return adj"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_adj_undirected(edges) :\n",
    "    numOfNodes = 1 + max([e[1] for e in edges] + [e[0] for e in\n",
    "    edges])\n",
    "    adj = [[0] * numOfNodes for _ in range(numOfNodes) ]\n",
    "    for e in edges:\n",
    "        adj[e[0]][e[1]] = adj[e[1]][e[0]] = 1\n",
    "    return adj"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def BFS(adj):\n",
    "    print (\"BFS\")\n",
    "    vis = set( )\n",
    "    n = len(adj)\n",
    "    for i in range(n):\n",
    "        if i in vis:\n",
    "            continue\n",
    "        vis.add(i)\n",
    "        q = deque([i])\n",
    "        while q:\n",
    "            el = q.pop()\n",
    "            print(el, end=\" \")\n",
    "            for adjel in range(n):\n",
    "                if adj[el][adjel] and adjel not in vis:\n",
    "                    vis.add(adjel)\n",
    "                    q.appendleft(adjel)\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def DFS(adj):\n",
    "    print (\"DFS\")\n",
    "    vis = set( )\n",
    "    n = len(adj)\n",
    "    for i in range(n):\n",
    "        if i in vis:\n",
    "            continue\n",
    "        vis.add(i)\n",
    "        q = deque([i])\n",
    "        while q:\n",
    "            el = q.pop()\n",
    "            print(el, end=\" \")\n",
    "            for adjel in range(n):\n",
    "                if adj[el][adjel] and adjel not in vis:\n",
    "                    vis.add(adjel)\n",
    "                    q.append(adjel)\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dir\n",
      "[0, 1, 0, 0, 0, 0, 0, 0]\n",
      "[0, 0, 1, 1, 0, 0, 0, 0]\n",
      "[0, 0, 0, 0, 1, 0, 0, 0]\n",
      "[0, 0, 0, 0, 1, 0, 0, 0]\n",
      "[0, 0, 0, 0, 0, 0, 0, 0]\n",
      "[0, 0, 0, 0, 0, 0, 0, 1]\n",
      "[0, 0, 0, 0, 0, 0, 0, 0]\n",
      "[0, 0, 0, 0, 0, 0, 1, 0]\n",
      "undir\n",
      "[0, 1, 0, 0, 0, 0, 0, 0]\n",
      "[1, 0, 1, 1, 0, 0, 0, 0]\n",
      "[0, 1, 0, 0, 1, 0, 0, 0]\n",
      "[0, 1, 0, 0, 1, 0, 0, 0]\n",
      "[0, 0, 1, 1, 0, 0, 0, 0]\n",
      "[0, 0, 0, 0, 0, 0, 0, 1]\n",
      "[0, 0, 0, 0, 0, 0, 0, 1]\n",
      "[0, 0, 0, 0, 0, 1, 1, 0]\n",
      "BFS\n",
      "0 1 2 3 4 5 7 6 \n",
      "BFS\n",
      "0 1 2 3 4 5 7 6 \n",
      "DFS\n",
      "0 1 3 4 2 5 7 6 \n",
      "DFS\n",
      "0 1 3 4 2 5 7 6 \n"
     ]
    }
   ],
   "source": [
    "adj_dir = create_adj([[0, 1], [1, 2], [1, 3], [2, 4], [3, 4], [5,\n",
    "7], [7, 6]])\n",
    "adj_undir = create_adj_undirected([[0, 1], [1, 2], [1, 3], [2,\n",
    "4], [3, 4], [5, 7], [7, 6]])\n",
    "print(\"dir\")\n",
    "for x in adj_dir:\n",
    "    print(x)\n",
    "print( \"undir\")\n",
    "for x in adj_undir:\n",
    "    print(x)\n",
    "BFS(adj_dir)\n",
    "BFS(adj_undir)\n",
    "DFS(adj_dir)\n",
    "DFS(adj_undir)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def detect_cycle_undirected_bfs(adj):\n",
    "    vis = set()\n",
    "    n = len(adj)\n",
    "    for i in range(n):\n",
    "        if i in vis:\n",
    "            continue \n",
    "        vis.add(i)\n",
    "        q = deque([[i, -1]])\n",
    "        while q:\n",
    "            el, par = q.pop()\n",
    "            for adjel in range(n):\n",
    "                if adj[el][adjel]:\n",
    "                    if adjel not in vis: \n",
    "                        vis.add(adjel)\n",
    "                        q.appendleft([adjel, el])\n",
    "                    elif adjel != par:\n",
    "                        print(f\"cycle found at {el} - {adjel}!\")\n",
    "                        return\n",
    "        print(\"No Cycle\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def detect_cycle_undirected_dfs(adj):\n",
    "    vis = set()\n",
    "    n = len(adj)\n",
    "    for i in range(n):\n",
    "        if i in vis:\n",
    "            continue \n",
    "        vis.add(i)\n",
    "        q = deque([[i, -1]])\n",
    "        while q:\n",
    "            el, par = q.pop()\n",
    "            for adjel in range(n):\n",
    "                if adj[el][adjel]:\n",
    "                    if adjel not in vis: \n",
    "                        vis.add(adjel)\n",
    "                        q.append([adjel, el])\n",
    "                    elif adjel != par:\n",
    "                        print(f\"cycle found at {el} - {adjel}!\")\n",
    "                        return\n",
    "        print(\"No Cycle\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "cycle found at 3 - 4!\n",
      "cycle found at 4 - 2!\n"
     ]
    }
   ],
   "source": [
    "detect_cycle_undirected_bfs(adj_undir)\n",
    "detect_cycle_undirected_dfs(adj_undir)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dfs_recursive(adj, vis, el, par):\n",
    "    vis.add(el)\n",
    "    for adjel in range(len(adj)):\n",
    "        if adj[el][adjel]:\n",
    "            if adjel not in vis:\n",
    "                if dfs_recursive(adj, vis, adjel, el):\n",
    "                    return True\n",
    "            elif adjel != par:\n",
    "                print(f\"cycle found at {el} - {adjel}\")\n",
    "                return True\n",
    "    return False\n",
    "def detect_cycle_undirected_dfs_recursive(adj) :\n",
    "    vis = set()\n",
    "    n = len(adj)\n",
    "    for i in range(n):\n",
    "        if i in vis:\n",
    "            continue\n",
    "        if dfs_recursive(adj, vis, i, -1):\n",
    "            return\n",
    "        print(\"no cycle\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "cycle found at 3 - 1\n"
     ]
    }
   ],
   "source": [
    "detect_cycle_undirected_dfs_recursive(adj_undir)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dfs_recursive_path(adj, vis, path, el):\n",
    "    vis.add(el)\n",
    "    path.add(el)\n",
    "    for adjel in range(len(adj)):\n",
    "        if(adj[el][adjel]):\n",
    "            if adjel in path:\n",
    "                print(f' Cycle exist at {adjel} - {el}')\n",
    "                return True\n",
    "            if adjel in vis:\n",
    "                continue\n",
    "            if dfs_recursive_path(adj, vis, path, adjel):\n",
    "                return True\n",
    "    path.remove(el)\n",
    "    return False\n",
    "        \n",
    "def detect_cycle_directed_dfs_recursive(adj):\n",
    "    vis = set()\n",
    "    n = len(adj)\n",
    "    for i in range(n):\n",
    "        if i in vis:\n",
    "            continue\n",
    "        if dfs_recursive_path(adj, vis, set(), i):\n",
    "            return\n",
    "    print(\"no cycle\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "no cycle\n"
     ]
    }
   ],
   "source": [
    "detect_cycle_directed_dfs_recursive(adj_dir)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Dijkstra's Algorithm\n",
    "- To calculate shortest distance of each node from a given source node\n",
    "- Prerequisite : all weights are +ve only\n",
    "- Take an array of size n (distance) where each index indicate distance of source to index i\n",
    "- Initialise them with inf and distance[source] = 0\n",
    "- let at a time distance from source to x = dx and source to y = dy and we are at vertex x where a edge from x->y of weight p exists. Then distance[y] = min(dy, dx+p)\n",
    "- we can relax (minimize path from only those nodes whose absolute minimum path has been finded else if we update their adjacent node and then in future that node gets updted then we will have to update it's all adjacent nodes and then thei adjacent nodes and so on....\n",
    "- when we have no more vertex left to check whose absolute minimum path is known then we can include that vertex which has least distance from source in the category of absolute minimum path known"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reasoning:\n",
    "1. if sc and destination are the same then dist is 0. if Dist is an array [] where Dist[i] will store the best found shortest distance from sc to i. We write.\n",
    "        Dist [Sc] = 0 which is its absolute shortest distance.\n",
    "        for all other nodes X, we have dist[X]= infinity\n",
    "2. if dist[×] = dx & dis[y] = dy and we discover edge[×][y] = p (meaning wt of edge from × to y is p) such that   dy > dx + p\n",
    "    then we can say dist[y] = dx + p .\n",
    "    or we can say dist[y] = min(dist [y], dist[x] + edge[x][y]) for all nodes × which have an edge to y (process is called <b>relaxation</b>)\n",
    "    This can be updated from every node x that we visit\n",
    "3. We only visit the nodes for which we know we have calculated the absolute shortest path (which will now not be updated).\n",
    "    from start we know only for sc we have an absolute shortest path which is Dist[Sc] = 0 and it can not be updated since\n",
    "    all edges have +ve weight.\n",
    "4. if in a graph we have some nodes A , B, C for which we have found the absolute shortest paths And for rest of the nodes D, E, F we have some paths (no path is a path with weight infinity) at this point we will say the node in D, E, F which has min dist value has its shortest path found and no other path after this which we might find can be shorter\n",
    "\n",
    "   proof:\n",
    "       lets say dist[D] < Dist[E] , Dist[F] - eq A\n",
    "       for a smaller path to be introduced to D via E the following will have to be true\n",
    "       Dist [D] > Dist[E] + W     // W = cumilative weight of a new path from E to D        but from eq A , this can only be true if W ‹ 0 which is false (under pre-requisites)\n",
    "       (for E we can still say it is possible that Dist[E] › dist[D] + W where W can be › 0 because Dist[D] < Dist[E] but not the other way)\n",
    "    same for F also\n",
    "    =› dist[D] now is the absolute shortest path\n",
    "    so now we say we have 4 nodes A, B, C, D for which we know absolute shortest path\n",
    "    E, Fare still not completely explored .\n",
    "    at this point we will visit D and update all the adjecent nodes by point (2) explained above"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "algo:\n",
    "1. mark dist[src] = 0\n",
    "    for all other nodes × dist[x] = inf\n",
    "    for all nodes × visted[x] = false\n",
    "2. while there is any node not vistied: // that is while there exists any node x for which visited[x] == False\n",
    "        x = the node with min dist[x] amongst the nodes which are not visited\n",
    "        visited[x] = True\n",
    "        for all nodes p which are having an edge from x to p and visited[p] is False:\n",
    "                dist[p] = min(dist[p], dist[x] + adj[x][p])\n",
    "Q: why dont we use a min heap instead of visited and dist to find min weight edge ??\n",
    "\n",
    "            Note : time complexity:  v^2\n",
    "           Can be improved by using heaps (nlogn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 40, 60, 50, 80, 90]\n"
     ]
    }
   ],
   "source": [
    "adj =  [[0, 40, 0, 50, 0, 0],\n",
    "        [0, 0, 30, 0, 0, 0],\n",
    "        [0, 0, 0, 0, 20, 50],\n",
    "        [0, 0, 10, 0, 40, 0],\n",
    "        [0, 0, 0, 0, 0, 10],\n",
    "        [0, 0, 0, 0, 0, 0]]\n",
    " \n",
    "# we can also show no edge by -1\n",
    " \n",
    "v = len(adj)\n",
    "inf = 999999999999999999\n",
    "dist = [inf]*v\n",
    "dist[0] = 0\n",
    "visited = [False]*v\n",
    " \n",
    " \n",
    " \n",
    "for i in range(v):\n",
    "    mindist = inf\n",
    "    x = -1\n",
    " \n",
    "    for j in range(v):\n",
    "        if not visited[j] and dist[j] < mindist:\n",
    "            x = j\n",
    "            mindist = dist[j]\n",
    " \n",
    "    visited[x] = True\n",
    " \n",
    "    for j in range(v):\n",
    "        if not visited[j] and adj[x][j] > 0:\n",
    "            dist[j] = min(dist[j], dist[x] + adj[x][j])\n",
    " \n",
    "print(dist)\n",
    " \n",
    " \n",
    "# output:\n",
    " \n",
    "#\n"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note:**<br>\n",
    "we can also use Topological sort and then compute distance starting from all vertex comes first in topological sort as there is no way to reach that vertex so start with it and then relax all it's edges and then next node in topological sort and so on..."
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Topological Sort (Kahn' s Algorithm )\n",
    "If for any task to happen it depend on other to happen first then we can get order to do task by topological sort<br>\n",
    "Algo:\n",
    "   1. For topological sort check cycle first as if cycle is present then no topological sort is possible\n",
    "   2. For all nodes calculate indegree and outdegree\n",
    "   3. All those nodes which have indegree = 0 put them in queue\n",
    "   4. take out element from queue and print it, also decrease indegree of it's adjacent nodes by 1 if any of them becomes 0, put them in queue <br>\n",
    "       Note: So we can use topological sort to detect cycle (if no. of printed nodes are not equal to nodes present in graph then cycle is present<br>\n",
    "       Not a sorting algorithm, Time complexity = O(v)\n",
    "   5. to check cycle if topological sort doesn't produce a array of n size then a cycle is present\n",
    "   6. we can store outdegrees and adjacency list to store outdegrees \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def TopologicalSort(n,graph):\n",
    "    degree = [[0,set()] for i in range(n)]\n",
    "    for edge in graph:\n",
    "        dest, src = edge  #it specifies that if edge is a,b then for a to happen b should happen first\n",
    "        degree[dest][0]+=1\n",
    "        degree[src][1].add(dest)\n",
    "    q = deque([x for x in range(n) if degree[x][0]==0])\n",
    "    order = []\n",
    "    count = n\n",
    "    while q:\n",
    "        el = q.popleft()\n",
    "        order.append(el)\n",
    "        n-=1\n",
    "        for i in degree[el][1]:\n",
    "            degree[i][0]-=1\n",
    "            if degree[i][0] == 0:\n",
    "                q.append(i)\n",
    "    if n!=0:\n",
    "        print(\"cycle present in graph\")\n",
    "        return\n",
    "    for i in order:\n",
    "        print(i, end = \" \")   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "cycle present in graph\n"
     ]
    }
   ],
   "source": [
    "TopologicalSort(6,[[0,1],[1,2],[1,3], [2,3],[3,4],[3,5],[4,5],[5,0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5 4 3 2 1 0 "
     ]
    }
   ],
   "source": [
    "TopologicalSort(6,[[0,1],[1,2],[1,3], [2,3],[3,4],[3,5],[4,5]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Another Method\n",
    "Normal DFS<br>\n",
    "C++ Code :"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "void dfs(vector<bool>& visited, stack<int> &st, int node, vector<int> adj[]){\n",
    "        visited[node] = 1;\n",
    "        for(auto it: adj[node]){\n",
    "            if(!visited[it])\n",
    "                dfs(visited, st, it, adj);\n",
    "        }\n",
    "        st.push(node);\n",
    "    }\n",
    "\tpublic:\n",
    "\t//Function to return list containing vertices in Topological order. \n",
    "\tvector<int> topoSort(int V, vector<int> adj[]) {\n",
    "\t    // code here\n",
    "\t    stack<int> st;\n",
    "\t    vector<bool> visited(V, 0);\n",
    "\t    for(int i=0;i<V;i++){\n",
    "\t        if(!visited[i])\n",
    "\t            dfs(visited,st, i, adj);\n",
    "\t    }\n",
    "\t    vector<int> result;\n",
    "\t    while(!st.empty()){\n",
    "\t        result.push_back(st.top());\n",
    "\t        st.pop();\n",
    "\t    }\n",
    "\t    return result;\n",
    "\t}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Union Find\n",
    "- Used to calculate no. of connected components among graph(forest)\n",
    "- Let us say at a point theere are two different components A and B and then we encounter an edge between one of the node of A to one of the node of B. Then we have to merge both set of vertices\n",
    "- To do it efficiently, we chose any vertex as representaive of A and a representative of B and if there exist a edge between nodes of A and B then we can make representative of A and B as a common representative(either representative of A or B)\n",
    "- updating each node representative takes much time which is not efficient, so we only change the representative of previous representative \n",
    "- For eg.\n",
    "        1,2,3,4,5  - all have 5 as their representative (here we chose right most) \n",
    "        6,7,8,9. - all have 9 as their representative\n",
    "        now there exist an edge between 1 and 7\n",
    "        then we update representative of first set as representative of second set\n",
    "        to do that we set representaive of 5 as 9\n",
    "        now if we search for representaive of 1 then we get 5\n",
    "        and if we again check it's representative we get 9\n",
    "        representaive of 9 is 9 so we stop here and we got representative of 1 as 9"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Redundant Connection Question"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def RedundantConnction(edges):\n",
    "    parent = [x for x in range(1001)] #as maximum no. of nodes are 1000 (given in question)\n",
    "    for edge in edges:\n",
    "        a,b = edge\n",
    "        pa = a\n",
    "        pb = b\n",
    "        while(parent[pa]!=pa):\n",
    "            pa = parent[pa]\n",
    "        while(parent[pb]!=pb):\n",
    "            pb = parent[pb]\n",
    "        if pa==pb:\n",
    "            return [a,b]\n",
    "        parent[pa] = b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bellman Ford Algorithm\n",
    "- condition : there should not be a loop of negative weight (else repeating cycle we get reduce each time weight by passing through loop so we -inf)\n",
    "- we can also check negative weight loops by this algorithm\n",
    "- we wil perform relaxation at each edge (reducing weight to reach vertex)\n",
    "this relaxation will again occur if any change has occurred in previous relaxation of all edges\n",
    "- at max we can perform n-1 iteration and in next iteration if still we can reduce weight i.e., relaxation can occur then a cycle is present in graph (n = no. of nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bellman Ford Algorithm:\n",
    " \n",
    "- Single src shortest path:\n",
    " \n",
    "- Difference between this and dijkstra's algo is that this can support -ve weights assigned to edges. \n",
    " \n",
    "\n",
    " \n",
    "- Pre-requisites:\n",
    "      cycles with total path sum as -ve is not allowed\n",
    " \n",
    " \n",
    "Reasoning:\n",
    " \n",
    "1. if src and destination are same then dist is 0. dist[x][x] is always 0 . that means even though we dont know anything about the distance from Src we we know that \n",
    " \n",
    "\tDist[Src] = 0 which is its absolute shortest distance. \n",
    " \n",
    "\tfor all other nodes X we have dist[X] = infinity\n",
    " \n",
    "2. Relaxation Process:\n",
    " \n",
    "\tif dist[x] = dx & dis[y] = dy and we discover edge[x][y] = p such that \n",
    " \n",
    "\tdy > dx + p \n",
    " \n",
    "\tthen we can say dist[y] = dx + p . or we can say\n",
    " \n",
    "    dist[y] = min(dist[y], dist[x] + edge[x][y]) for all nodes x which have an edge to y\n",
    " \n",
    " \n",
    "3. if we relax all edges and there is a change in some vertice's distance then that change can trigger other changes and we have to redo relaxation for all the nodes again.\n",
    "if distance does not change we can be certain that this is the shortest path for all nodes.\n",
    " \n",
    "4. Max number of times all edges need to be relaxed is n-1 where n is the number of nodes.\n",
    " \n",
    "\tproof:\n",
    "\t\trelaxation starts from src\n",
    " \n",
    "\t\tthe longest path that can be from src to any node (no cycles included) can be of n-1 edges.\n",
    " \n",
    "\t\tand every time atleast on of the edge in this path would get updated (if needed)\n",
    " \n",
    "\t\tso max n - 1 iterations of the relaxation process are required\n",
    " \n",
    " \n",
    "algo:\n",
    " \n",
    "for n-1 times:\n",
    "\tany_edge_updated = False\n",
    "\tfor all edges:\n",
    "\t\tif dist[edge.dest] > edge.wt + dist[edge.src]:\n",
    "\t\t\tdist[edge.dest] = edge.wt + dist[edge.src]\n",
    "\t\t\tany_edge_updated = True\n",
    "\tif not any_edge_updated:\n",
    "\t\tbreak\n",
    " \n",
    "// note that the above code will not update anything if dist[edge.src] is infinity\n",
    " \n",
    "\n",
    " \n",
    "- time complexity:\n",
    "\t**e*v**\n",
    " \n",
    "\tif v is n and we know e is at max v*v-1\n",
    " \n",
    "\t**=> O(n^3)**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 5, 2, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "adj = [[None, 5, 2, None, None],\n",
    "       [None, None, 1, None, None],\n",
    "       [None, None, None, -1, -1],\n",
    "       [1, None, None, None, None],\n",
    "       [3, None, None, 2, None]]\n",
    " \n",
    "inf = 999999999999999\n",
    "n = len(adj)\n",
    "src = 0\n",
    "dist = [inf] * n\n",
    "dist[src] = 0\n",
    " \n",
    "for _ in range(n - 1):\n",
    "    any_edge_updated = False\n",
    "    for nodefrom in range(n):\n",
    "        for nodeto in range(n):\n",
    "            if adj[nodefrom][nodeto] and dist[nodefrom] != inf and dist[nodeto] > adj[nodefrom][nodeto] + dist[nodefrom]:\n",
    "                dist[nodeto] = adj[nodefrom][nodeto] + dist[nodefrom]\n",
    "                any_edge_updated = True\n",
    "        if not any_edge_updated:\n",
    "            break\n",
    " \n",
    "print(dist)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# All Pair Shortest Path\n",
    "- using Bellman Ford we will get it in n*n^3 = n^4time\n",
    "## Floyd Warshall Algorithm\n",
    "- in this we freeze a vertex (let i) and then check for every pair of vertex is their exist a better path having intermediate node as i (can relax them through i)\n",
    "    - so ith row and ith column won't change in adjancency matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Floyd Warshall:\n",
    " \n",
    "- All pair shortest path:\n",
    " \n",
    "- Pre-Requisite:\n",
    "        No negative Cycle\n",
    "1. consider an adjecency matrix A, given to you for a weighted directed graph.\n",
    "    n = number of vertices so A is of size nxn (nodes : 1 to n )\n",
    "     initially, A[i][j] = weight of the edge from i to j, infinity if edge doesn't exist, 0 if i is same as j\n",
    "\n",
    "2. Now we create an A1 matrix by relaxing all values through node 1. \n",
    "    So node 1 and edges directly from node 1 will not change.\n",
    "    => 1st row and col will not change\n",
    "    For others paths i to j \n",
    "        A1[i,j] = min(A[i,j], A[i,1]+A[1,j])\n",
    " \n",
    " \n",
    "3. Do this n times, for all nodes\n",
    " \n",
    "\n",
    "\n",
    " \n",
    " \n",
    " \n",
    "- **TC : n^3**\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def FloydWarshall(adj):\n",
    "    n = len(adj)\n",
    "    A = []\n",
    "    for i in range(n):\n",
    "        m = []\n",
    "        for j in range(n):\n",
    "            if(adj[i][j]==None):\n",
    "                m.append(inf)\n",
    "            else:\n",
    "                m.append(adj[i][j])\n",
    "        A.append(m)\n",
    "    for k in range(n):\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                A[i][j] = min(A[i][j],A[i][k]+A[k][j])\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[2, 5, 2, 1, 1],\n",
       " [1, 6, 1, 0, 0],\n",
       " [0, 5, 2, -1, -1],\n",
       " [1, 6, 3, 2, 2],\n",
       " [3, 8, 5, 2, 4]]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FloydWarshall(adj)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [[None, None, -2, 3],\n",
    "     [2, None, None, None],\n",
    "     [None, None, None, 4],\n",
    "     [None, -1, None, None]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[3, 1, -2, 2], [2, 3, 0, 4], [5, 3, 3, 4], [1, -1, -1, 3]]"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "FloydWarshall(a)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Minimum Spanning Tree\n",
    "- Spanning Tree - a connected graph in which there is no redundant edges. a graph can be made into spanning tree by using Union find algorithm (removing all redundant graph)\n",
    "    - will contain n-1 egdes and have no cycle\n",
    "- Minimum Spanning Tree - a weighted directed graph which is a spanning tree and has least weight(cost) \n",
    "    - minimum cost to connect all nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Prim's Algorithm\n",
    "1. At first we select any node and mark it as visited \n",
    "2. Then we check all the edges connecting a visited node and non-visited node and take edge with minimum weight. We mark that non-visisted node as visited\n",
    "3. using this algorithm till we have no node left in non visited we will get minimum spanning tree\n",
    "4. We can use a priority queue to store edges of a node when we mark it as visited\n",
    "        Note : Can't gauratee a unique answer as there can be multiple edges with same weight\n",
    "**Time Complexity : O(vloge = nlogn)** actual : eloge<br>\n",
    "as e = n^2 so loge = 2logn -> n= v"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Kruskal's Algorithm\n",
    "From all unused edges use edge with minimum weight which is not redundant <br>\n",
    "Intermediate stages are not tree (unlike Prim's which always maintain a tree)<br>\n",
    "we cn store edges in heap and use a count variable to count no. of nodes connected <br>\n",
    "**Time Comlexity  = O(nlogn)**  (e+v)loge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Minimum cost to connect all points "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def MinimumCost(points):\n",
    "    dist = []\n",
    "    n = len(points)\n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            dist.append((abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1]), i, j))\n",
    "    heapq.heapify(dist)\n",
    "    parent = [i for i in range(n)]\n",
    "    MinCost = 0\n",
    "    while(n>1):\n",
    "        d,i,j = heapq.heappop(dist)\n",
    "        while(i!=parent[i]):\n",
    "            i = parent[i]\n",
    "        while(j!=parent[j]):\n",
    "            j = parent[j]\n",
    "        if i!=j:\n",
    "            parent[i] = j\n",
    "            MinCost += d\n",
    "            n-=1\n",
    "    return MinCost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "18"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "points = [ [3,12], [-2,5], [-4,1]]\n",
    "MinimumCost(points)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 1557 Minimum Number of Vertices to Reach All Nodes\n",
    "to connect all nodes we have to take all those nodes which have indegree 0 \n",
    "if a node has a incoming edge then it can be covered from another edge\n",
    "**Find Solution for all Directed Graph**  -- A good question\n",
    "In this question it is given that this graph is acyclic therefore there will be edges whose indegree = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def SmallestSetOfVertices(n, edges):\n",
    "        indegree = [0]*n\n",
    "        for x,y in edges:\n",
    "            indegree[y]+=1\n",
    "        return [x for x in range(n) if indegree[x] == 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def SmallestSetOfVertices2(n, edges):\n",
    "    return set(range (n)) - set(y for x,y in edges) #one liner"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}