Repository: keon/algorithms
Pull request #612 (2019-12-09 06:50:09)

Add bfs count islands
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [X] **If creating a new file :**
  - [ ] added links to it in the README files ?
  - [X] included tests with it ?
  - [X] added description (overview of algorithm, time and space complexity, and possible edge case) in docstrings ?

- [X] **if done some changes :**
  - [X] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**

keon: looks good to me, but this code needs unittests

Patch:
diff --git a/README.md b/README.md
index f288ee3..bf686b8 100644
--- a/README.md
+++ b/README.md
@@ -71,6 +71,8 @@ If you want to uninstall algorithms, it is as simple as:
     - [two_sum](algorithms/arrays/two_sum.py)
     - [move_zeros](algorithms/arrays/move_zeros.py)
     - [n_sum](algorithms/arrays/n_sum.py)
+- [automata](algorithms/automata)
+    - [DFA](algorithms/automata/DFA.py)
 - [backtrack](algorithms/backtrack)
     - [general_solution.md](algorithms/backtrack/)
     - [add_operators](algorithms/backtrack/add_operators.py)
@@ -160,6 +162,11 @@ If you want to uninstall algorithms, it is as simple as:
     - [satisfiability](algorithms/graph/satisfiability.py)
     - [tarjan](algorithms/graph/tarjan.py)
     - [traversal](algorithms/graph/traversal.py)
+	  - [maximum_flow](algorithms/graph/maximum_flow.py)
+    - [maximum_flow_bfs](algorithms/graph/maximum_flow_bfs.py)
+    - [maximum_flow_dfs](algorithms/graph/maximum_flow_dfs.py)
+    - [all_pairs_shortest_path](algorithms/graph/all_pairs_shortest_path.py)
+    - [bellman_ford](algorithms/graph/bellman_ford.py)
 - [heap](algorithms/heap)
     - [merge_sorted_k_lists](algorithms/heap/merge_sorted_k_lists.py)
     - [skyline](algorithms/heap/skyline.py)
@@ -215,6 +222,9 @@ If you want to uninstall algorithms, it is as simple as:
     - [sqrt_precision_factor](algorithms/maths/sqrt_precision_factor.py)
     - [summing_digits](algorithms/maths/summing_digits.py)
     - [hailstone](algorithms/maths/hailstone.py)
+    - [recursive_binomial_coefficient](algorithms/maths/recursive_binomial_coefficient.py)
+    - [find_order](algorithms/maths/find_order_simple.py)
+	  - [find_primitive_root](algorithms/maths/find_primitive_root_simple.py)
 - [matrix](algorithms/matrix)
     - [sudoku_validator](algorithms/matrix/sudoku_validator.py)
     - [bomb_enemy](algorithms/matrix/bomb_enemy.py)
@@ -320,6 +330,7 @@ If you want to uninstall algorithms, it is as simple as:
     - [first_unique_char](algorithms/strings/first_unique_char.py)
     - [repeat_substring](algorithms/strings/repeat_substring.py)     
 	- [atbash_cipher](algorithms/strings/atbash_cipher.py)
+	- [knuth_morris_pratt](algorithms/strings/knuth_morris_pratt.py)
 - [tree](algorithms/tree)
     - [bst](algorithms/tree/bst)
         - [array_to_bst](algorithms/tree/bst/array_to_bst.py)
diff --git a/algorithms/automata/__init__.py b/algorithms/automata/__init__.py
new file mode 100644
index 0000000..bef182c
--- /dev/null
+++ b/algorithms/automata/__init__.py
@@ -0,0 +1,1 @@
+from .dfa import *
diff --git a/algorithms/automata/dfa.py b/algorithms/automata/dfa.py
new file mode 100644
index 0000000..36211c7
--- /dev/null
+++ b/algorithms/automata/dfa.py
@@ -0,0 +1,18 @@
+def DFA(transitions, start, final, string):
+
+    num = len(string)
+    num_final = len(final)
+    cur = start
+    
+    for i in range (num):
+        
+        if transitions[cur][string[i]] == None:
+            return False
+        else:
+            cur = transitions[cur][string[i]]
+
+    for i in range (num_final):
+        if cur == final[i]:
+            return True
+    return False
+        
diff --git a/algorithms/bfs/__init__.py b/algorithms/bfs/__init__.py
index b3d3b0c..e61e7db 100644
--- a/algorithms/bfs/__init__.py
+++ b/algorithms/bfs/__init__.py
@@ -1,3 +1,4 @@
+from .count_islands import *
 from .maze_search import *
 from .shortest_distance_from_all_buildings import *
 from .word_ladder import *
