Statistics
| Branch: | Revision:

## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / flow / dinitz_alg.py @ 5cef0f13

 1 ```# dinitz.py - Dinitz' algorithm for maximum flow problems. ``` ```# ``` ```# Copyright 2016-2019 NetworkX developers. ``` ```# ``` ```# This file is part of NetworkX. ``` ```# ``` ```# NetworkX is distributed under a BSD license; see LICENSE.txt for more ``` ```# information. ``` ```# ``` ```# Author: Jordi Torrents ``` ```""" ``` ```Dinitz' algorithm for maximum flow problems. ``` ```""" ``` ```from collections import deque ``` ```import networkx as nx ``` ```from networkx.algorithms.flow.utils import build_residual_network ``` ```from networkx.utils import pairwise ``` ```__all__ = ['dinitz'] ``` ```def dinitz(G, s, t, capacity='capacity', residual=None, value_only=False, cutoff=None): ``` ``` """Find a maximum single-commodity flow using Dinitz' algorithm. ``` ``` ``` ``` This function returns the residual network resulting after computing ``` ``` the maximum flow. See below for details about the conventions ``` ``` NetworkX uses for defining residual networks. ``` ``` ``` ``` This algorithm has a running time of \$O(n^2 m)\$ for \$n\$ nodes and \$m\$ ``` ``` edges _. ``` ``` ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` Edges of the graph are expected to have an attribute called ``` ``` 'capacity'. If this attribute is not present, the edge is ``` ``` considered to have infinite capacity. ``` ``` ``` ``` s : node ``` ``` Source node for the flow. ``` ``` ``` ``` t : node ``` ``` Sink node for the flow. ``` ``` ``` ``` capacity : string ``` ``` Edges of the graph G are expected to have an attribute capacity ``` ``` that indicates how much flow the edge can support. If this ``` ``` attribute is not present, the edge is considered to have ``` ``` infinite capacity. Default value: 'capacity'. ``` ``` ``` ``` residual : NetworkX graph ``` ``` Residual network on which the algorithm is to be executed. If None, a ``` ``` new residual network is created. Default value: None. ``` ``` ``` ``` value_only : bool ``` ``` If True compute only the value of the maximum flow. This parameter ``` ``` will be ignored by this algorithm because it is not applicable. ``` ``` ``` ``` cutoff : integer, float ``` ``` If specified, the algorithm will terminate when the flow value reaches ``` ``` or exceeds the cutoff. In this case, it may be unable to immediately ``` ``` determine a minimum cut. Default value: None. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` R : NetworkX DiGraph ``` ``` Residual network after computing the maximum flow. ``` ``` ``` ``` Raises ``` ``` ------ ``` ``` NetworkXError ``` ``` The algorithm does not support MultiGraph and MultiDiGraph. If ``` ``` the input graph is an instance of one of these two classes, a ``` ``` NetworkXError is raised. ``` ``` ``` ``` NetworkXUnbounded ``` ``` If the graph has a path of infinite capacity, the value of a ``` ``` feasible flow on the graph is unbounded above and the function ``` ``` raises a NetworkXUnbounded. ``` ``` ``` ``` See also ``` ``` -------- ``` ``` :meth:`maximum_flow` ``` ``` :meth:`minimum_cut` ``` ``` :meth:`preflow_push` ``` ``` :meth:`shortest_augmenting_path` ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` The residual network :samp:`R` from an input graph :samp:`G` has the ``` ``` same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair ``` ``` of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a ``` ``` self-loop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists ``` ``` in :samp:`G`. ``` ``` ``` ``` For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']` ``` ``` is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists ``` ``` in :samp:`G` or zero otherwise. If the capacity is infinite, ``` ``` :samp:`R[u][v]['capacity']` will have a high arbitrary finite value ``` ``` that does not affect the solution of the problem. This value is stored in ``` ``` :samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`, ``` ``` :samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and ``` ``` satisfies :samp:`R[u][v]['flow'] == -R[v][u]['flow']`. ``` ``` ``` ``` The flow value, defined as the total flow into :samp:`t`, the sink, is ``` ``` stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not ``` ``` specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such ``` ``` that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum ``` ``` :samp:`s`-:samp:`t` cut. ``` ``` ``` ``` Examples ``` ``` -------- ``` ``` >>> import networkx as nx ``` ``` >>> from networkx.algorithms.flow import dinitz ``` ``` ``` ``` The functions that implement flow algorithms and output a residual ``` ``` network, such as this one, are not imported to the base NetworkX ``` ``` namespace, so you have to explicitly import them from the flow package. ``` ``` ``` ``` >>> G = nx.DiGraph() ``` ``` >>> G.add_edge('x','a', capacity=3.0) ``` ``` >>> G.add_edge('x','b', capacity=1.0) ``` ``` >>> G.add_edge('a','c', capacity=3.0) ``` ``` >>> G.add_edge('b','c', capacity=5.0) ``` ``` >>> G.add_edge('b','d', capacity=4.0) ``` ``` >>> G.add_edge('d','e', capacity=2.0) ``` ``` >>> G.add_edge('c','y', capacity=2.0) ``` ``` >>> G.add_edge('e','y', capacity=3.0) ``` ``` >>> R = dinitz(G, 'x', 'y') ``` ``` >>> flow_value = nx.maximum_flow_value(G, 'x', 'y') ``` ``` >>> flow_value ``` ``` 3.0 ``` ``` >>> flow_value == R.graph['flow_value'] ``` ``` True ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  Dinitz' Algorithm: The Original Version and Even's Version. ``` ``` 2006. Yefim Dinitz. In Theoretical Computer Science. Lecture ``` ``` Notes in Computer Science. Volume 3895. pp 218-240. ``` ``` http://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf ``` ``` ``` ``` """ ``` ``` R = dinitz_impl(G, s, t, capacity, residual, cutoff) ``` ``` R.graph['algorithm'] = 'dinitz' ``` ``` return R ``` ```def dinitz_impl(G, s, t, capacity, residual, cutoff): ``` ``` if s not in G: ``` ``` raise nx.NetworkXError('node %s not in graph' % str(s)) ``` ``` if t not in G: ``` ``` raise nx.NetworkXError('node %s not in graph' % str(t)) ``` ``` if s == t: ``` ``` raise nx.NetworkXError('source and sink are the same node') ``` ``` if residual is None: ``` ``` R = build_residual_network(G, capacity) ``` ``` else: ``` ``` R = residual ``` ``` # Initialize/reset the residual network. ``` ``` for u in R: ``` ``` for e in R[u].values(): ``` ``` e['flow'] = 0 ``` ``` # Use an arbitrary high value as infinite. It is computed ``` ``` # when building the residual network. ``` ``` INF = R.graph['inf'] ``` ``` if cutoff is None: ``` ``` cutoff = INF ``` ``` R_succ = R.succ ``` ``` R_pred = R.pred ``` ``` def breath_first_search(): ``` ``` parents = {} ``` ``` queue = deque([s]) ``` ``` while queue: ``` ``` if t in parents: ``` ``` break ``` ``` u = queue.popleft() ``` ``` for v in R_succ[u]: ``` ``` attr = R_succ[u][v] ``` ``` if v not in parents and attr['capacity'] - attr['flow'] > 0: ``` ``` parents[v] = u ``` ``` queue.append(v) ``` ``` return parents ``` ``` def depth_first_search(parents): ``` ``` """Build a path using DFS starting from the sink""" ``` ``` path = [] ``` ``` u = t ``` ``` flow = INF ``` ``` while u != s: ``` ``` path.append(u) ``` ``` v = parents[u] ``` ``` flow = min(flow, R_pred[u][v]['capacity'] - R_pred[u][v]['flow']) ``` ``` u = v ``` ``` path.append(s) ``` ``` # Augment the flow along the path found ``` ``` if flow > 0: ``` ``` for u, v in pairwise(path): ``` ``` R_pred[u][v]['flow'] += flow ``` ``` R_pred[v][u]['flow'] -= flow ``` ``` return flow ``` ``` flow_value = 0 ``` ``` while flow_value < cutoff: ``` ``` parents = breath_first_search() ``` ``` if t not in parents: ``` ``` break ``` ``` this_flow = depth_first_search(parents) ``` ``` if this_flow * 2 > INF: ``` ``` raise nx.NetworkXUnbounded( ``` ``` 'Infinite capacity path, flow unbounded above.') ``` ``` flow_value += this_flow ``` ``` R.graph['flow_value'] = flow_value ``` ``` return R ```