Coverage for /pythoncovmergedfiles/medio/medio/usr/local/lib/python3.9/dist-packages/networkx/algorithms/flow/boykovkolmogorov.py: 5%
156 statements
« prev ^ index » next coverage.py v7.3.2, created at 2023-10-20 07:00 +0000
1"""
2Boykov-Kolmogorov algorithm for maximum flow problems.
3"""
4from collections import deque
5from operator import itemgetter
7import networkx as nx
8from networkx.algorithms.flow.utils import build_residual_network
10__all__ = ["boykov_kolmogorov"]
13@nx._dispatch(
14 graphs={"G": 0, "residual?": 4},
15 edge_attrs={"capacity": float("inf")},
16 preserve_edge_attrs={"residual": {"capacity": float("inf")}},
17 preserve_graph_attrs={"residual"},
18)
19def boykov_kolmogorov(
20 G, s, t, capacity="capacity", residual=None, value_only=False, cutoff=None
21):
22 r"""Find a maximum single-commodity flow using Boykov-Kolmogorov algorithm.
24 This function returns the residual network resulting after computing
25 the maximum flow. See below for details about the conventions
26 NetworkX uses for defining residual networks.
28 This algorithm has worse case complexity $O(n^2 m |C|)$ for $n$ nodes, $m$
29 edges, and $|C|$ the cost of the minimum cut [1]_. This implementation
30 uses the marking heuristic defined in [2]_ which improves its running
31 time in many practical problems.
33 Parameters
34 ----------
35 G : NetworkX graph
36 Edges of the graph are expected to have an attribute called
37 'capacity'. If this attribute is not present, the edge is
38 considered to have infinite capacity.
40 s : node
41 Source node for the flow.
43 t : node
44 Sink node for the flow.
46 capacity : string
47 Edges of the graph G are expected to have an attribute capacity
48 that indicates how much flow the edge can support. If this
49 attribute is not present, the edge is considered to have
50 infinite capacity. Default value: 'capacity'.
52 residual : NetworkX graph
53 Residual network on which the algorithm is to be executed. If None, a
54 new residual network is created. Default value: None.
56 value_only : bool
57 If True compute only the value of the maximum flow. This parameter
58 will be ignored by this algorithm because it is not applicable.
60 cutoff : integer, float
61 If specified, the algorithm will terminate when the flow value reaches
62 or exceeds the cutoff. In this case, it may be unable to immediately
63 determine a minimum cut. Default value: None.
65 Returns
66 -------
67 R : NetworkX DiGraph
68 Residual network after computing the maximum flow.
70 Raises
71 ------
72 NetworkXError
73 The algorithm does not support MultiGraph and MultiDiGraph. If
74 the input graph is an instance of one of these two classes, a
75 NetworkXError is raised.
77 NetworkXUnbounded
78 If the graph has a path of infinite capacity, the value of a
79 feasible flow on the graph is unbounded above and the function
80 raises a NetworkXUnbounded.
82 See also
83 --------
84 :meth:`maximum_flow`
85 :meth:`minimum_cut`
86 :meth:`preflow_push`
87 :meth:`shortest_augmenting_path`
89 Notes
90 -----
91 The residual network :samp:`R` from an input graph :samp:`G` has the
92 same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair
93 of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a
94 self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists
95 in :samp:`G`.
97 For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`
98 is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists
99 in :samp:`G` or zero otherwise. If the capacity is infinite,
100 :samp:`R[u][v]['capacity']` will have a high arbitrary finite value
101 that does not affect the solution of the problem. This value is stored in
102 :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,
103 :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and
104 satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`.
106 The flow value, defined as the total flow into :samp:`t`, the sink, is
107 stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not
108 specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such
109 that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum
110 :samp:`s`-:samp:`t` cut.
112 Examples
113 --------
114 >>> from networkx.algorithms.flow import boykov_kolmogorov
116 The functions that implement flow algorithms and output a residual
117 network, such as this one, are not imported to the base NetworkX
118 namespace, so you have to explicitly import them from the flow package.
120 >>> G = nx.DiGraph()
121 >>> G.add_edge("x", "a", capacity=3.0)
122 >>> G.add_edge("x", "b", capacity=1.0)
123 >>> G.add_edge("a", "c", capacity=3.0)
124 >>> G.add_edge("b", "c", capacity=5.0)
125 >>> G.add_edge("b", "d", capacity=4.0)
126 >>> G.add_edge("d", "e", capacity=2.0)
127 >>> G.add_edge("c", "y", capacity=2.0)
128 >>> G.add_edge("e", "y", capacity=3.0)
129 >>> R = boykov_kolmogorov(G, "x", "y")
130 >>> flow_value = nx.maximum_flow_value(G, "x", "y")
131 >>> flow_value
132 3.0
133 >>> flow_value == R.graph["flow_value"]
134 True
136 A nice feature of the Boykov-Kolmogorov algorithm is that a partition
137 of the nodes that defines a minimum cut can be easily computed based
138 on the search trees used during the algorithm. These trees are stored
139 in the graph attribute `trees` of the residual network.
141 >>> source_tree, target_tree = R.graph["trees"]
142 >>> partition = (set(source_tree), set(G) - set(source_tree))
144 Or equivalently:
146 >>> partition = (set(G) - set(target_tree), set(target_tree))
148 References
149 ----------
150 .. [1] Boykov, Y., & Kolmogorov, V. (2004). An experimental comparison
151 of min-cut/max-flow algorithms for energy minimization in vision.
152 Pattern Analysis and Machine Intelligence, IEEE Transactions on,
153 26(9), 1124-1137.
154 https://doi.org/10.1109/TPAMI.2004.60
156 .. [2] Vladimir Kolmogorov. Graph-based Algorithms for Multi-camera
157 Reconstruction Problem. PhD thesis, Cornell University, CS Department,
158 2003. pp. 109-114.
159 https://web.archive.org/web/20170809091249/https://pub.ist.ac.at/~vnk/papers/thesis.pdf
161 """
162 R = boykov_kolmogorov_impl(G, s, t, capacity, residual, cutoff)
163 R.graph["algorithm"] = "boykov_kolmogorov"
164 return R
167def boykov_kolmogorov_impl(G, s, t, capacity, residual, cutoff):
168 if s not in G:
169 raise nx.NetworkXError(f"node {str(s)} not in graph")
170 if t not in G:
171 raise nx.NetworkXError(f"node {str(t)} not in graph")
172 if s == t:
173 raise nx.NetworkXError("source and sink are the same node")
175 if residual is None:
176 R = build_residual_network(G, capacity)
177 else:
178 R = residual
180 # Initialize/reset the residual network.
181 # This is way too slow
182 # nx.set_edge_attributes(R, 0, 'flow')
183 for u in R:
184 for e in R[u].values():
185 e["flow"] = 0
187 # Use an arbitrary high value as infinite. It is computed
188 # when building the residual network.
189 INF = R.graph["inf"]
191 if cutoff is None:
192 cutoff = INF
194 R_succ = R.succ
195 R_pred = R.pred
197 def grow():
198 """Bidirectional breadth-first search for the growth stage.
200 Returns a connecting edge, that is and edge that connects
201 a node from the source search tree with a node from the
202 target search tree.
203 The first node in the connecting edge is always from the
204 source tree and the last node from the target tree.
205 """
206 while active:
207 u = active[0]
208 if u in source_tree:
209 this_tree = source_tree
210 other_tree = target_tree
211 neighbors = R_succ
212 else:
213 this_tree = target_tree
214 other_tree = source_tree
215 neighbors = R_pred
216 for v, attr in neighbors[u].items():
217 if attr["capacity"] - attr["flow"] > 0:
218 if v not in this_tree:
219 if v in other_tree:
220 return (u, v) if this_tree is source_tree else (v, u)
221 this_tree[v] = u
222 dist[v] = dist[u] + 1
223 timestamp[v] = timestamp[u]
224 active.append(v)
225 elif v in this_tree and _is_closer(u, v):
226 this_tree[v] = u
227 dist[v] = dist[u] + 1
228 timestamp[v] = timestamp[u]
229 _ = active.popleft()
230 return None, None
232 def augment(u, v):
233 """Augmentation stage.
235 Reconstruct path and determine its residual capacity.
236 We start from a connecting edge, which links a node
237 from the source tree to a node from the target tree.
238 The connecting edge is the output of the grow function
239 and the input of this function.
240 """
241 attr = R_succ[u][v]
242 flow = min(INF, attr["capacity"] - attr["flow"])
243 path = [u]
244 # Trace a path from u to s in source_tree.
245 w = u
246 while w != s:
247 n = w
248 w = source_tree[n]
249 attr = R_pred[n][w]
250 flow = min(flow, attr["capacity"] - attr["flow"])
251 path.append(w)
252 path.reverse()
253 # Trace a path from v to t in target_tree.
254 path.append(v)
255 w = v
256 while w != t:
257 n = w
258 w = target_tree[n]
259 attr = R_succ[n][w]
260 flow = min(flow, attr["capacity"] - attr["flow"])
261 path.append(w)
262 # Augment flow along the path and check for saturated edges.
263 it = iter(path)
264 u = next(it)
265 these_orphans = []
266 for v in it:
267 R_succ[u][v]["flow"] += flow
268 R_succ[v][u]["flow"] -= flow
269 if R_succ[u][v]["flow"] == R_succ[u][v]["capacity"]:
270 if v in source_tree:
271 source_tree[v] = None
272 these_orphans.append(v)
273 if u in target_tree:
274 target_tree[u] = None
275 these_orphans.append(u)
276 u = v
277 orphans.extend(sorted(these_orphans, key=dist.get))
278 return flow
280 def adopt():
281 """Adoption stage.
283 Reconstruct search trees by adopting or discarding orphans.
284 During augmentation stage some edges got saturated and thus
285 the source and target search trees broke down to forests, with
286 orphans as roots of some of its trees. We have to reconstruct
287 the search trees rooted to source and target before we can grow
288 them again.
289 """
290 while orphans:
291 u = orphans.popleft()
292 if u in source_tree:
293 tree = source_tree
294 neighbors = R_pred
295 else:
296 tree = target_tree
297 neighbors = R_succ
298 nbrs = ((n, attr, dist[n]) for n, attr in neighbors[u].items() if n in tree)
299 for v, attr, d in sorted(nbrs, key=itemgetter(2)):
300 if attr["capacity"] - attr["flow"] > 0:
301 if _has_valid_root(v, tree):
302 tree[u] = v
303 dist[u] = dist[v] + 1
304 timestamp[u] = time
305 break
306 else:
307 nbrs = (
308 (n, attr, dist[n]) for n, attr in neighbors[u].items() if n in tree
309 )
310 for v, attr, d in sorted(nbrs, key=itemgetter(2)):
311 if attr["capacity"] - attr["flow"] > 0:
312 if v not in active:
313 active.append(v)
314 if tree[v] == u:
315 tree[v] = None
316 orphans.appendleft(v)
317 if u in active:
318 active.remove(u)
319 del tree[u]
321 def _has_valid_root(n, tree):
322 path = []
323 v = n
324 while v is not None:
325 path.append(v)
326 if v in (s, t):
327 base_dist = 0
328 break
329 elif timestamp[v] == time:
330 base_dist = dist[v]
331 break
332 v = tree[v]
333 else:
334 return False
335 length = len(path)
336 for i, u in enumerate(path, 1):
337 dist[u] = base_dist + length - i
338 timestamp[u] = time
339 return True
341 def _is_closer(u, v):
342 return timestamp[v] <= timestamp[u] and dist[v] > dist[u] + 1
344 source_tree = {s: None}
345 target_tree = {t: None}
346 active = deque([s, t])
347 orphans = deque()
348 flow_value = 0
349 # data structures for the marking heuristic
350 time = 1
351 timestamp = {s: time, t: time}
352 dist = {s: 0, t: 0}
353 while flow_value < cutoff:
354 # Growth stage
355 u, v = grow()
356 if u is None:
357 break
358 time += 1
359 # Augmentation stage
360 flow_value += augment(u, v)
361 # Adoption stage
362 adopt()
364 if flow_value * 2 > INF:
365 raise nx.NetworkXUnbounded("Infinite capacity path, flow unbounded above.")
367 # Add source and target tree in a graph attribute.
368 # A partition that defines a minimum cut can be directly
369 # computed from the search trees as explained in the docstrings.
370 R.graph["trees"] = (source_tree, target_tree)
371 # Add the standard flow_value graph attribute.
372 R.graph["flow_value"] = flow_value
373 return R