diff --git a/algorithms/bfs/count_islands.py b/algorithms/bfs/count_islands.py
new file mode 100644
index 0000000..5c9d006
--- /dev/null
+++ b/algorithms/bfs/count_islands.py
@@ -0,0 +1,65 @@
+"""
+This is a bfs-version of counting-islands problem in dfs section.
+Given a 2d grid map of '1's (land) and '0's (water),
+count the number of islands.
+An island is surrounded by water and is formed by
+connecting adjacent lands horizontally or vertically.
+You may assume all four edges of the grid are all surrounded by water.
+
+Example 1:
+11110
+11010
+11000
+00000
+Answer: 1
+
+Example 2:
+11000
+11000
+00100
+00011
+Answer: 3
+
+Example 3:
+111000
+110000
+100001
+001101
+001100
+Answer: 3
+
+Example 4:
+110011
+001100
+000001
+111100
+Answer: 5
+"""
+
+
+def count_islands(grid):
+    row = len(grid)
+    col = len(grid[0])
+
+    num_islands = 0
+    visited = [[0] * col for i in range(row)]
+    directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
+    queue = []
+
+    for i in range(row):
+        for j, num in enumerate(grid[i]):
+            if num == 1 and visited[i][j] != 1:
+                visited[i][j] = 1
+                queue.append((i, j))
+                while queue:
+                    x, y = queue.pop(0)
+                    for k in range(len(directions)):
+                        nx_x = x + directions[k][0]
+                        nx_y = y + directions[k][1]
+                        if nx_x >= 0 and nx_y >= 0 and nx_x < row and nx_y < col:
+                            if visited[nx_x][nx_y] != 1 and grid[nx_x][nx_y] == 1:
+                                queue.append((nx_x, nx_y))
+                                visited[nx_x][nx_y] = 1
+                num_islands += 1
+
+    return num_islands
diff --git a/algorithms/graph/__init__.py b/algorithms/graph/__init__.py
index f94f12c..6675e63 100644
--- a/algorithms/graph/__init__.py
+++ b/algorithms/graph/__init__.py
@@ -1,2 +1,7 @@
 from .tarjan import *
 from .check_bipartite import *
