ioftools / networkxMiCe / networkxmaster / networkx / algorithms / flow / dinitz_alg.py @ 5cef0f13
History  View  Annotate  Download (7.27 KB)
1 
# dinitz.py  Dinitz' algorithm for maximum flow problems.


2 
#

3 
# Copyright 20162019 NetworkX developers.

4 
#

5 
# This file is part of NetworkX.

6 
#

7 
# NetworkX is distributed under a BSD license; see LICENSE.txt for more

8 
# information.

9 
#

10 
# Author: Jordi Torrents <jordi.t21@gmail.com>

11 
"""

12 
Dinitz' algorithm for maximum flow problems.

13 
"""

14 
from collections import deque 
15  
16 
import networkx as nx 
17 
from networkx.algorithms.flow.utils import build_residual_network 
18 
from networkx.utils import pairwise 
19  
20 
__all__ = ['dinitz']

21  
22  
23 
def dinitz(G, s, t, capacity='capacity', residual=None, value_only=False, cutoff=None): 
24 
"""Find a maximum singlecommodity flow using Dinitz' algorithm.

25 

26 
This function returns the residual network resulting after computing

27 
the maximum flow. See below for details about the conventions

28 
NetworkX uses for defining residual networks.

29 

30 
This algorithm has a running time of $O(n^2 m)$ for $n$ nodes and $m$

31 
edges [1]_.

32 

33 

34 
Parameters

35 


36 
G : NetworkX graph

37 
Edges of the graph are expected to have an attribute called

38 
'capacity'. If this attribute is not present, the edge is

39 
considered to have infinite capacity.

40 

41 
s : node

42 
Source node for the flow.

43 

44 
t : node

45 
Sink node for the flow.

46 

47 
capacity : string

48 
Edges of the graph G are expected to have an attribute capacity

49 
that indicates how much flow the edge can support. If this

50 
attribute is not present, the edge is considered to have

51 
infinite capacity. Default value: 'capacity'.

52 

53 
residual : NetworkX graph

54 
Residual network on which the algorithm is to be executed. If None, a

55 
new residual network is created. Default value: None.

56 

57 
value_only : bool

58 
If True compute only the value of the maximum flow. This parameter

59 
will be ignored by this algorithm because it is not applicable.

60 

61 
cutoff : integer, float

62 
If specified, the algorithm will terminate when the flow value reaches

63 
or exceeds the cutoff. In this case, it may be unable to immediately

64 
determine a minimum cut. Default value: None.

65 

66 
Returns

67 


68 
R : NetworkX DiGraph

69 
Residual network after computing the maximum flow.

70 

71 
Raises

72 


73 
NetworkXError

74 
The algorithm does not support MultiGraph and MultiDiGraph. If

75 
the input graph is an instance of one of these two classes, a

76 
NetworkXError is raised.

77 

78 
NetworkXUnbounded

79 
If the graph has a path of infinite capacity, the value of a

80 
feasible flow on the graph is unbounded above and the function

81 
raises a NetworkXUnbounded.

82 

83 
See also

84 


85 
:meth:`maximum_flow`

86 
:meth:`minimum_cut`

87 
:meth:`preflow_push`

88 
:meth:`shortest_augmenting_path`

89 

90 
Notes

91 


92 
The residual network :samp:`R` from an input graph :samp:`G` has the

93 
same nodes as :samp:`G`. :samp:`R` is a DiGraph that contains a pair

94 
of edges :samp:`(u, v)` and :samp:`(v, u)` iff :samp:`(u, v)` is not a

95 
selfloop, and at least one of :samp:`(u, v)` and :samp:`(v, u)` exists

96 
in :samp:`G`.

97 

98 
For each edge :samp:`(u, v)` in :samp:`R`, :samp:`R[u][v]['capacity']`

99 
is equal to the capacity of :samp:`(u, v)` in :samp:`G` if it exists

100 
in :samp:`G` or zero otherwise. If the capacity is infinite,

101 
:samp:`R[u][v]['capacity']` will have a high arbitrary finite value

102 
that does not affect the solution of the problem. This value is stored in

103 
:samp:`R.graph['inf']`. For each edge :samp:`(u, v)` in :samp:`R`,

104 
:samp:`R[u][v]['flow']` represents the flow function of :samp:`(u, v)` and

105 
satisfies :samp:`R[u][v]['flow'] == R[v][u]['flow']`.

106 

107 
The flow value, defined as the total flow into :samp:`t`, the sink, is

108 
stored in :samp:`R.graph['flow_value']`. If :samp:`cutoff` is not

109 
specified, reachability to :samp:`t` using only edges :samp:`(u, v)` such

110 
that :samp:`R[u][v]['flow'] < R[u][v]['capacity']` induces a minimum

111 
:samp:`s`:samp:`t` cut.

112 

113 
Examples

114 


115 
>>> import networkx as nx

116 
>>> from networkx.algorithms.flow import dinitz

117 

118 
The functions that implement flow algorithms and output a residual

119 
network, such as this one, are not imported to the base NetworkX

120 
namespace, so you have to explicitly import them from the flow package.

121 

122 
>>> G = nx.DiGraph()

123 
>>> G.add_edge('x','a', capacity=3.0)

124 
>>> G.add_edge('x','b', capacity=1.0)

125 
>>> G.add_edge('a','c', capacity=3.0)

126 
>>> G.add_edge('b','c', capacity=5.0)

127 
>>> G.add_edge('b','d', capacity=4.0)

128 
>>> G.add_edge('d','e', capacity=2.0)

129 
>>> G.add_edge('c','y', capacity=2.0)

130 
>>> G.add_edge('e','y', capacity=3.0)

131 
>>> R = dinitz(G, 'x', 'y')

132 
>>> flow_value = nx.maximum_flow_value(G, 'x', 'y')

133 
>>> flow_value

134 
3.0

135 
>>> flow_value == R.graph['flow_value']

136 
True

137 

138 
References

139 


140 
.. [1] Dinitz' Algorithm: The Original Version and Even's Version.

141 
2006. Yefim Dinitz. In Theoretical Computer Science. Lecture

142 
Notes in Computer Science. Volume 3895. pp 218240.

143 
http://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf

144 

145 
"""

