Repository: keon/algorithms
Pull request #603 (2019-12-03 13:22:38)

[ADD] Create maximum_flow_bfs.py
(Put an `X` inside the `[ ]` to denote check mark `[X]`.)


- [X] **If creating a new file :**
  - [x] 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 ?

- [ ] **if done some changes :**
  - [ ] wrote short description in the PR explaining what the changes do ?
  - [ ] Fixes #[issue number] if related to any issue

- [ ] **other**


lcw921: implemented the Ford Fulkerson Algorithm algorithm using both bfs and dfs. These are basically the same, but the only difference is whether they use queues or stacks as data structures to find the path.
lcw921: I implemented the Ford Fulkerson Algorithm algorithm using both bfs and dfs. These are basically the same, but the only difference is whether they use queues or stacks as data structures to find the path.
keon: please add unittests
lcw921: Added unit tests. Request you to check.
lcw921: Plz check it again. I resolve them.

2019년 12월 9일 (월) 오후 5:52, Keon <notifications@github.com>님이 작성:

> *@keon* commented on this pull request.
> ------------------------------
>
> In tests/test_graph.py
> <https://github.com/keon/algorithms/pull/603#discussion_r355323135>:
>
> > +    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]]
>
> 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]
> ]
>
>
> please make it easier to read.
> unittests are read by people, and when it breaks, it should be easy to recognize what broke
>
> —
> You are receiving this because you modified the open/close state.
> Reply to this email directly, view it on GitHub
> <https://github.com/keon/algorithms/pull/603?email_source=notifications&email_token=AJKV3FO27QDP4SZELWU5AODQXYBMVA5CNFSM4JUX56YKYY3PNVWWK3TUL52HS4DFWFIHK3DMKJSXC5LFON2FEZLWNFSXPKTDN5WW2ZLOORPWSZGOCOMIAYQ#pullrequestreview-328761442>,
> or unsubscribe
> <https://github.com/notifications/unsubscribe-auth/AJKV3FJBPHM5XFP4TVN375LQXYBMVANCNFSM4JUX56YA>
> .
>

lcw921: i resolve them. plz check it again.

Patch:
diff --git a/README.md b/README.md
index d188e04..8569d3b 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,8 @@ 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_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)
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/automata/__init__.py b/algorithms/automata/__init__.py
new file mode 100644
index 0000000..1613fa6
--- /dev/null
+++ b/algorithms/automata/__init__.py
@@ -0,0 +1,1 @@
+from .DFA import *
diff --git a/algorithms/graph/__init__.py b/algorithms/graph/__init__.py
index a155c77..43cab3d 100644
--- a/algorithms/graph/__init__.py
+++ b/algorithms/graph/__init__.py
@@ -1,4 +1,6 @@
 from .tarjan import *
 from .check_bipartite 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/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


Test patch:
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_graph.py b/tests/test_graph.py
index 48c2bbb..47d5afa 100644
--- a/tests/test_graph.py
+++ b/tests/test_graph.py
@@ -1,9 +1,12 @@
 from algorithms.graph import Tarjan
 from algorithms.graph import check_bipartite
 from algorithms.graph.dijkstra import Dijkstra
+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
 
 
@@ -78,6 +81,49 @@ class TestDijkstra(unittest.TestCase):
 
         self.assertEqual(g.dijkstra(0), [0, 4, 12, 19, 21, 11, 9, 8, 14])
 
+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):
@@ -88,7 +134,14 @@ class TestAll_Pairs_Shortest_Path(unittest.TestCase):
                  [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]])
+        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):
@@ -111,3 +164,4 @@ class TestBellmanFord(unittest.TestCase):
         } 
     
         self.assertEqual(True, bellman_ford(graph2, 'a'))
+