1""" 

2@file 

3@brief Implements the `Edmonds-Karp algorithm <https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm>`_ 

4inspired from Wikipedia (same page). 

5""" 

6import copy 

7import collections 

8from pyquickhelper.loghelper import noLOG 

9 

10 

11class EdmondsKarpGraph: 

12 """ 

13 This class represents a directed graph using adjacency 

14 matrix representation. 

15 """ 

16 

17 def __init__(self, edges): 

18 """ 

19 The graph is defined as a list of tuple (n1, n2, capacity). 

20 is the capacity of the graph. 

21 

22 @param edges list of tuple (n1, n2, capacity) 

23 """ 

24 graph = {} 

25 for n1, n2, capacity in edges: 

26 if n1 not in graph: 

27 graph[n1] = {} 

28 graph[n1][n2] = capacity 

29 self._graph = graph # residual graph 

30 

31 def bfs(self, graph, s, t, parent): 

32 ''' 

33 Returns True if there is a path from source *s* to sink *t* in 

34 residual graph. Also fills *parent* to store the path. 

35 

36 @param graph graph 

37 @param s node 1 

38 @param t node 2 

39 @param parent stores the path 

40 @return boolean 

41 ''' 

42 # Mark all the vertices as not visited 

43 visited = {} 

44 

45 # Create a queue for BFS 

46 queue = collections.deque() 

47 

48 # Mark the source node as visited and enqueue it 

49 queue.append(s) 

50 visited[s] = True 

51 

52 # Standard BFS Loop 

53 while queue: 

54 u = queue.popleft() 

55 

56 # Get all adjacent vertices's of the dequeued vertex u 

57 # If a adjacent has not been visited, then mark it 

58 # visited and enqueue it 

59 for node, val in graph[u].items(): 

60 if (not visited.get(node, False)) and val > 0: 

61 queue.append(node) 

62 visited[node] = True 

63 parent[node] = u 

64 

65 # If we reached sink in BFS starting from source, then return 

66 # true, else false 

67 return visited.get(t, False) 

68 

69 def edmonds_karp(self, source, sink, fLOG=noLOG, verbose=False, 

70 update=None): 

71 """ 

72 Returns the maximum flow from *s* to *t* in the given graph. 

73 

74 @param source source of the flow 

75 @param sink destination of the flow 

76 @param fLOG logging function 

77 @param verbose more information 

78 @param update custom update function 

79 @return maximum flow 

80 

81 The update function can take into account linked edges. 

82 the default version is: 

83 

84 :: 

85 

86 def update_default(graph, u, v, path_flow): 

87 graph[u][v] -= path_flow 

88 graph[v][u] += path_flow 

89 """ 

90 graph = copy.deepcopy(self._graph) 

91 # Add symmetry. 

92 add_edges = [] 

93 for n1, forward in graph.items(): 

94 for n2 in forward: 

95 if n2 not in graph or n1 not in graph[n2]: 

96 add_edges.append((n2, n1)) 

97 for n1, n2 in add_edges: 

98 if n1 not in graph: 

99 graph[n1] = {} 

100 if n2 not in graph[n1]: 

101 graph[n1][n2] = 0 

102 

103 if verbose: 

104 ini = copy.deepcopy(graph) 

105 fLOG("---------") 

106 for k, v in sorted(graph.items()): 

107 for kk, vv in sorted(v.items()): 

108 if ini[k][kk] > 0: 

109 fLOG(" {0} -> {1} : {2:03f}".format(k, kk, vv)) 

110 fLOG("---------") 

111 

112 # This array is filled by BFS and to store path 

113 parent = {} 

114 

115 max_flow = 0 # There is no flow initially 

116 

117 def update_default(graph, u, v, path_flow): 

118 graph[u][v] -= path_flow 

119 graph[v][u] += path_flow 

120 

121 if update is None: 

122 update = update_default 

123 

124 # Augment the flow while there is path from source to sink 

125 iteration = 0 

126 while self.bfs(graph, source, sink, parent): 

127 iteration += 1 

128 if fLOG: 

129 fLOG("[edmonds_karp] max_flow={0}".format(max_flow)) 

130 

131 # Find minimum residual capacity of the edges along the 

132 # path filled by BFS. Or we can say find the maximum flow 

133 # through the path found. 

134 path_flow = float("Inf") 

135 s = sink 

136 while s != source: 

137 path_flow = min(path_flow, graph[parent[s]][s]) 

138 s = parent[s] 

139 

140 # Add path flow to overall flow 

141 max_flow += path_flow 

142 

143 # update residual capacities of the edges and reverse edges 

144 # along the path 

145 v = sink 

146 while v != source: 

147 u = parent[v] 

148 update(graph, u, v, path_flow) 

149 v = parent[v] 

150 

151 if iteration == 0: 

152 raise ValueError("No path can increase max_flow.") 

153 

154 if verbose: 

155 fLOG("---------") 

156 for k, v in sorted(graph.items()): 

157 for kk, vv in sorted(v.items()): 

158 if ini[k][kk] != vv and ini[k][kk] > 0: 

159 fLOG( 

160 " {0} -> {1} : {2:03f} -- ini {3:03f}".format(k, kk, vv, ini[k][kk])) 

161 fLOG("---", max_flow) 

162 if fLOG: 

163 fLOG("[edmonds_karp] max_flow={0}".format(max_flow)) 

164 return max_flow