146 
R = dinitz_impl(G, s, t, capacity, residual, cutoff) 
147 
R.graph['algorithm'] = 'dinitz' 
148 
return R

149  
150  
151 
def dinitz_impl(G, s, t, capacity, residual, cutoff): 
152 
if s not in G: 
153 
raise nx.NetworkXError('node %s not in graph' % str(s)) 
154 
if t not in G: 
155 
raise nx.NetworkXError('node %s not in graph' % str(t)) 
156 
if s == t:

157 
raise nx.NetworkXError('source and sink are the same node') 
158  
159 
if residual is None: 
160 
R = build_residual_network(G, capacity) 
161 
else:

162 
R = residual 
163  
164 
# Initialize/reset the residual network.

165 
for u in R: 
166 
for e in R[u].values(): 
167 
e['flow'] = 0 
168  
169 
# Use an arbitrary high value as infinite. It is computed

170 
# when building the residual network.

171 
INF = R.graph['inf']

172  
173 
if cutoff is None: 
174 
cutoff = INF 
175  
176 
R_succ = R.succ 
177 
R_pred = R.pred 
178  
179 
def breath_first_search(): 
180 
parents = {} 
181 
queue = deque([s]) 
182 
while queue:

183 
if t in parents: 
184 
break

185 
u = queue.popleft() 
186 
for v in R_succ[u]: 
187 
attr = R_succ[u][v] 
188 
if v not in parents and attr['capacity']  attr['flow'] > 0: 
189 
parents[v] = u 
190 
queue.append(v) 
191 
return parents

192  
193 
def depth_first_search(parents): 
194 
"""Build a path using DFS starting from the sink"""

195 
path = [] 
196 
u = t 
197 
flow = INF 
198 
while u != s:

199 
path.append(u) 
200 
v = parents[u] 
201 
flow = min(flow, R_pred[u][v]['capacity']  R_pred[u][v]['flow']) 
202 
u = v 
203 
path.append(s) 
204 
# Augment the flow along the path found

205 
if flow > 0: 
206 
for u, v in pairwise(path): 
207 
R_pred[u][v]['flow'] += flow

208 
R_pred[v][u]['flow'] = flow

209 
return flow

210  
211 
flow_value = 0

212 
while flow_value < cutoff:

213 
parents = breath_first_search() 
214 
if t not in parents: 
215 
break

216 
this_flow = depth_first_search(parents) 
217 
if this_flow * 2 > INF: 
218 
raise nx.NetworkXUnbounded(

219 
'Infinite capacity path, flow unbounded above.')

220 
flow_value += this_flow 
221  
222 
R.graph['flow_value'] = flow_value

223 
return R
