Graph_BFS_and_DFS_Implimentations.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n",
      "4\n",
      "[[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"
     ]
    }
   ],
   "source": [
    "# count number of islands with only 2 functions and compare DFS and BFS solutions\n",
    "\n",
    "import copy\n",
    "import numpy as np\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 count_islands_bfs_with_queue(test_graph):\n",
    "    graph = np.copy(test_graph)\n",
    "    N, D = graph.shape\n",
    "    count = 0\n",
    "    for i in range(N):\n",
    "        for j in range(D):\n",
    "            if graph[i][j] == 1:\n",
    "                BFS_with_queue(graph, i, j)\n",
    "                count += 1\n",
    "    return count\n",
    "\n",
    "\n",
    "def BFS_with_queue(graph, r, c): # making a change in the original graph and marking 0 values for each traverse\n",
    "    N, D = graph.shape\n",
    "    queue = []\n",
    "    queue.append((r, c))\n",
    "    graph[r][c] = 0\n",
    "    while queue:\n",
    "        directions = [[-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 1], [1, -1], [1, 0], [1, 1]]\n",
    "        r, c = queue.pop(0)\n",
    "        for d in directions:\n",
    "            m, k = d   \n",
    "            if r + m >= 0 and r+m < N and c + k >= 0 and c + k < D and graph[r+m][c+k] == 1:\n",
    "                queue.append((r+m, c+k))\n",
    "                graph[r+m][c+k] = 0\n",
    "\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 count\n",
    "\n",
    "\n",
    "print(count_islands(test_graph))\n",
    "print(count_islands_bfs_with_queue(test_graph))\n",
    "print(test_graph)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 1 0 1 0 1]\n",
      " [1 0 1 0 1 0]\n",
      " [0 1 0 1 0 1]\n",
      " [1 0 1 0 1 0]\n",
      " [0 1 0 1 0 1]\n",
      " [1 0 1 0 1 0]]\n"
     ]
    }
   ],
   "source": [
    "# create a densely connected test graph where there are 2 sets of nodes, colored either with 0 or 1. \n",
    "# Make sure no nodes are connected to its own kind. The 1's in the graph means there is an edge between these nodes.\n",
    "\n",
    "# Edges between vertices:\n",
    "\n",
    "# 0 -- 1   0 -- 3   0 -- 5\n",
    "   \n",
    "# 2 -- 3   2 -- 1   2 -- 5\n",
    "  \n",
    "# 4 -- 5   4 -- 1   4 -- 3\n",
    "\n",
    "# with the reverse edges, makes total 18 directed connections between 6 nodes (noted with 1) in the below matrix\n",
    "\n",
    "import numpy as np\n",
    "m = 6\n",
    "raw_matrix = np.zeros([m, m], dtype = int)\n",
    "for i in range(len(raw_matrix)): # for each row\n",
    "    for j in range(len(raw_matrix[0])): # for each column\n",
    "        if i % 2 == 0 and j % 2 == 1: # if the i index is even and j is odd\n",
    "            raw_matrix[i][j] = 1\n",
    "        if i % 2 == 1 and j % 2 == 0: # if the in index is odd and j is even\n",
    "            raw_matrix[i][j] = 1\n",
    "\n",
    "print(raw_matrix)\n",
    "\n",
    "test_matrix = raw_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 0, 1, 0, 1, 0]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# BFS implimentation to check bipartiteness. \n",
    "# Use the test matrix above to test the function below\n",
    "            \n",
    "def check_if_bipartite(matrix): \n",
    "   \n",
    "    # Create a color list for each vertex\n",
    "    color_list = [-1] * len(matrix) # assign -1 to each vertex, the vertices later will take 0 or 1\n",
    "\n",
    "    # Assign first color to source vertex, pick the first vertex as source vertex for convenience\n",
    "    color_list[0] = 1\n",
    "\n",
    "    # Create a queue (FIFO) of vertex numbers and enqueue source vertex for BFS traversal \n",
    "    queue = [] \n",
    "    queue.append(0) # add the first vertex as source vertex to start the BFS\n",
    "\n",
    "    while len(queue) > 0: \n",
    "\n",
    "        # pop the the first vertex to see its connections\n",
    "        u = queue.pop(0) # queue will push from the end (append) and pop from the head (pop(0))\n",
    "        \n",
    "        # Return false if there is a self-loop \n",
    "        if matrix[u][u] == 1: return False\n",
    "        \n",
    "        for v in range(len(matrix)): # check all connections of the selected vertex\n",
    "            \n",
    "            # if an edge from u to v exists and destination v is not visited, color v into a different group\n",
    "            if matrix[u][v] == 1 and color_list[v] == -1: \n",
    "                # if u is 0 then v is 1, or if u is 1 then v is 0\n",
    "                color_list[v] = 1 - color_list[u]\n",
    "                # push the vertex v into the queue\n",
    "                queue.append(v) \n",
    "\n",
    "            # if an edge from u to v exists but both vertices have the same color, return False\n",
    "            elif matrix[u][v] == 1 and color_list[v] == color_list[u]: return False\n",
    "            \n",
    "    \n",
    "    print(color_list) # view the color list\n",
    "    return True\n",
    "\n",
    "        \n",
    "check_if_bipartite(test_matrix)               \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "network of the optimized graph with the max flow:\n",
      "[[ 0. 16.  7.  0.  0.  0.]\n",
      " [ 0.  0.  8. 12.  0.  0.]\n",
      " [ 6.  6.  0.  9. 11.  0.]\n",
      " [ 0.  0.  0.  0.  0. 19.]\n",
      " [ 0.  0.  3.  7.  0.  4.]\n",
      " [ 0.  0.  0.  1.  0.  0.]]\n",
      "max flow:  23.0 \n",
      "\n",
      "original capacities: \n",
      " [[ 0. 16. 13.  0.  0.  0.]\n",
      " [ 0.  0. 10. 12.  0.  0.]\n",
      " [ 0.  4.  0.  0. 14.  0.]\n",
      " [ 0.  0.  9.  0.  0. 20.]\n",
      " [ 0.  0.  0.  7.  0.  4.]\n",
      " [ 0.  0.  0.  0.  0.  0.]]\n"
     ]
    }
   ],
   "source": [
    "# Maximum flow implimentation of a network of connections with the help of BFS \n",
    "# Rendition of the wikipedia solution at https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Graph: \n",
    "   \n",
    "    def __init__(self, graph): \n",
    "        self.graph = np.copy(graph) # graph with max flow capacities from each vertex \n",
    "        \n",
    "    # Returns tne maximum flow from s to t in the given graph \n",
    "    def max_flow_edmonds_karp(self, source, sink): \n",
    "        N, D = self.graph.shape\n",
    "        # initialize a parent array\n",
    "        parent = -np.ones(D, dtype = int) \n",
    "  \n",
    "        # augment the flow while there is path from source to sink, \n",
    "        # for each path between source and sink, the parent array is continually updated with BFS\n",
    "        while self.BFS(source, sink, parent):\n",
    "            \n",
    "            # Find minimum residual capacity (or max flow) of the edges along the path filled by BFS. \n",
    "            min_path_flow = np.inf \n",
    "            t = sink # initialize target as sink \n",
    "            \n",
    "            # from sink to source traverse all parents and find the min flow between all vertices\n",
    "            while(t !=  source): \n",
    "                min_path_flow = min(min_path_flow, self.graph[parent[t]][t]) \n",
    "                t = parent[t] \n",
    "  \n",
    "            # update residual capacities of the edges and reverse edges along the path \n",
    "            v = sink \n",
    "            while(v !=  source): \n",
    "                u = parent[v] \n",
    "                self.graph[u][v] -= min_path_flow \n",
    "                self.graph[v][u] += min_path_flow \n",
    "                v = parent[v] \n",
    "        # the residual network is updated\n",
    "    \n",
    "        # extract the optimized network flow from the optimized residual network\n",
    "        updated_network = self.draw_the_updated_network_flow()\n",
    "        \n",
    "        print('network of the optimized graph with the max flow:')\n",
    "        print(updated_network) # to view the network in equilibrium (when in is equal to out)\n",
    "        # assert that total amount dispatched from source is equal to the total amount received at target \n",
    "        assert(np.sum(updated_network[source , :]) == np.sum(updated_network[: , sink]))\n",
    "        # the max flow into the system at equilibrium is ready to output\n",
    "        return np.sum(updated_network[source, :]) # sum of all inputs from the source vertex into the network\n",
    "    \n",
    " \n",
    "    # simple BFS checks if there is a path from s to t, and returns T or F of a changing graph with a parent array\n",
    "    def BFS(self, source, target, parent): \n",
    "        # parent array is an additional feature that will keep being updated for each time BFS is run\n",
    "  \n",
    "        # Mark all the vertices as not visited \n",
    "        visited =[False]*(len(self.graph)) \n",
    "        \n",
    "        # Create a queue for BFS \n",
    "        queue=[] \n",
    "          \n",
    "        # Mark the source node as visited and enqueue it \n",
    "        queue.append(source) \n",
    "        visited[source] = True\n",
    "           \n",
    "         # Standard BFS Loop \n",
    "        while len(queue) > 0: \n",
    "            #Dequeue a vertex from queue and print it \n",
    "            u = queue.pop(0) \n",
    "            visited[u] = True\n",
    "            # Get all adjacent vertices of the dequeued vertex u that have not been visited, \n",
    "            # mark them visited and then enqueue  \n",
    "            for i in range(len(self.graph[u])): \n",
    "                # check if the index is not visited and graph has a value at [u][i] that is being updated\n",
    "                if visited[i] == False and self.graph[u][i] > 0:\n",
    "                    # append the vertex to the queue, mark it as True, update parent for all connecting vertices \n",
    "                    queue.append(i) \n",
    "                    parent[i] = u \n",
    "        \n",
    "        # if we reached sink in BFS starting from source, then return true, else false \n",
    "        # equilibrium is reached when source vertex output == target vertex input \n",
    "        # when self.graph[target vertex][vertex_at_i_index] == 0 so that visited[t] returns FALSE\n",
    "        return visited[target] # returns True if visited[t] else it returns False (flow conservation)\n",
    "\n",
    "    \n",
    "    def draw_the_updated_network_flow(self):\n",
    "        # transpose of the final residual graph would be the graph with the optimized max flow \n",
    "        n , d = self.graph.shape\n",
    "        updated_graph = np.zeros([d, n], dtype = float)\n",
    "        for i in range(n):\n",
    "            for j in range(d):\n",
    "                updated_graph[j][i] = self.graph[i][j]\n",
    "        return updated_graph\n",
    "    \n",
    "    \n",
    "    \n",
    "test_graph = np.array([[0, 16, 13, 0, 0, 0], \n",
    "                       [0, 0, 10, 12, 0, 0], \n",
    "                       [0, 4, 0, 0, 14, 0], \n",
    "                       [0, 0, 9, 0, 0, 20], \n",
    "                       [0, 0, 0, 7, 0, 4], \n",
    "                       [0, 0, 0, 0, 0, 0]] , dtype = float)\n",
    "  \n",
    "\n",
    "g = Graph(test_graph) \n",
    "print('max flow: ', g.max_flow_edmonds_karp(0, 5), '\\n') \n",
    "print('original capacities:', '\\n', np.array(test_graph)) # view the original flow of the network\n",
    " # to view how the graph has been shaped to its final form\n",
    "\n",
    "    \n",
    "# The above implementation of Ford Fulkerson Algorithm is called Edmonds-Karp Algorithm. \n",
    "# The idea of Edmonds-Karp is to use BFS in Ford Fulkerson implementation as BFS which always picks a path \n",
    "# with minimum number of edges. When BFS is used, the worst case time complexity can be reduced to O(VE2).\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "23.0"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Edmonds-Karp of max flow with 2 functions:\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "def max_flow_edmonds_karp(graph, source, sink): \n",
    "    N, D = graph.shape\n",
    "    # initialize a parent array\n",
    "    parent = -np.ones(D, dtype = int) \n",
    "    while BFS(graph, source, sink, parent):\n",
    "        # Find minimum residual capacity (or max flow) of the edges along the path filled by BFS. \n",
    "        min_path_flow = np.inf \n",
    "        t = sink # initialize target as sink \n",
    "        # from sink to source traverse all parents and find the min flow between all vertices\n",
    "        while(t !=  source): \n",
    "            min_path_flow = min(min_path_flow, graph[parent[t]][t]) \n",
    "            t = parent[t]\n",
    "        # update residual capacities of the edges and reverse edges along the path \n",
    "        v = sink \n",
    "        while(v !=  source): \n",
    "            u = parent[v] \n",
    "            graph[u][v] -= min_path_flow \n",
    "            graph[v][u] += min_path_flow \n",
    "            v = parent[v] \n",
    "    # the residual network is updated\n",
    "\n",
    "    return np.sum(graph.T[source, :]) # sum of all inputs from the source vertex into the network\n",
    "\n",
    "\n",
    "# simple BFS checks if there is a path from s to t, and returns T or F of a changing graph with a parent array\n",
    "def BFS(graph, source, target, parent): \n",
    "    visited =[False]*(len(graph)) \n",
    "    queue = [source]  \n",
    "    visited[source] = True\n",
    "    while len(queue) > 0: \n",
    "        u = queue.pop(0) \n",
    "        visited[u] = True\n",
    "        for i in range(len(graph[u])): \n",
    "            # check if the index is not visited and graph has a value at [u][i] that is being updated\n",
    "            if visited[i] == False and graph[u][i] > 0:\n",
    "                # append the vertex to the queue, mark it as True, update parent for all connecting vertices \n",
    "                queue.append(i) \n",
    "                parent[i] = u \n",
    "\n",
    "    return visited[target] # returns True if visited[t] else it returns False (flow conservation)\n",
    "\n",
    "max_flow_edmonds_karp(test_graph, 0, 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 0 0 1 0 1]\n",
      " [1 0 1 0 0 0]\n",
      " [1 0 0 0 0 0]\n",
      " [0 1 1 0 1 0]\n",
      " [0 1 0 1 1 0]\n",
      " [0 0 0 0 0 1]]\n",
      "[-1, -1, -1, 0, -1, -1]\n",
      "[1, -1, -1, 0, -1, -1]\n",
      "[1, -1, 1, 0, -1, -1]\n",
      "[2, -1, 1, 0, -1, -1]\n",
      "[2, 3, 1, 0, -1, -1]\n",
      "[2, 3, 1, 0, 3, -1]\n",
      "[2, 4, 1, 0, 3, -1]\n",
      "[2, 4, 1, 0, 3, 5]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(6, [2, 4, 1, 0, 3, 5])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Python program to find maximal bipartite matching. \n",
    "# Use DFS instead of BFS.\n",
    "\n",
    "import numpy as np\n",
    "    \n",
    "class bpm: \n",
    "    def __init__(self, graph): \n",
    "        self.graph = graph  # people are the rows (N) and (D) jobs are the columns\n",
    "  \n",
    "\n",
    "    # create a function that returns maximum number of matching \n",
    "    # for each applicant initialize a seen list and see if dfs returns True for this applicant \n",
    "    def max_bipartite_match(self): \n",
    "        # create a job match list that will keep track of which applicant gets which job\n",
    "        # the job array will be filled with the applicant's index number\n",
    "        jobs_array = [-1] * len(self.graph)\n",
    "          \n",
    "        # Count of jobs assigned to applicants \n",
    "        result = 0 \n",
    "        for each_applicant in range(len(self.graph)): # for each applicant, create a seen array\n",
    "              \n",
    "            # Mark all jobs as not seen for next applicant and do a dfs search\n",
    "            seen_jobs = [False] * len(self.graph)\n",
    "              \n",
    "            # if the applicant i can get a job increase the max number of jobs by one\n",
    "            if self.dfs(each_applicant, jobs_array, seen_jobs): \n",
    "                result += 1\n",
    "   \n",
    "        # print(jobs_array) # view the final form of the applicants array that matched people to jobs\n",
    "        return result , jobs_array\n",
    "    \n",
    "    \n",
    "    # create a function that returns true if a matching is posibble while updating the job matching list\n",
    "    def dfs(self, u, jobs_array, seen_jobs): \n",
    "        # for each job, see if there is a connection already and if that job is already seen\n",
    "        for v in range(len(self.graph)): \n",
    "            # if applicant u is interested in job v and v is not seen \n",
    "            if self.graph[u][v] > 0 and seen_jobs[v] == False: \n",
    "                # mark job as visited \n",
    "                seen_jobs[v] = True \n",
    "                # if the job has not been assigned yet or the previously assigned person has an alternative job,\n",
    "                # give this job to the previous person. applicants[v] means which candidate has job v?\n",
    "                # if applicants[v] == -1 or self.dfs(applicants[v], applicants, seen_jobs): \n",
    "                if jobs_array[v] == -1 or self.dfs(jobs_array[v], jobs_array, seen_jobs):\n",
    "                    # update the match list\n",
    "                    jobs_array[v] = u \n",
    "                    print(jobs_array) # to view the updates on the jobs array\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "    \n",
    "test_matrix = np.array([[0, 0, 0, 1, 0, 1],\n",
    "                        [1, 0, 1, 0, 0, 0],\n",
    "                        [1, 0, 0, 0, 0, 0],\n",
    "                        [0, 1, 1, 0, 1, 0],\n",
    "                        [0, 1, 0, 1, 1, 0],\n",
    "                        [0, 0, 0, 0, 0, 1]])\n",
    "g = bpm(test_matrix)\n",
    "print(g.graph) # reminder of the graph\n",
    "g.max_bipartite_match() # max number of matches, jobs list just to view who got which job\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(6, [2, 4, 1, 0, 3, 5])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Simplified version of maximal bipartite matching.\n",
    "\n",
    "import numpy as np\n",
    "def max_bipartite_match(graph): \n",
    "    jobs_array = [-1] * len(graph) # final jobs array that the people's indices will be shown\n",
    "    for each_applicant in range(len(graph)): \n",
    "        seen_jobs = [False] * len(graph)\n",
    "        dfs(graph, each_applicant, jobs_array, seen_jobs) \n",
    "    return len([i for i in jobs_array if i != -1]), jobs_array\n",
    "\n",
    "\n",
    "def dfs(graph, u, jobs_array, seen_jobs): \n",
    "    for v in range(len(graph)): # for each job\n",
    "        if graph[u][v] > 0 and seen_jobs[v] == False: # if that job was not seen by applicant and possible to assign\n",
    "            seen_jobs[v] = True # mark the job as viewed\n",
    "            if jobs_array[v] == -1 or dfs(graph, jobs_array[v], jobs_array, seen_jobs):\n",
    "                jobs_array[v] = u # assign the job to new applicant even if index v was previously assigned to prev u\n",
    "                return True # after each assignment return True\n",
    "            \n",
    "            \n",
    "            \n",
    "test_matrix = np.array([[0, 0, 0, 1, 0, 1],\n",
    "                    [1, 0, 1, 0, 0, 0],\n",
    "                    [1, 0, 0, 0, 0, 0],\n",
    "                    [0, 1, 1, 0, 1, 0],\n",
    "                    [0, 1, 0, 1, 1, 0],\n",
    "                    [0, 0, 0, 0, 0, 1]])\n",
    "\n",
    "max_bipartite_match(test_matrix) # max number of matches, jobs list just to view who got which job\n",
    "# (6, [2, 4, 1, 0, 3, 5])"
   ]
  }
 ],
 "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
}