Coverage for src/ensae_teaching_cs/td_2a/edmonds_karp.py: 84%
79 statements
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
« prev ^ index » next coverage.py v7.1.0, created at 2023-04-28 06:23 +0200
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
77 @param verbose more information
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]:
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
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