Skip to content

Commit 8261cba

Browse files
lcw921keon
lcw921
authored and
keon
committed
[ADD] Create maximum_flow_bfs.py (keon#603)
* [ADD] Create maximum_flow_bfs.py * Update README.md * Update README.md * [ADD] Create maximum_flow_dfs.py * Update README.md * Add unittest * Fix no newline end of file
1 parent cd4f9c7 commit 8261cba

File tree

5 files changed

+227
-1
lines changed

5 files changed

+227
-1
lines changed

‎README.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -162,6 +162,8 @@ If you want to uninstall algorithms, it is as simple as:
162162
- [satisfiability](algorithms/graph/satisfiability.py)
163163
- [tarjan](algorithms/graph/tarjan.py)
164164
- [traversal](algorithms/graph/traversal.py)
165+
- [maximum_flow_bfs](algorithms/graph/maximum_flow_bfs.py)
166+
- [maximum_flow_dfs](algorithms/graph/maximum_flow_dfs.py)
165167
- [all_pairs_shortest_path](algorithms/graph/all_pairs_shortest_path.py)
166168
- [bellman_ford](algorithms/graph/bellman_ford.py)
167169
- [heap](algorithms/heap)

‎algorithms/graph/__init__.py‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,6 @@
11
from .tarjan import *
22
from .check_bipartite import *
3+
from .maximum_flow_bfs import *
4+
from .maximum_flow_dfs import *
35
from .all_pairs_shortest_path import *
46
from .bellman_ford import *

‎algorithms/graph/maximum_flow_bfs.py‎

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
"""
2+
Given a n*n adjacency array.
3+
it will give you a maximum flow.
4+
This version use BFS to search path.
5+
6+
Assume the first is the source and the last is the sink.
7+
8+
Time complexity - O(Ef)
9+
10+
example
11+
12+
graph = [[0, 16, 13, 0, 0, 0],
13+
[0, 0, 10, 12, 0, 0],
14+
[0, 4, 0, 0, 14, 0],
15+
[0, 0, 9, 0, 0, 20],
16+
[0, 0, 0, 7, 0, 4],
17+
[0, 0, 0, 0, 0, 0]]
18+
19+
answer should be
20+
21+
23
22+
23+
"""
24+
import copy
25+
import queue
26+
import math
27+
28+
def maximum_flow_bfs(adjacency_matrix):
29+
#initial setting
30+
new_array = copy.deepcopy(adjacency_matrix)
31+
total = 0
32+
33+
while(1):
34+
#setting min to max_value
35+
min = math.inf
36+
#save visited nodes
37+
visited = [0]*len(new_array)
38+
#save parent nodes
39+
path = [0]*len(new_array)
40+
41+
#initialize queue for BFS
42+
bfs = queue.Queue()
43+
44+
#initial setting
45+
visited[0] = 1
46+
bfs.put(0)
47+
48+
#BFS to find path
49+
while(bfs.qsize() > 0):
50+
#pop from queue
51+
src = bfs.get()
52+
for k in range(len(new_array)):
53+
#checking capacity and visit
54+
if(new_array[src][k] > 0 and visited[k] == 0 ):
55+
#if not, put into queue and chage to visit and save path
56+
visited[k] = 1
57+
bfs.put(k)
58+
path[k] = src
59+
60+
#if there is no path from src to sink
61+
if(visited[len(new_array) - 1] == 0):
62+
break
63+
64+
#initial setting
65+
tmp = len(new_array) - 1
66+
67+
#Get minimum flow
68+
while(tmp != 0):
69+
#find minimum flow
70+
if(min > new_array[path[tmp]][tmp]):
71+
min = new_array[path[tmp]][tmp]
72+
tmp = path[tmp]
73+
74+
#initial setting
75+
tmp = len(new_array) - 1
76+
77+
#reduce capacity
78+
while(tmp != 0):
79+
new_array[path[tmp]][tmp] = new_array[path[tmp]][tmp] - min
80+
tmp = path[tmp]
81+
82+
total = total + min
83+
84+
return total

‎algorithms/graph/maximum_flow_dfs.py‎

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
"""
2+
Given a n*n adjacency array.
3+
it will give you a maximum flow.
4+
This version use DFS to search path.
5+
6+
Assume the first is the source and the last is the sink.
7+
8+
Time complexity - O(Ef)
9+
10+
example
11+
12+
graph = [[0, 16, 13, 0, 0, 0],
13+
[0, 0, 10, 12, 0, 0],
14+
[0, 4, 0, 0, 14, 0],
15+
[0, 0, 9, 0, 0, 20],
16+
[0, 0, 0, 7, 0, 4],
17+
[0, 0, 0, 0, 0, 0]]
18+
19+
answer should be
20+
21+
23
22+
23+
"""
24+
import copy
25+
import math
26+
27+
def maximum_flow_dfs(adjacency_matrix):
28+
#initial setting
29+
new_array = copy.deepcopy(adjacency_matrix)
30+
total = 0
31+
32+
while(1):
33+
#setting min to max_value
34+
min = math.inf
35+
#save visited nodes
36+
visited = [0]*len(new_array)
37+
#save parent nodes
38+
path = [0]*len(new_array)
39+
40+
#initialize stack for DFS
41+
stack = []
42+
43+
#initial setting
44+
visited[0] = 1
45+
stack.append(0)
46+
47+
#DFS to find path
48+
while(len(stack) > 0):
49+
#pop from queue
50+
src = stack.pop()
51+
for k in range(len(new_array)):
52+
#checking capacity and visit
53+
if(new_array[src][k] > 0 and visited[k] == 0 ):
54+
#if not, put into queue and chage to visit and save path
55+
visited[k] = 1
56+
stack.append(k)
57+
path[k] = src
58+
59+
#if there is no path from src to sink
60+
if(visited[len(new_array) - 1] == 0):
61+
break
62+
63+
#initial setting
64+
tmp = len(new_array) - 1
65+
66+
#Get minimum flow
67+
while(tmp != 0):
68+
#find minimum flow
69+
if(min > new_array[path[tmp]][tmp]):
70+
min = new_array[path[tmp]][tmp]
71+
tmp = path[tmp]
72+
73+
#initial setting
74+
tmp = len(new_array) - 1
75+
76+
#reduce capacity
77+
while(tmp != 0):
78+
new_array[path[tmp]][tmp] = new_array[path[tmp]][tmp] - min
79+
tmp = path[tmp]
80+
81+
total = total + min
82+
83+
return total
84+

‎tests/test_graph.py‎

Lines changed: 55 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,12 @@
11
from algorithms.graph import Tarjan
22
from algorithms.graph import check_bipartite
33
from algorithms.graph.dijkstra import Dijkstra
4+
from algorithms.graph import maximum_flow_bfs
5+
from algorithms.graph import maximum_flow_dfs
46
from algorithms.graph import all_pairs_shortest_path
57
from algorithms.graph import bellman_ford
68

9+
710
import unittest
811

912

@@ -78,6 +81,49 @@ def test_dijkstra(self):
7881

7982
self.assertEqual(g.dijkstra(0), [0, 4, 12, 19, 21, 11, 9, 8, 14])
8083

84+
class TestMaximum_Flow_Bfs(unittest.TestCase):
85+
86+
"""
87+
Test for the file def maximum_flow_bfs.py
88+
Arguments:
89+
unittest {[type]} -- [description]
90+
"""
91+
92+
def test_maximum_flow_bfs(self):
93+
graph = [
94+
[0, 16, 13, 0, 0, 0],
95+
[0, 0, 10, 12, 0, 0],
96+
[0, 4, 0, 0, 14, 0],
97+
[0, 0, 9, 0, 0, 20],
98+
[0, 0, 0, 7, 0, 4],
99+
[0, 0, 0, 0, 0, 0]
100+
]
101+
maximum_flow = maximum_flow_bfs(graph)
102+
103+
self.assertEqual(maximum_flow, 23)
104+
105+
class TestMaximum_Flow_Dfs(unittest.TestCase):
106+
107+
"""
108+
Test for the file def maximum_flow_dfs.py
109+
Arguments:
110+
unittest {[type]} -- [description]
111+
"""
112+
113+
def test_maximum_flow_dfs(self):
114+
graph = [
115+
[0, 16, 13, 0, 0, 0],
116+
[0, 0, 10, 12, 0, 0],
117+
[0, 4, 0, 0, 14, 0],
118+
[0, 0, 9, 0, 0, 20],
119+
[0, 0, 0, 7, 0, 4],
120+
[0, 0, 0, 0, 0, 0]
121+
]
122+
maximum_flow = maximum_flow_dfs(graph)
123+
124+
self.assertEqual(maximum_flow, 23)
125+
126+
81127
class TestAll_Pairs_Shortest_Path(unittest.TestCase):
82128

83129
def test_all_pairs_shortest_path(self):
@@ -88,7 +134,14 @@ def test_all_pairs_shortest_path(self):
88134
[0.867, 0.119, 0.352, 0.398, 0]]
89135
result = all_pairs_shortest_path(graph)
90136

91-
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]])
137+
self.assertEqual(result, [
138+
[0, 0.1, 0.101, 0.142, 0.277],
139+
[0.436, 0, 0.191, 0.192, 0.34299999999999997],
140+
[0.245, 0.345, 0, 0.333, 0.484],
141+
[0.706, 0.27, 0.46099999999999997, 0, 0.151],
142+
[0.5549999999999999, 0.119, 0.31, 0.311, 0],
143+
])
144+
92145

93146
class TestBellmanFord(unittest.TestCase):
94147
def test_bellman_ford(self):
@@ -111,3 +164,4 @@ def test_bellman_ford(self):
111164
}
112165

113166
self.assertEqual(True, bellman_ford(graph2, 'a'))
167+

0 commit comments

Comments
 (0)