# Coverage for src/ensae_teaching_cs/td_2a/edmonds_karp.py: 84%

## 79 statements

, created at 2023-01-27 05:44 +0100

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

11class EdmondsKarpGraph:

12 """

13 This class represents a directed graph using adjacency

14 matrix representation.

15 """

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.

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

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.

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 = {}

45 # Create a queue for BFS

46 queue = collections.deque()

48 # Mark the source node as visited and enqueue it

49 queue.append(s)

50 visited[s] = True

52 # Standard BFS Loop

53 while queue:

54 u = queue.popleft()

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

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

66 # true, else false

67 return visited.get(t, False)

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.

74 @param source source of the flow

75 @param sink destination of the flow

76 @param fLOG logging function

78 @param update custom update function

79 @return maximum flow

81 The update function can take into account linked edges.

82 the default version is:

84 ::

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]:

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

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(f" {k} -> {kk} : {vv:03f}")

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

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

113 parent = {}

115 max_flow = 0 # There is no flow initially

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

118 graph[u][v] -= path_flow

119 graph[v][u] += path_flow

121 if update is None:

122 update = update_default

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(f"[edmonds_karp] max_flow={max_flow}")

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]

140 # Add path flow to overall flow

141 max_flow += path_flow

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]

151 if iteration == 0:

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

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 f" {k} -> {kk} : {vv:03f} -- ini {ini[k][kk]:03f}")

161 fLOG("---", max_flow)

162 if fLOG:

163 fLOG(f"[edmonds_karp] max_flow={max_flow}")

164 return max_flow