+from .maximum_flow import *
+from .maximum_flow_bfs import *
+from .maximum_flow_dfs import *
+from .all_pairs_shortest_path import *
+from .bellman_ford import *
diff --git a/algorithms/graph/bellman_ford.py b/algorithms/graph/bellman_ford.py
new file mode 100644
index 0000000..518f75c
--- /dev/null
+++ b/algorithms/graph/bellman_ford.py
@@ -0,0 +1,44 @@
+'''
+This Bellman-Ford Code is for determination whether we can get
+shortest path from given graph or not for single-source shortest-paths problem.
+In other words, if given graph has any negative-weight cycle that is reachable
+from the source, then it will give answer False for "no solution exits".
+For argument graph, it should be a dictionary type
+such as
+graph = {
+    'a': {'b': 6, 'e': 7},
+    'b': {'c': 5, 'd': -4, 'e': 8},
+    'c': {'b': -2},
+    'd': {'a': 2, 'c': 7},
+    'e': {'b': -3}
+}
+'''
+
+def bellman_ford(graph, source):
+    weight = {}
+    pre_node = {}
+
+    initialize_single_source(graph, source, weight, pre_node)
+
+    for i in range(1, len(graph)):
+        for node in graph:
+            for adjacent in graph[node]:
+                if weight[adjacent] > weight[node] + graph[node][adjacent]:
+                    weight[adjacent] = weight[node] + graph[node][adjacent]
+                    pre_node[adjacent] = node
+
+    for node in graph:
+        for adjacent in graph[node]:
+            if weight[adjacent] > weight[node] + graph[node][adjacent]:
+                return False
+
+    return True
+
+def initialize_single_source(graph, source, weight, pre_node):
+
+    for node in graph:
+        weight[node] = float('inf')
+        pre_node[node] = None
+
+    weight[source] = 0
+    
diff --git a/algorithms/graph/maximum_flow.py b/algorithms/graph/maximum_flow.py
new file mode 100644
index 0000000..ca78244
--- /dev/null
+++ b/algorithms/graph/maximum_flow.py
@@ -0,0 +1,134 @@
+"""
+Given the capacity, source and sink of a graph,
+computes the maximum flow from source to sink.
+Input : capacity, source, sink
+Output : maximum flow from source to sink
+Capacity is a two-dimensional array that is v*v.
+capacity[i][j] implies the capacity of the edge from i to j.
+If there is no edge from i to j, capacity[i][j] should be zero.
+"""
+
+import queue
+
+def dfs(capacity, flow, visit, vertices, idx, sink, current_flow = 1 << 63):
+    # DFS function for ford_fulkerson algorithm.
+    if idx == sink: 
+        return current_flow
+    visit[idx] = True
+    for nxt in range(vertices):
+        if not visit[nxt] and flow[idx][nxt] < capacity[idx][nxt]:
+            tmp = dfs(capacity, flow, visit, vertices, nxt, sink, min(current_flow, capacity[idx][nxt]-flow[idx][nxt]))
+            if tmp:
+                flow[idx][nxt] += tmp
+                flow[nxt][idx] -= tmp
+                return tmp
+    return 0
+
+def ford_fulkerson(capacity, source, sink):
+    # Computes maximum flow from source to sink using DFS.
+    # Time Complexity : O(Ef)
+    # E is the number of edges and f is the maximum flow in the graph.
+    vertices = len(capacity)
+    ret = 0
+    flow = [[0]*vertices for i in range(vertices)]
+    while True:
+        visit = [False for i in range(vertices)]
+        tmp = dfs(capacity, flow, visit, vertices, source, sink)
+        if tmp: 
+            ret += tmp
+        else: 
+            break
+    return ret
+
+def edmonds_karp(capacity, source, sink):
+    # Computes maximum flow from source to sink using BFS.
+    # Time complexity : O(V*E^2)
+    # V is the number of vertices and E is the number of edges.
+    vertices = len(capacity)
+    ret = 0
+    flow = [[0]*vertices for i in range(vertices)]
+    while True:
+        tmp = 0
+        q = queue.Queue()
+        visit = [False for i in range(vertices)]
+        par = [-1 for i in range(vertices)]
+        visit[source] = True
+        q.put((source, 1 << 63))
+        # Finds new flow using BFS.
+        while q.qsize():
+            front = q.get()
+            idx, current_flow = front
+            if idx == sink:
+                tmp = current_flow
+                break
+            for nxt in range(vertices):
+                if not visit[nxt] and flow[idx][nxt] < capacity[idx][nxt]:
+                    visit[nxt] = True
+                    par[nxt] = idx
+                    q.put((nxt, min(current_flow, capacity[idx][nxt]-flow[idx][nxt])))
+        if par[sink] == -1: 
+            break
+        ret += tmp
+        parent = par[sink]
+        idx = sink
+        # Update flow array following parent starting from sink.
+        while parent != -1:
+            flow[parent][idx] += tmp
+            flow[idx][parent] -= tmp
+            idx = parent
+            parent = par[parent]
+    return ret
+
+def dinic_bfs(capacity, flow, level, source, sink):
+    # BFS function for Dinic algorithm.
+    # Check whether sink is reachable only using edges that is not full.
+
+    vertices = len(capacity)
+    q = queue.Queue()
+    q.put(source)
+    level[source] = 0
+    while q.qsize():
+        front = q.get()
+        for nxt in range(vertices):
+            if level[nxt] == -1 and flow[front][nxt] < capacity[front][nxt]:
+                level[nxt] = level[front] + 1
+                q.put(nxt)
+    return level[sink] != -1
+
+def dinic_dfs(capacity, flow, level, idx, sink, work, current_flow = 1 << 63):
+    # DFS function for Dinic algorithm.
+    # Finds new flow using edges that is not full.
+    if idx == sink:
+        return current_flow
+    vertices = len(capacity)
+    while work[idx] < vertices:
+        nxt = work[idx]
+        if level[nxt] == level[idx] + 1 and flow[idx][nxt] < capacity[idx][nxt]:
+            tmp = dinic_dfs(capacity, flow, level, nxt, sink, work, min(current_flow, capacity[idx][nxt] - flow[idx][nxt])) 
+            if tmp > 0:
+                flow[idx][nxt] += tmp
+                flow[nxt][idx] -= tmp
+                return tmp
+        work[idx] += 1
+    return 0
+
+def dinic(capacity, source, sink):
+    # Computes maximum flow from source to sink using Dinic algorithm.
+    # Time complexity : O(V^2*E)
+    # V is the number of vertices and E is the number of edges.
+    vertices = len(capacity)
+    flow = [[0]*vertices for i in range(vertices)]
+    ret = 0
+    while True:
+        level = [-1 for i in range(vertices)]
+        work = [0 for i in range(vertices)]
+        if not dinic_bfs(capacity, flow, level, source, sink):
+            break
+        while True:
+            tmp = dinic_dfs(capacity, flow, level, source, sink, work)
+            if tmp > 0:
+                ret += tmp
+            else:
+                break
+    return ret
+
diff --git a/algorithms/graph/maximum_flow_bfs.py b/algorithms/graph/maximum_flow_bfs.py
new file mode 100644
index 0000000..4d2d032
--- /dev/null
+++ b/algorithms/graph/maximum_flow_bfs.py
@@ -0,0 +1,84 @@
+"""
+Given a n*n adjacency array.
+it will give you a maximum flow.
+This version use BFS to search path.
+
+Assume the first is the source and the last is the sink.
+
+Time complexity - O(Ef)
+
+example
+
+graph = [[0, 16, 13, 0, 0, 0], 
+        [0, 0, 10, 12, 0, 0], 
+        [0, 4, 0, 0, 14, 0], 
+        [0, 0, 9, 0, 0, 20], 
+        [0, 0, 0, 7, 0, 4], 
+        [0, 0, 0, 0, 0, 0]] 
+
+answer should be
+
+23
+
+"""
+import copy
+import queue
+import math
+
+def maximum_flow_bfs(adjacency_matrix):
+    #initial setting
+    new_array = copy.deepcopy(adjacency_matrix)
+    total = 0
+
+    while(1):
+        #setting min to max_value
+        min = math.inf
+        #save visited nodes
+        visited = [0]*len(new_array)
+        #save parent nodes
+        path = [0]*len(new_array)
+        
+        #initialize queue for BFS
+        bfs = queue.Queue()
+
+        #initial setting 
+        visited[0] = 1
+        bfs.put(0)
+
+        #BFS to find path
+        while(bfs.qsize() > 0):
+            #pop from queue
+            src = bfs.get()
+            for k in range(len(new_array)):
+                #checking capacity and visit
+                if(new_array[src][k] > 0 and visited[k] == 0 ):
+                    #if not, put into queue and chage to visit and save path
+                    visited[k] = 1
+                    bfs.put(k)
+                    path[k] = src
+            
+        #if there is no path from src to sink
+        if(visited[len(new_array) - 1] == 0):
+            break
+        
+        #initial setting
+        tmp = len(new_array) - 1
+
+        #Get minimum flow
+        while(tmp != 0):
+            #find minimum flow
+            if(min > new_array[path[tmp]][tmp]):
+                min = new_array[path[tmp]][tmp]
+            tmp = path[tmp]
+
+        #initial setting
+        tmp = len(new_array) - 1
+
+        #reduce capacity
+        while(tmp != 0):
+            new_array[path[tmp]][tmp] = new_array[path[tmp]][tmp] - min
+            tmp = path[tmp]
+
+        total = total + min
+    
+    return total
diff --git a/algorithms/graph/maximum_flow_dfs.py b/algorithms/graph/maximum_flow_dfs.py
new file mode 100644
index 0000000..2d89d6b
--- /dev/null
+++ b/algorithms/graph/maximum_flow_dfs.py
@@ -0,0 +1,84 @@
+"""
+Given a n*n adjacency array.
+it will give you a maximum flow.
+This version use DFS to search path.
+
+Assume the first is the source and the last is the sink.
+
+Time complexity - O(Ef)
+
+example
+
+graph = [[0, 16, 13, 0, 0, 0], 
+        [0, 0, 10, 12, 0, 0], 
+        [0, 4, 0, 0, 14, 0], 
+        [0, 0, 9, 0, 0, 20], 
+        [0, 0, 0, 7, 0, 4], 
+        [0, 0, 0, 0, 0, 0]] 
+
+answer should be
+
+23
+
+"""
+import copy
+import math
+
+def maximum_flow_dfs(adjacency_matrix):
+    #initial setting
+    new_array = copy.deepcopy(adjacency_matrix)
+    total = 0
+
+    while(1):
+        #setting min to max_value
+        min = math.inf
+        #save visited nodes
+        visited = [0]*len(new_array)
+        #save parent nodes
+        path = [0]*len(new_array)
+        
+        #initialize stack for DFS
+        stack = []
+
+        #initial setting 
+        visited[0] = 1
+        stack.append(0)
+
+        #DFS to find path
+        while(len(stack) > 0):
+            #pop from queue
+            src = stack.pop()
+            for k in range(len(new_array)):
+                #checking capacity and visit
+                if(new_array[src][k] > 0 and visited[k] == 0 ):
+                    #if not, put into queue and chage to visit and save path
+                    visited[k] = 1
+                    stack.append(k)
+                    path[k] = src
+            
+        #if there is no path from src to sink
+        if(visited[len(new_array) - 1] == 0):
+            break
+        
+        #initial setting
+        tmp = len(new_array) - 1
+
+        #Get minimum flow
+        while(tmp != 0):
+            #find minimum flow
+            if(min > new_array[path[tmp]][tmp]):
+                min = new_array[path[tmp]][tmp]
+            tmp = path[tmp]
+
+        #initial setting
+        tmp = len(new_array) - 1
+
+        #reduce capacity
+        while(tmp != 0):
+            new_array[path[tmp]][tmp] = new_array[path[tmp]][tmp] - min
+            tmp = path[tmp]
+
+        total = total + min
+    
+    return total
+    
\ No newline at end of file
diff --git a/algorithms/maths/__init__.py b/algorithms/maths/__init__.py
index 7028a0a..1cb5f7d 100644
--- a/algorithms/maths/__init__.py
+++ b/algorithms/maths/__init__.py
@@ -15,3 +15,5 @@ from .rabin_miller import *
 from .rsa import *
 from .combination import *
 from .cosine_similarity import *
