ioftools / networkxMiCe / networkxmaster / networkx / algorithms / flow / edmondskarp.py @ 5cef0f13
History  View  Annotate  Download (8.01 KB)
1 
# * coding: utf8 *


2 
"""

3 
EdmondsKarp algorithm for maximum flow problems.

4 
"""

5  
6 
__author__ = """ysitu <ysitu@users.noreply.github.com>"""

7 
# Copyright (C) 2014 ysitu <ysitu@users.noreply.github.com>

8 
# All rights reserved.

9 
# BSD license.

10  
11 
import networkx as nx 
12 
from networkx.algorithms.flow.utils import * 
13  
14 
__all__ = ['edmonds_karp']

15  
16  
17 
def edmonds_karp_core(R, s, t, cutoff): 
18 
"""Implementation of the EdmondsKarp algorithm.

19 
"""

20 
R_nodes = R.nodes 
21 
R_pred = R.pred 
22 
R_succ = R.succ 
23  
24 
inf = R.graph['inf']

25  
26 
def augment(path): 
27 
"""Augment flow along a path from s to t.

28 
"""

29 
# Determine the path residual capacity.

30 
flow = inf 
31 
it = iter(path)

32 
u = next(it)

33 
for v in it: 
34 
attr = R_succ[u][v] 
35 
flow = min(flow, attr['capacity']  attr['flow']) 
36 
u = v 
37 
if flow * 2 > inf: 
38 
raise nx.NetworkXUnbounded(

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

40 
# Augment flow along the path.

41 
it = iter(path)

42 
u = next(it)

43 
for v in it: 
44 
R_succ[u][v]['flow'] += flow

45 
R_succ[v][u]['flow'] = flow

46 
u = v 
47 
return flow

48  
49 
def bidirectional_bfs(): 
50 
"""Bidirectional breadthfirst search for an augmenting path.

51 
"""

52 
pred = {s: None}

53 
q_s = [s] 
54 
succ = {t: None}

55 
q_t = [t] 
56 
while True: 
57 
q = [] 
58 
if len(q_s) <= len(q_t): 
59 
for u in q_s: 
60 
for v, attr in R_succ[u].items(): 
61 
if v not in pred and attr['flow'] < attr['capacity']: 
62 
pred[v] = u 
63 
if v in succ: 
64 
return v, pred, succ

65 
q.append(v) 
66 
if not q: 
67 
return None, None, None 
68 
q_s = q 
69 
else:

70 
for u in q_t: 
71 
for v, attr in R_pred[u].items(): 
72 
if v not in succ and attr['flow'] < attr['capacity']: 
73 
succ[v] = u 
74 
if v in pred: 
75 
return v, pred, succ

76 
q.append(v) 
77 
if not q: 
78 
return None, None, None 
79 
q_t = q 
80  
81 
# Look for shortest augmenting paths using breadthfirst search.

82 
flow_value = 0

83 
while flow_value < cutoff:

84 
v, pred, succ = bidirectional_bfs() 
85 
if pred is None: 
86 
break

87 
path = [v] 
88 
# Trace a path from s to v.

89 
u = v 
90 
while u != s:

91 
u = pred[u] 
92 
path.append(u) 
93 
path.reverse() 
94 
# Trace a path from v to t.

95 
u = v 
96 
while u != t:

97 
u = succ[u] 
98 
path.append(u) 
99 
flow_value += augment(path) 
100  
101 
return flow_value

102  
103  
104 
def edmonds_karp_impl(G, s, t, capacity, residual, cutoff): 
105 
"""Implementation of the EdmondsKarp algorithm.

106 
"""

107 
if s not in G: 
108 
raise nx.NetworkXError('node %s not in graph' % str(s)) 
109 
if t not in G: 
110 
raise nx.NetworkXError('node %s not in graph' % str(t)) 
111 
if s == t:

112 
raise nx.NetworkXError('source and sink are the same node') 
113  
114 
if residual is None: 
115 
R = build_residual_network(G, capacity) 
116 
else:

117 
R = residual 
118  
119 
# Initialize/reset the residual network.

120 
for u in R: 
121 
for e in R[u].values(): 
122 
e['flow'] = 0 
123  
124 
if cutoff is None: 
125 
cutoff = float('inf') 
126 
R.graph['flow_value'] = edmonds_karp_core(R, s, t, cutoff)

127  
128 
return R

129  
130  
131 
def edmonds_karp(G, s, t, capacity='capacity', residual=None, value_only=False, 
132 
cutoff=None):

133 
"""Find a maximum singlecommodity flow using the EdmondsKarp algorithm.

134 

135 
This function returns the residual network resulting after computing

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

137 
NetworkX uses for defining residual networks.

138 

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

140 
edges.

141 

142 

143 
Parameters

144 


145 
G : NetworkX graph

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

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

148 
considered to have infinite capacity.

149 

150 
s : node

151 
Source node for the flow.

152 

153 
t : node

154 
Sink node for the flow.

155 

156 
capacity : string

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

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

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

160 
infinite capacity. Default value: 'capacity'.

161 

162 
residual : NetworkX graph

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

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

165 

166 
value_only : bool

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

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

169 

170 
cutoff : integer, float

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

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

173 
determine a minimum cut. Default value: None.

174 

175 
Returns

176 


177 
R : NetworkX DiGraph

178 
Residual network after computing the maximum flow.

179 

180 
Raises

181 


182 
NetworkXError

183 
The algorithm does not support MultiGraph and MultiDiGraph. If

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

185 
NetworkXError is raised.

186 

187 
NetworkXUnbounded

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

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

190 
raises a NetworkXUnbounded.

191 

192 
See also

193 


194 
:meth:`maximum_flow`

195 
:meth:`minimum_cut`

196 
:meth:`preflow_push`

197 
:meth:`shortest_augmenting_path`

198 

199 
Notes

200 


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

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

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

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

205 
in :samp:`G`.

206 

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

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

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

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

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

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

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

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

215 

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

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

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

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

220 
:samp:`s`:samp:`t` cut.

221 

222 
Examples

223 


224 
>>> import networkx as nx

225 
>>> from networkx.algorithms.flow import edmonds_karp

226 

227 
The functions that implement flow algorithms and output a residual

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

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

230 

231 
>>> G = nx.DiGraph()

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

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

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

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

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

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

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

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

240 
>>> R = edmonds_karp(G, 'x', 'y')

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

242 
>>> flow_value

243 
3.0

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

245 
True

246 

247 
"""

248 
R = edmonds_karp_impl(G, s, t, capacity, residual, cutoff) 
249 
R.graph['algorithm'] = 'edmonds_karp' 
250 
return R
