Graph_DFS_Implimentations.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Graph DFS Implimentations:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 3 2 1 4 "
     ]
    }
   ],
   "source": [
    "# Iterative DFS traversal from a given source vertex.  \n",
    "# Exhausts all possible moves from the source vertex without visiting any vertices the second time.\n",
    "\n",
    "test_graph = {0: [2, 3], 1: [0,4], 2:[1], 3: [] , 4:[]}\n",
    "\n",
    "class Graph:  \n",
    "    def __init__(self,graph):   \n",
    "        self.graph = graph  \n",
    "        self.visited = []\n",
    "        self.stack = []\n",
    "\n",
    "    def dfs(self, source_node):\n",
    "        self.stack = [source_node]\n",
    "        while len(self.stack) > 0:\n",
    "            next_node = self.stack.pop() # pop the last item\n",
    "            self.visited.append(next_node)\n",
    "            print(next_node, end = ' ')\n",
    "            for i in self.graph[next_node]:\n",
    "                if i not in self.visited and i != None:\n",
    "                    self.stack.append(i)\n",
    "        \n",
    "        \n",
    "g = Graph(test_graph)\n",
    "g.dfs(0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 1, 4, 0, 3]\n",
      "[2, 1, 4, 0, 3]\n",
      "[2, 1, 0, 4, 3]\n",
      "[2, 1, 0, 4, 3]\n"
     ]
    }
   ],
   "source": [
    "# Reminder of the differences of simple dfs and bfs:\n",
    "\n",
    "test_graph = {0: [2, 3], 1: [0,4], 2:[1], 3: [] , 4:[]}\n",
    "\n",
    "# do an iterative dfs with a stack\n",
    "def iterative_dfs(test_graph, source_node):\n",
    "    stack = [source_node]\n",
    "    visited = []\n",
    "    while len(stack) > 0:\n",
    "        next_node = stack.pop() # pop the last item\n",
    "        visited.append(next_node)\n",
    "        for i in test_graph[next_node]:\n",
    "            if i not in visited and i != None:\n",
    "                stack.append(i)\n",
    "    return visited        \n",
    "\n",
    "print(iterative_dfs(test_graph, 2))\n",
    "\n",
    "\n",
    "# do a dfs with recursion\n",
    "def dfs_with_recursion(test_graph, source_node, stack = None, visited = None):\n",
    "    if stack == None: stack = [source_node]\n",
    "    if visited == None: visited = []\n",
    "    if len(stack) > 0:\n",
    "        next_node = stack.pop() # pop the last item\n",
    "        visited.append(next_node)\n",
    "        for i in test_graph[next_node]:\n",
    "            if i not in visited and i != None:\n",
    "                stack.append(i)\n",
    "        dfs_with_recursion(test_graph, next_node, stack, visited)    \n",
    "    return visited    \n",
    "\n",
    "print(dfs_with_recursion(test_graph, 2))\n",
    "\n",
    "\n",
    "# do an iterative bfs with a queue\n",
    "def iterative_bfs(test_graph, source_node):\n",
    "    queue = [source_node]\n",
    "    visited = []\n",
    "    while len(queue) > 0:\n",
    "        next_node = queue.pop(0) # pop the first item\n",
    "        visited.append(next_node)\n",
    "        for i in test_graph[next_node]:\n",
    "            if i not in queue and i not in visited and i != None:\n",
    "                queue.append(i)\n",
    "    return visited        \n",
    "                \n",
    "print(iterative_bfs(test_graph, 2))\n",
    "\n",
    "\n",
    "# do a bfs with recursion\n",
    "def bfs_with_recursion(test_graph, source_node, queue = None, visited = None):\n",
    "    if queue == None: queue = [source_node]\n",
    "    if visited == None: visited = []\n",
    "    if len(queue) > 0:\n",
    "        next_node = queue.pop(0) # pop the first item\n",
    "        visited.append(next_node)\n",
    "        for i in test_graph[next_node]:\n",
    "            if i not in visited and i != None:\n",
    "                queue.append(i)\n",
    "        bfs_with_recursion(test_graph, next_node, queue, visited)    \n",
    "    return visited    \n",
    "    \n",
    "        \n",
    "print(bfs_with_recursion(test_graph, 2))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 1, 1, 1],\n",
       "       [1, 1, 1, 1],\n",
       "       [1, 1, 1, 1],\n",
       "       [0, 0, 0, 1]])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# show transitive closure on a 2D matrix with dfs\n",
    "\n",
    "test_graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}\n",
    "import numpy as np\n",
    "\n",
    "def dfs(u, v, visited, graph):\n",
    "    visited[u][v] = 1\n",
    "    for i in graph[v]: # traverse over the connections of the destination\n",
    "        if i != None and visited[u][i] == 0: # if there has been no connection from u to i\n",
    "            dfs(u, i, visited, graph)\n",
    "\n",
    "\n",
    "def apply_tc(graph):\n",
    "    n = len(graph)\n",
    "    visited = np.zeros([n,n], dtype = int)\n",
    "    for i in graph.keys():\n",
    "        dfs(i, i, visited, graph)\n",
    "    return visited # tc of the graph\n",
    "\n",
    "apply_tc(test_graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "cycle\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[0, 1, 3, 6, 2, 4, 5]"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# checking cycles in a graph traditionally is done with bfs and not dfs:\n",
    "\n",
    "test_graph = {0: [1], 1: [3, 6], 2: [4, 5], 3: [2], 4: [0], 5: [], 6: []}\n",
    "\n",
    "def iterative_bfs(graph, source): \n",
    "    visited = []\n",
    "    queue = [source]\n",
    "    while len(queue) > 0:\n",
    "        curr_node = queue.pop(0) # last item is popped\n",
    "        visited.append(curr_node)\n",
    "        for each_conn in graph[curr_node]:\n",
    "            if each_conn != None and each_conn not in visited:\n",
    "                queue.append(each_conn)\n",
    "            elif each_conn in visited:\n",
    "                print('cycle')\n",
    "    return visited\n",
    "\n",
    "iterative_bfs(test_graph, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "graph contains cyclic connection\n",
      "True\n",
      "[0 0 0 0 2 2 0]\n"
     ]
    }
   ],
   "source": [
    "# Finding cycles in an undirected graph\n",
    "\n",
    "# Detect if there is any cycles in an undirected graph where connections can be seen once\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 is_cyclic(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",
    "            # print(self.parent) # to view how the parent index is changing\n",
    "    \n",
    "    def find_parent(self, i): # reach to the parent with a dfs\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.is_cyclic())\n",
    "# view the parent list after all vertices are seen\n",
    "print(g.parent)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "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 a 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): # a simple dfs\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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1 1 1 0 0]\n",
      " [0 1 0 0 1]\n",
      " [1 0 0 1 1]\n",
      " [0 0 0 0 1]\n",
      " [1 0 1 0 1]] \n",
      " True\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find the number of islands assuming 1s are connected to each other forming an island among sea of zeros\n",
    "# Complexity: O(N x D)\n",
    "\n",
    "import numpy as np\n",
    "class Graph: \n",
    "  \n",
    "    def __init__(self, g): # g is a 2D matrix with random boolean numbers\n",
    "        self.N, self.D = g.shape\n",
    "        self.graph = g \n",
    "  \n",
    "\n",
    "    def within_borders(self, i, j, visited): \n",
    "        # returns true if: i and j are within the boundaries, vertex hasn't been visited, and graph[i][j] is 1 \n",
    "        return (i >= 0 and i < self.N and j >= 0 and j < self.D and visited[i][j] == False \\\n",
    "                and self.graph[i][j] == True) \n",
    "              \n",
    "        \n",
    "    def all_possible_moves(self): # simple permutation to obtain all moves to the neighboring cells\n",
    "        array = [-1,0,1] # all possible moves for either i or j if it starts from 0\n",
    "        k = 2\n",
    "        return self._all_possible_moves(array, k)\n",
    "        \n",
    "        \n",
    "    def _all_possible_moves(self, array, k, sub_array = None, result = None): \n",
    "        if result == None: result = []\n",
    "        if sub_array == None: sub_array = []\n",
    "        if len(sub_array) == k: \n",
    "            result.append(sub_array)\n",
    "            return\n",
    "        for i in range(len(array)):\n",
    "            self._all_possible_moves(array, k, sub_array + [array[i]], result)\n",
    "        return [i for i in result if i != [0,0]] # eliminate the possibility of not moving at all for both indices\n",
    "        \n",
    "    \n",
    "    def store_all_possible_moves(self):\n",
    "        self.row_col_neighbors = self.all_possible_moves() # all possible moves of i and j can take together\n",
    "        \n",
    "        \n",
    "    def DFS(self, i, j, visited): \n",
    "        # row_col_neighbors is simply: [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]] \n",
    "        visited[i][j] = True\n",
    "        for k in self.row_col_neighbors: \n",
    "            r , c = k\n",
    "            if self.within_borders(i + r, j + c, visited) == True: \n",
    "                self.DFS(i + r, j + c, visited) \n",
    "  \n",
    "\n",
    "    def count_islands(self): \n",
    "        self.store_all_possible_moves()\n",
    "        visited = np.zeros([self.N,self.D], dtype = int)\n",
    "        count = 0\n",
    "        for i in range(self.N): \n",
    "            for j in range(self.D): \n",
    "                if visited[i][j] == False and self.graph[i][j] == 1: \n",
    "                    self.DFS(i, j, visited) \n",
    "                    count += 1\n",
    "                    \n",
    "        \n",
    "        print(visited, '\\n' , (visited == graph).all()) # visited should just look like the original graph\n",
    "        return count \n",
    "  \n",
    "  \n",
    "graph = np.array([[1, 1, 1, 0, 0], \n",
    "                  [0, 1, 0, 0, 1], \n",
    "                  [1, 0, 0, 1, 1], \n",
    "                  [0, 0, 0, 0, 1], \n",
    "                  [1, 0, 1, 0, 1]])\n",
    "\n",
    "test_graph = Graph(graph)\n",
    "test_graph.count_islands()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(array([[0, 1, 1, 0, 0],\n",
       "        [0, 1, 0, 0, 1],\n",
       "        [1, 0, 0, 1, 1],\n",
       "        [0, 0, 0, 0, 1],\n",
       "        [1, 0, 1, 0, 1]]), 4)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# count number of islands with only 2 functions \n",
    "\n",
    "test_graph = np.array([[0, 1, 1, 0, 0], \n",
    "                       [0, 1, 0, 0, 1], \n",
    "                       [1, 0, 0, 1, 1], \n",
    "                       [0, 0, 0, 0, 1], \n",
    "                       [1, 0, 1, 0, 1]])\n",
    "\n",
    "    \n",
    "def DFS(i, j, graph, visited, N, D):\n",
    "    visited[i][j] = True\n",
    "    for each_neighbor in [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]: \n",
    "        r , c = each_neighbor\n",
    "        if (i + r) >= 0 and (i + r) < N and (j + c) >= 0 and (j + c) < D: # if within the borders of the matrix\n",
    "            if graph[i+r][j+c] == 1 and visited[i+r][j+c] == 0: \n",
    "                DFS(i + r, j + c, graph, visited, N, D) \n",
    "\n",
    "\n",
    "def count_islands(graph): \n",
    "    N,D = graph.shape\n",
    "    visited = np.zeros([N, D], dtype = int)\n",
    "    count = 0\n",
    "    for i in range(N): \n",
    "        for j in range(D): \n",
    "            if visited[i][j] == False and graph[i][j] == 1: \n",
    "                DFS(i, j, graph, visited, N, D) \n",
    "                count += 1\n",
    "    return visited , count\n",
    "\n",
    "\n",
    "count_islands(test_graph)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Python3 program to find the longest cable length between any two cities with Time Complexity : O(V * (V + E))\n",
    "\n",
    "# There 6 cities index from [0 to 5]. The distance from index 0 to index 1 is 3, the distance from index 1 to 5 is 2..\n",
    "# Here is the visual of the cities and their distances\n",
    "\n",
    "# 0 --- 1 ---- 2\n",
    "#       1 -- 5 ------ 3\n",
    "#            5 ----- 4\n",
    "\n",
    "# matrix representation of an undirected test graph \n",
    "graph = np.array([[0,3,0,0,0,0], \n",
    "                  [3,0,4,0,0,2],\n",
    "                  [0,4,0,0,0,0],\n",
    "                  [0,0,0,0,0,6],\n",
    "                  [0,0,0,0,0,5],\n",
    "                  [0,2,0,6,5,0]])\n",
    "\n",
    "import numpy as np\n",
    "def DFS(graph, src, prev_len, max_len, visited, results): \n",
    "    \n",
    "    visited[src] = True\n",
    "    curr_len = 0\n",
    "    for i in range(len(graph[src])): # for all connections of the source\n",
    "        if graph[src][i] != 0 and visited[i] == False:\n",
    "            each_conn = graph[src][i]\n",
    "            curr_len = prev_len + each_conn \n",
    "            if max_len < curr_len:  \n",
    "                max_len = curr_len \n",
    "            DFS(graph, i, curr_len,  max_len, visited, results) \n",
    "        results.append(max_len)\n",
    "\n",
    "        \n",
    "def longest_distance(graph): \n",
    "    \n",
    "    results = []\n",
    "    max_len = -np.inf\n",
    "    for i in range(len(graph)): \n",
    "        visited = [False] * len(graph)  \n",
    "        DFS(graph, i, 0, max_len, visited, results) \n",
    "  \n",
    "    return max(results) \n",
    "\n",
    "\n",
    "longest_distance(graph)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "# Find a Mother Vertex in a Directed and Connected Graph \n",
    "# Mother Vertex: A vertex v such that all other vertices in graph can be reached by a path from v\n",
    "\n",
    "# Undirected Connected Graphs or Disconnected Graphs can't have a mother vertex. \n",
    "test_graph = {0: [1, 2], 1: [3], 2: [], 3:[], 4: [1],  5: [6, 2], 6: [4, 0]}\n",
    "\n",
    "class Graph:   \n",
    "    def __init__(self, graph): \n",
    "        self.graph = {0: [1, 2], 1: [3], 2: [], 3:[], 4: [1],  5: [6, 2], 6: [4, 0]} # connections\n",
    "\n",
    "    # Do DFS traversal from the specified vertex of the given graph.\n",
    "    # If there is a mother vertex, then a dfs from mother vertex should reach out to all vertices\n",
    "    def DFS(self, k, visited): \n",
    "        visited[k] = True\n",
    "        for v in self.graph[k]: # for each connection \n",
    "            if v != None and visited[v] == False: \n",
    "                self.DFS(v, visited) # visited value becomes the new key for each recursion\n",
    "        return visited\n",
    "            \n",
    "        \n",
    "    def find_mother_vertex(self): \n",
    "        for i in range(len(self.graph)): \n",
    "            visited = [False]*(len(self.graph)) \n",
    "            result = self.DFS(i,visited) \n",
    "            # print(i, result) to view the visited vertices by dfs made from each vertex\n",
    "            if result == [True] * len(self.graph):\n",
    "                return i\n",
    "\n",
    "g = Graph(test_graph)  \n",
    "print(g.find_mother_vertex()) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[2, 0, 1, 3], [2, 0, 3], [2, 1, 3]]"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Python program to print all different paths from a source vertex to a destination vertex with dfs\n",
    "\n",
    "import numpy as np\n",
    "test_graph = {0: [1, 3], 1: [3], 2: [0,1], 3:[]}\n",
    "visited = [False] * len(test_graph)\n",
    "import copy\n",
    "\n",
    "def print_all_paths_from_s_to_d(graph, s, d, visited, path = None, result = None):\n",
    "    if result == None: result = []\n",
    "    if path == None: path = []\n",
    "    visited[s] = True\n",
    "    path.append(s) \n",
    "    if s == d: \n",
    "        sub_result = copy.deepcopy(path)\n",
    "        result.append(sub_result)\n",
    "    for i in graph[s]: \n",
    "        if visited[i] == False: \n",
    "            print_all_paths_from_s_to_d(graph, i, d, visited, path, result) \n",
    "    path.pop() # pop the last item reached and mark it as unvisited\n",
    "    visited[s] = False # reassign the current node to False to go back and find another route\n",
    "    return result\n",
    "\n",
    "print_all_paths_from_s_to_d(test_graph, 2, 3, visited) "
   ]
  }
 ],
 "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
}