+from .find_order_simple import *
+from .find_primitive_root_simple import *
diff --git a/algorithms/maths/find_order_simple.py b/algorithms/maths/find_order_simple.py
new file mode 100644
index 0000000..d4866ee
--- /dev/null
+++ b/algorithms/maths/find_order_simple.py
@@ -0,0 +1,27 @@
+import math
+
+"""
+For positive integer n and given integer a that satisfies gcd(a, n) = 1,
+the order of a modulo n is the smallest positive integer k that satisfies
+pow (a, k) % n = 1. In other words, (a^k) ≡ 1 (mod n).
+Order of certain number may or may not be exist. If so, return -1.
+"""
+def find_order(a, n):
+    if ((a == 1) & (n == 1)):
+        return 1
+        """ Exception Handeling :
+        1 is the order of of 1 """
+    else:
+        if (math.gcd(a, n) != 1):
+            print ("a and n should be relative prime!")
+            return -1
+        else:
+            for i in range(1, n):
+                if (pow(a, i) % n == 1):
+                    return i
+            return -1
+
+"""
+Time complexity only for calculating order = O(nlog(n))
+O(n) for iteration loop, O(log(n)) for built-in power function
+"""
diff --git a/algorithms/maths/find_primitive_root_simple.py b/algorithms/maths/find_primitive_root_simple.py
new file mode 100644
index 0000000..a5b74f6
--- /dev/null
+++ b/algorithms/maths/find_primitive_root_simple.py
@@ -0,0 +1,71 @@
+import math
+
+"""
+For positive integer n and given integer a that satisfies gcd(a, n) = 1,
+the order of a modulo n is the smallest positive integer k that satisfies
+pow (a, k) % n = 1. In other words, (a^k) ≡ 1 (mod n).
+Order of certain number may or may not be exist. If so, return -1.
+"""
+def find_order(a, n):
+    if ((a == 1) & (n == 1)):
+        return 1
+        """ Exception Handeling :
+        1 is the order of of 1 """
+    else:
+        if (math.gcd(a, n) != 1):
+            print ("a and n should be relative prime!")
+            return -1
+        else:
+            for i in range(1, n):
+                if (pow(a, i) % n == 1):
+                    return i
+            return -1
+
+"""
+Euler's totient function, also known as phi-function ϕ(n),
+counts the number of integers between 1 and n inclusive,
+which are coprime to n.
+(Two numbers are coprime if their greatest common divisor (GCD) equals 1).
+Code from /algorithms/maths/euler_totient.py, written by 'goswami-rahul'
+"""
+def euler_totient(n):
+    """Euler's totient function or Phi function.
+    Time Complexity: O(sqrt(n))."""
+    result = n;
+    for i in range(2, int(n ** 0.5) + 1):
+        if n % i == 0:
+            while n % i == 0:
+                n //= i
+            result -= result // i
+    if n > 1:
+        result -= result // n;
+    return result;
+
+"""
+For positive integer n and given integer a that satisfies gcd(a, n) = 1,
+a is the primitive root of n, if a's order k for n satisfies k = ϕ(n).
+Primitive roots of certain number may or may not be exist.
+If so, return empty list.
+"""
+
+def find_primitive_root(n):
+    if (n == 1):
+        return [0]
+        """ Exception Handeling :
+        0 is the only primitive root of 1 """
+    else:
+        phi = euler_totient(n)
+        p_root_list = []
+        """ It will return every primitive roots of n. """
+        for i in range (1, n):
+            if (math.gcd(i, n) != 1):
+                continue
+                """ To have order, a and n must be
+                relative prime with each other. """
+            else:
+                order = find_order(i, n)
+                if (order == phi):
+                    p_root_list.append(i)
+                else:
+                    continue
+        return p_root_list
diff --git a/algorithms/maths/recursive_binomial_coefficient.py b/algorithms/maths/recursive_binomial_coefficient.py
new file mode 100644
index 0000000..ae57bd6
--- /dev/null
+++ b/algorithms/maths/recursive_binomial_coefficient.py
@@ -0,0 +1,28 @@
+def recursive_binomial_coefficient(n,k):
+    """Calculates the binomial coefficient, C(n,k), with n>=k using recursion
+    Time complexity is O(k), so can calculate fairly quickly for large values of k.
+
+    >>> recursive_binomial_coefficient(5,0)
+    1
+
+    >>> recursive_binomial_coefficient(8,2)
+    28
+
+    >>> recursive_binomial_coefficient(500,300)
+    5054949849935535817667719165973249533761635252733275327088189563256013971725761702359997954491403585396607971745777019273390505201262259748208640
+
+    """
+
+    if k>n:
+        raise ValueError('Invalid Inputs, ensure that n >= k')
+        #function is only defined for n>=k
+    if k == 0 or n == k:
+        #C(n,0) = C(n,n) = 1, so this is our base case.
+        return 1
+    if k > n/2:
+        #C(n,k) = C(n,n-k), so if n/2 is sufficiently small, we can reduce the problem size.
+        return recursive_binomial_coefficient(n,n-k)
+    else:
+        #else, we know C(n,k) = (n/k)C(n-1,k-1), so we can use this to reduce our problem size.
+        return int((n/k)*recursive_binomial_coefficient(n-1,k-1))
+
diff --git a/algorithms/strings/__init__.py b/algorithms/strings/__init__.py
index 9110a0f..3e6bc19 100644
--- a/algorithms/strings/__init__.py
+++ b/algorithms/strings/__init__.py
@@ -35,3 +35,5 @@ from .rotate import *
 from .first_unique_char import *
 from .repeat_substring import *
 from .atbash_cipher import *
