-
Notifications
You must be signed in to change notification settings - Fork 1
/
PythonMatching.py
192 lines (175 loc) · 5 KB
/
PythonMatching.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
"""
created by: masphei @2013
contact: [email protected]
description: PythonFlow class is an implementation of Ford-Fulkerson algorithm which is found in Introduction to Algorithm 3rd Edition. There are several ways of modification to build the program as my thought.
"""
import timeit
class PythonFlow:
# PythonFlow implement Ford-Fulkerson method to maximize flow on graph problems.
# example of input text:
#
# 0 16 13 0 0 0
# 0 0 0 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
#
# (do not forget to put last enter)
def __init__(self):
# graph G network
self.graph = []
# flow f network
self.flow = []
# residual f' network
self.residual = []
# total flow which can be retrieved
self.total_flow = 0
#file name
self.file_name = "D:/Copy/Coding/GitHub/PythonFlow/bipartite.txt"
self.load_file()
# self.print_graph(self.graph)
row = [0] # source
for x in range(len(self.graph)):
self.graph[x].insert(0, 0)
if x < len(self.graph)/2:
self.graph[x].append(0)
row.append(1)
else:
self.graph[x].append(1)
row.append(0)
row.append(0) # sink
self.graph.insert(0, row)
self.graph.append([0 for x in range(len(self.graph)+1)])
# self.print_graph(self.graph)
self.init_flow()
self.update_residual()
#input graph from specified file
def load_file(self):
counter_row = 0
counter_col = 0
row = []
number = ""
#iterate whole lines
for line in open(self.file_name):
#iterate each character
for char in line:
if char == "\n":
counter_col += 1
row.append(int(number.strip()))
self.graph.append(row)
row = []
number = ""
elif char == " ":
row.append(int(number.strip()))
number = ""
elif char != " ":
number += char
#initializing flow network
def init_flow(self):
number = []
for element in self.graph:
for value in element:
number.append(0)
self.flow.append(number)
number = []
#update residual network value based on current flow
def update_residual(self):
number = []
self.residual = []
for x in range(len(self.graph)):
for y in range(len(self.graph[x])):
number.append(self.graph[x][y] - self.flow[x][y])
self.residual.append(number)
number = []
def main_algorithm(self):
best_path = self.find_best_path()
# iterate until no augmenting paths exist, it gives sign for maximum flow f
while len(best_path)!= 0:
self.apply_path(best_path)
self.update_residual()
best_path = self.find_best_path()
def apply_path(self, path):
cost = self.get_minimum_cost_flow(path)
# print "applying cost:",cost
self.total_flow += cost
source = 0
for x in path:
self.flow[source][x] += cost
source = x
self.update_residual()
def find_best_path(self):
# best path is obtained by doing bfs to reveal all available paths and greedy to choose the best path
# assume that there is no antiparallel edges
# this method chooses the best path from options
self.options = []
self.get_path(0, [])
if len(self.options) >0:
self.cost = []
min_index = -1
max_flow = 0
# do such a greedy to get the maximum impact
for x in range(len(self.options)):
min = self.get_minimum_cost_flow(self.options[x])
if max_flow < min:
max_flow = min
min_index = x
# print "Best augmenting path: ",self.options[min_index], "with cost: ", max_flow
return self.options[min_index]
else:
return []
# find the minimum cost flow from augmenting paths
def get_minimum_cost_flow(self, path):
source = 0
min = 9999
for x in path:
if min > self.residual[source][x]:
min = self.residual[source][x]
source = x
return min
# get list of available paths from particular vertex
def get_path(self, vertex, paths):
options = self.get_options(vertex)
sink_index = len(self.graph[0]) - 1
if vertex == sink_index and len(options) == 0:
self.options.append(paths)
else:
# testing: counter = 0
# testing: while len(self.options) == 0 and counter < len(options):
# testing: x = options[counter]
for x in options:
if x not in paths:
# generate new path
new_path = []
for y in paths:
new_path.append(y)
new_path.append(x)
# iteratively find paths
self.get_path(x, new_path)
# testing: counter += 1
# permute available vertices to generate path
def get_options(self, initial_vertex):
retval = []
index = 0
for x in self.graph[initial_vertex]:
if index != initial_vertex and self.residual[initial_vertex][index]!=0:
retval.append(index)
index += 1
return retval
# print graph
def print_graph(self, graph):
for x in range(len(graph)):
print graph[x]
# example of usage
flow = PythonFlow()
print "This is Graph G:"
flow.print_graph(flow.graph)
start = timeit.default_timer()
flow.main_algorithm()
stop = timeit.default_timer()
print "This is Flow f:"
flow.print_graph(flow.flow)
print "This is Residual f':"
flow.print_graph(flow.residual)
print "Total flow: ", flow.total_flow
print "time elapsed: ", (stop - start), " seconds"