+from .knuth_morris_pratt import *
+
diff --git a/algorithms/strings/knuth_morris_pratt.py b/algorithms/strings/knuth_morris_pratt.py
new file mode 100644
index 0000000..0bdf4d5
--- /dev/null
+++ b/algorithms/strings/knuth_morris_pratt.py
@@ -0,0 +1,34 @@
+"""
+Given two strings text and pattern,
+return the list of  start indexes in text that matches with the pattern
+using knuth_morris_pratt algorithm.
+If idx is in the list, text[idx : idx + M] matches with pattern.
+Time complexity : O(N+M)
+N and M is the length of text and pattern, respectively.
+"""
+
+def knuth_morris_pratt(text, pattern):
+    n = len(text)
+    m = len(pattern)
+    pi = [0 for i in range(m)]
+    i = 0
+    j = 0
+    # making pi table
+    for i in range(1, m):
+        while j and pattern[i] != pattern[j]:
+            j = pi[j - 1]
+        if pattern[i] == pattern[j]:
+            j += 1
+            pi[i] = j
+    # finding pattern
+    j = 0
+    ret = []
+    for i in range(n):
+        while j and text[i] != pattern[j]:
+            j = pi[j - 1]
+        if text[i] == pattern[j]:
+            j += 1
+            if j == m:
+                ret.append(i - m + 1)
+                j = pi[j - 1]
+    return ret


Test patch:
diff --git a/algorithms/graph/all_pairs_shortest_path.py b/algorithms/graph/all_pairs_shortest_path.py
new file mode 100644
index 0000000..46f3b7c
--- /dev/null
+++ b/algorithms/graph/all_pairs_shortest_path.py
@@ -0,0 +1,28 @@
+"""
+Given a n*n adjacency array.
+it will give you all pairs shortest path length.
+use deepcopy to preserve the original information.
+
+Time complexity : O(E^3)
+
+example
+
+a = [[0, 0.1, 0.101, 0.142, 0.277], [0.465, 0, 0.191, 0.192, 0.587], [0.245, 0.554, 0, 0.333, 0.931], [1.032, 0.668, 0.656, 0, 0.151], [0.867, 0.119, 0.352, 0.398, 0]]
+
+result 
+
+[[0, 0.1, 0.101, 0.142, 0.277], [0.436, 0, 0.191, 0.192, 0.34299999999999997], [0.245, 0.345, 0, 0.333, 0.484], [0.706, 0.27, 0.46099999999999997, 0, 0.151], [0.5549999999999999, 0.119, 0.31, 0.311, 0]]
+
+"""
+import copy
+
+def all_pairs_shortest_path(adjacency_matrix):
+    new_array = copy.deepcopy(adjacency_matrix)
+
+    for k in range(len(new_array)):
+        for i in range(len(new_array)):
+            for j in range(len(new_array)):
+                if new_array[i][j] > new_array[i][k] + new_array[k][j]:
+                    new_array[i][j] = new_array[i][k] + new_array[k][j]           
+    
+    return new_array
\ No newline at end of file
diff --git a/tests/test_automata.py b/tests/test_automata.py
new file mode 100644
index 0000000..201c3d4
--- /dev/null
+++ b/tests/test_automata.py
@@ -0,0 +1,48 @@
+from algorithms.automata import DFA
+
+
+import unittest
+
+
+class TestDFA(unittest.TestCase):
+    def test_DFA(self):
+    
+        transitions = {
+            'a': {'1': 'a', '0': 'b'},
+            'b': {'1': 'b', '0': 'a'}
+        }
+
+        final=['a']
+        start = 'a'
+    
+        self.assertEqual(False, DFA(transitions, start, final, "000111100"))
+        self.assertEqual(True, DFA(transitions, start, final, "111000011"))
+        
+        transitions1 = {
+            '0': {'0': '1', '1': '0'},
+            '1': {'0': '2', '1': '0'},
+            '2': {'0': '2', '1': '3'},
+            '3': {'0': '3', '1': '3'}
+        }    
+        
+        final1 = ['0', '1', '2']
+        start1 = '0'
+        
+        self.assertEqual(False, DFA(transitions1, start1, final1, "0001111"))
+        self.assertEqual(True, DFA(transitions1, start1, final1, "01010101"))
+        
+        transitions2 = {
+            '0': {'a': '0', 'b': '1'},
+            '1': {'a': '0', 'b': '2'},
+            '2': {'a': '3', 'b': '2'},
+            '3': {'a': '3', 'b': '3'}
+        }
+        
+        final2=['3']
+        start2 = '0'
+
+        self.assertEqual(False, DFA(transitions2, start2, final2, "aaabbb"))
+        self.assertEqual(True, DFA(transitions2, start2, final2, "baabba"))
+        
+if __name__ == '__main__':
+    unittest.main()
diff --git a/tests/test_bfs.py b/tests/test_bfs.py
index 62c179b..98bcb7e 100644
--- a/tests/test_bfs.py
+++ b/tests/test_bfs.py
@@ -1,4 +1,5 @@
 from algorithms.bfs import (
+    count_islands,
     maze_search,
     shortest_distance_from_all_buildings,
     ladder_length
@@ -7,8 +8,21 @@ from algorithms.bfs import (
 import unittest
 
 
+class TestCountIslands(unittest.TestCase):
+
+    def test_count_islands(self):
+        grid_1 = [[1,1,1,1,0], [1,1,0,1,0], [1,1,0,0,0], [0,0,0,0,0]]
+        self.assertEqual(1, count_islands(grid_1))
+        grid_2 = [[1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1]]
+        self.assertEqual(3, count_islands(grid_2))
+        grid_3 = [[1,1,1,0,0,0], [1,1,0,0,0,0], [1,0,0,0,0,1], [0,0,1,1,0,1], [0,0,1,1,0,0]]
+        self.assertEqual(3, count_islands(grid_3))
+        grid_4 = [[1,1,0,0,1,1], [0,0,1,1,0,0], [0,0,0,0,0,1], [1,1,1,1,0,0]]
+        self.assertEqual(5, count_islands(grid_4))
+
+
 class TestMazeSearch(unittest.TestCase):
-    
+
     def test_maze_search(self):
         grid_1 = [[1,0,1,1,1,1],[1,0,1,0,1,0],[1,0,1,0,1,1],[1,1,1,0,1,1]]
         self.assertEqual(14, maze_search(grid_1))
diff --git a/tests/test_graph.py b/tests/test_graph.py
index 893ea77..73ef230 100644
--- a/tests/test_graph.py
+++ b/tests/test_graph.py
@@ -1,6 +1,14 @@
 from algorithms.graph import Tarjan
 from algorithms.graph import check_bipartite
 from algorithms.graph.dijkstra import Dijkstra
+from algorithms.graph import ford_fulkerson
+from algorithms.graph import edmonds_karp
+from algorithms.graph import dinic
+from algorithms.graph import maximum_flow_bfs
+from algorithms.graph import maximum_flow_dfs
+from algorithms.graph import all_pairs_shortest_path
+from algorithms.graph import bellman_ford
+
 
 import unittest
 
@@ -74,4 +82,129 @@ class TestDijkstra(unittest.TestCase):
            [0, 0, 2, 0, 0, 0, 6, 7, 0] 
           ]; 
 
-        self.assertEqual(g.dijkstra(0), [0, 4, 12, 19, 21, 11, 9, 8, 14]);
\ No newline at end of file
+        self.assertEqual(g.dijkstra(0), [0, 4, 12, 19, 21, 11, 9, 8, 14])
+
+class TestMaximumFlow(unittest.TestCase):
+    """
+    Test for the file maximum_flow.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    def test_ford_fulkerson(self):
+        capacity = [
+                [0, 10, 10, 0, 0, 0, 0],
+                [0, 0, 2, 0, 4, 8, 0],
+                [0, 0, 0, 0, 0, 9, 0],
+                [0, 0, 0, 0, 0, 0, 0],
+                [0, 0, 0, 0, 0, 0, 10],
+                [0, 0, 0, 0, 6, 0, 10],
+                [0, 0, 0, 0, 0, 0, 0]
+            ]
+        self.assertEqual(19, ford_fulkerson(capacity, 0, 6))
+    def test_edmonds_karp(self):
+        capacity = [
+                [0, 10, 10, 0, 0, 0, 0],
+                [0, 0, 2, 0, 4, 8, 0],
+                [0, 0, 0, 0, 0, 9, 0],
+                [0, 0, 0, 0, 0, 0, 0],
+                [0, 0, 0, 0, 0, 0, 10],
+                [0, 0, 0, 0, 6, 0, 10],
+                [0, 0, 0, 0, 0, 0, 0]
+            ]
+        self.assertEqual(19, edmonds_karp(capacity, 0, 6))
+    def dinic(self):
+        capacity = [
+                [0, 10, 10, 0, 0, 0, 0],
+                [0, 0, 2, 0, 4, 8, 0],
+                [0, 0, 0, 0, 0, 9, 0],
+                [0, 0, 0, 0, 0, 0, 0],
+                [0, 0, 0, 0, 0, 0, 10],
+                [0, 0, 0, 0, 6, 0, 10],
+                [0, 0, 0, 0, 0, 0, 0]
+            ]
+        self.assertEqual(19, dinic(capacity, 0, 6))
+
+class TestMaximum_Flow_Bfs(unittest.TestCase):
+
+    """
+    Test for the file def maximum_flow_bfs.py
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    
+    def test_maximum_flow_bfs(self):
+        graph = [
+            [0, 16, 13, 0, 0, 0],
+            [0, 0, 10, 12, 0, 0],
+            [0, 4, 0, 0, 14, 0], 
+            [0, 0, 9, 0, 0, 20], 
+            [0, 0, 0, 7, 0, 4],
+            [0, 0, 0, 0, 0, 0]
+        ]
+        maximum_flow = maximum_flow_bfs(graph)
+
+        self.assertEqual(maximum_flow, 23)
+
+class TestMaximum_Flow_Dfs(unittest.TestCase):
+
+    """
+    Test for the file def maximum_flow_dfs.py
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    
+    def test_maximum_flow_dfs(self):
+        graph = [
+            [0, 16, 13, 0, 0, 0],
+            [0, 0, 10, 12, 0, 0],
+            [0, 4, 0, 0, 14, 0], 
+            [0, 0, 9, 0, 0, 20], 
+            [0, 0, 0, 7, 0, 4],
+            [0, 0, 0, 0, 0, 0]
+        ]
+        maximum_flow = maximum_flow_dfs(graph)
+
+        self.assertEqual(maximum_flow, 23)
+
+
+class TestAll_Pairs_Shortest_Path(unittest.TestCase):
+    
+    def test_all_pairs_shortest_path(self):
+        graph = [[0, 0.1, 0.101, 0.142, 0.277], 
+                 [0.465, 0, 0.191, 0.192, 0.587], 
+                 [0.245, 0.554, 0, 0.333, 0.931], 
+                 [1.032, 0.668, 0.656, 0, 0.151], 
+                 [0.867, 0.119, 0.352, 0.398, 0]]
+        result = all_pairs_shortest_path(graph)
+
+        self.assertEqual(result, [
+          [0, 0.1, 0.101, 0.142, 0.277],
+          [0.436, 0, 0.191, 0.192, 0.34299999999999997],
+          [0.245, 0.345, 0, 0.333, 0.484],
+          [0.706, 0.27, 0.46099999999999997, 0, 0.151],
+          [0.5549999999999999, 0.119, 0.31, 0.311, 0],
+        ])
+
+        
+class TestBellmanFord(unittest.TestCase):
+    def test_bellman_ford(self):
+        graph1 = {
+            'a': {'b': 6, 'e': 7},
+            'b': {'c': 5, 'd': -4, 'e': 8},
+            'c': {'b': -2},
+            'd': {'a': 2, 'c': 7},
+            'e': {'b': -3}
+        }
+    
+        self.assertEqual(True, bellman_ford(graph1, 'a'))
+    
+        graph2 = {
+            'a': {'d': 3, 'e': 4},
+            'b': {'a': 7, 'e':2},
+            'c': {'a': 12, 'd':9, 'e':11},
+            'd': {'c': 5, 'e': 11},
+            'e': {'a': 7, 'b': 5, 'd': 1}
+        } 
+    
+        self.assertEqual(True, bellman_ford(graph2, 'a'))
diff --git a/tests/test_maths.py b/tests/test_maths.py
index 86b61e0..ce34c3d 100644
--- a/tests/test_maths.py
+++ b/tests/test_maths.py
@@ -17,6 +17,8 @@ from algorithms.maths import (
     combination, combination_memo,
     hailstone,
     cosine_similarity,
+    find_order,
+    find_primitive_root,
 )
 
 import unittest
@@ -324,6 +326,32 @@ class TestCosineSimilarity(unittest.TestCase):
         self.assertAlmostEqual(cosine_similarity(vec_a, vec_b), -1)
         self.assertAlmostEqual(cosine_similarity(vec_a, vec_c), 0.4714045208)
 
+class TestFindPrimitiveRoot(unittest.TestCase):
+    """[summary]
+    Test for the file find_primitive_root_simple.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    def test_find_primitive_root_simple(self):
+        self.assertListEqual([0], find_primitive_root(1))
+        self.assertListEqual([2, 3], find_primitive_root(5))
+        self.assertListEqual([], find_primitive_root(24))
+        self.assertListEqual([2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32, 35], find_primitive_root(37))
+        
+
+class TestFindOrder(unittest.TestCase):
+    """[summary]
+    Test for the file find_order_simple.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    def test_find_order_simple(self):
+        self.assertEqual(1, find_order(1, 1))
+        self.assertEqual(6, find_order(3, 7))
+        self.assertEqual(-1, find_order(128, 256))
+        self.assertEqual(352, find_order(3, 353))
 
 if __name__ == "__main__":
     unittest.main()
diff --git a/tests/test_strings.py b/tests/test_strings.py
index 02abc6f..b20de80 100644
--- a/tests/test_strings.py
+++ b/tests/test_strings.py
@@ -37,7 +37,8 @@ from algorithms.strings import (
     rotate,
     first_unique_char,
     repeat_substring,
-    atbash
+    atbash,
+    knuth_morris_pratt
 )
 
 import unittest
@@ -532,5 +533,17 @@ class TestAtbashCipher(unittest.TestCase):
         self.assertEqual("AttaCK at DawN", atbash("ZggzXP zg WzdM"))
         self.assertEqual("ZggzXP zg WzdM", atbash("AttaCK at DawN"))
         
+class TestKnuthMorrisPratt(unittest.TestCase):
+    """[summary]
+    Test for the file knuth_morris_pratt.py
+
+    Arguments:
+        unittest {[type]} -- [description]
+    """
+    def test_knuth_morris_pratt(self):
+        self.assertEqual([0, 1, 2, 3, 4], knuth_morris_pratt("aaaaaaa", "aaa"))
+        self.assertEqual([0, 4], knuth_morris_pratt("abcdabc", "abc"))
+        self.assertEqual([], knuth_morris_pratt("aabcdaab", "aba"))
+
 if __name__ == "__main__":
     unittest.main()