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


2 
"""

3 
Flow based cut algorithms

4 
"""

5 
import itertools 
6 
import networkx as nx 
7  
8 
# Define the default maximum flow function to use in all flow based

9 
# cut algorithms.

10 
from networkx.algorithms.flow import edmonds_karp 
11 
from networkx.algorithms.flow import build_residual_network 
12 
default_flow_func = edmonds_karp 
13  
14 
from .utils import (build_auxiliary_node_connectivity, 
15 
build_auxiliary_edge_connectivity) 
16  
17 
__author__ = '\n'.join(['Jordi Torrents <jtorrents@milnou.net>']) 
18  
19 
__all__ = ['minimum_st_node_cut',

20 
'minimum_node_cut',

21 
'minimum_st_edge_cut',

22 
'minimum_edge_cut']

23  
24  
25 
def minimum_st_edge_cut(G, s, t, flow_func=None, auxiliary=None, 
26 
residual=None):

27 
"""Returns the edges of the cutset of a minimum (s, t)cut.

28 

29 
This function returns the set of edges of minimum cardinality that,

30 
if removed, would destroy all paths among source and target in G.

31 
Edge weights are not considered. See :meth:`minimum_cut` for

32 
computing minimum cuts considering edge weights.

33 

34 
Parameters

35 


36 
G : NetworkX graph

37 

38 
s : node

39 
Source node for the flow.

40 

41 
t : node

42 
Sink node for the flow.

43 

44 
auxiliary : NetworkX DiGraph

45 
Auxiliary digraph to compute flow based node connectivity. It has

46 
to have a graph attribute called mapping with a dictionary mapping

47 
node names in G and in the auxiliary digraph. If provided

48 
it will be reused instead of recreated. Default value: None.

49 

50 
flow_func : function

51 
A function for computing the maximum flow among a pair of nodes.

52 
The function has to accept at least three parameters: a Digraph,

53 
a source node, and a target node. And return a residual network

54 
that follows NetworkX conventions (see :meth:`maximum_flow` for

55 
details). If flow_func is None, the default maximum flow function

56 
(:meth:`edmonds_karp`) is used. See :meth:`node_connectivity` for

57 
details. The choice of the default function may change from version

58 
to version and should not be relied on. Default value: None.

59 

60 
residual : NetworkX DiGraph

61 
Residual network to compute maximum flow. If provided it will be

62 
reused instead of recreated. Default value: None.

63 

64 
Returns

65 


66 
cutset : set

67 
Set of edges that, if removed from the graph, will disconnect it.

68 

69 
See also

70 


71 
:meth:`minimum_cut`

72 
:meth:`minimum_node_cut`

73 
:meth:`minimum_edge_cut`

74 
:meth:`stoer_wagner`

75 
:meth:`node_connectivity`

76 
:meth:`edge_connectivity`

77 
:meth:`maximum_flow`

78 
:meth:`edmonds_karp`

79 
:meth:`preflow_push`

80 
:meth:`shortest_augmenting_path`

81 

82 
Examples

83 


84 
This function is not imported in the base NetworkX namespace, so you

85 
have to explicitly import it from the connectivity package:

86 

87 
>>> from networkx.algorithms.connectivity import minimum_st_edge_cut

88 

89 
We use in this example the platonic icosahedral graph, which has edge

90 
connectivity 5.

91 

92 
>>> G = nx.icosahedral_graph()

93 
>>> len(minimum_st_edge_cut(G, 0, 6))

94 
5

95 

96 
If you need to compute local edge cuts on several pairs of

97 
nodes in the same graph, it is recommended that you reuse the

98 
data structures that NetworkX uses in the computation: the

99 
auxiliary digraph for edge connectivity, and the residual

100 
network for the underlying maximum flow computation.

101 

102 
Example of how to compute local edge cuts among all pairs of

103 
nodes of the platonic icosahedral graph reusing the data

104 
structures.

105 

106 
>>> import itertools

107 
>>> # You also have to explicitly import the function for

108 
>>> # building the auxiliary digraph from the connectivity package

109 
>>> from networkx.algorithms.connectivity import (

110 
... build_auxiliary_edge_connectivity)

111 
>>> H = build_auxiliary_edge_connectivity(G)

112 
>>> # And the function for building the residual network from the

113 
>>> # flow package

114 
>>> from networkx.algorithms.flow import build_residual_network

115 
>>> # Note that the auxiliary digraph has an edge attribute named capacity

116 
>>> R = build_residual_network(H, 'capacity')

117 
>>> result = dict.fromkeys(G, dict())

118 
>>> # Reuse the auxiliary digraph and the residual network by passing them

119 
>>> # as parameters

120 
>>> for u, v in itertools.combinations(G, 2):

121 
... k = len(minimum_st_edge_cut(G, u, v, auxiliary=H, residual=R))

122 
... result[u][v] = k

123 
>>> all(result[u][v] == 5 for u, v in itertools.combinations(G, 2))

124 
True

125 

126 
You can also use alternative flow algorithms for computing edge

127 
cuts. For instance, in dense networks the algorithm

128 
:meth:`shortest_augmenting_path` will usually perform better than

129 
the default :meth:`edmonds_karp` which is faster for sparse

130 
networks with highly skewed degree distributions. Alternative flow

131 
functions have to be explicitly imported from the flow package.

132 

133 
>>> from networkx.algorithms.flow import shortest_augmenting_path

134 
>>> len(minimum_st_edge_cut(G, 0, 6, flow_func=shortest_augmenting_path))

135 
5

136 

137 
"""

138 
if flow_func is None: 
139 
flow_func = default_flow_func 
140  
141 
if auxiliary is None: 
142 
H = build_auxiliary_edge_connectivity(G) 
143 
else:

144 
H = auxiliary 
145  
146 
kwargs = dict(capacity='capacity', flow_func=flow_func, residual=residual) 
147  
148 
cut_value, partition = nx.minimum_cut(H, s, t, **kwargs) 
149 
reachable, non_reachable = partition 
150 
# Any edge in the original graph linking the two sets in the

151 
# partition is part of the edge cutset

152 
cutset = set()

153 
for u, nbrs in ((n, G[n]) for n in reachable): 
154 
cutset.update((u, v) for v in nbrs if v in non_reachable) 
155  
156 
return cutset

157  
158  
159 
def minimum_st_node_cut(G, s, t, flow_func=None, auxiliary=None, residual=None): 
160 
r"""Returns a set of nodes of minimum cardinality that disconnect source

161 
from target in G.

162 

163 
This function returns the set of nodes of minimum cardinality that,

164 
if removed, would destroy all paths among source and target in G.

165 

166 
Parameters

167 


168 
G : NetworkX graph

169 

170 
s : node

171 
Source node.

172 

173 
t : node

174 
Target node.

175 

176 
flow_func : function

177 
A function for computing the maximum flow among a pair of nodes.

178 
The function has to accept at least three parameters: a Digraph,

179 
a source node, and a target node. And return a residual network

180 
that follows NetworkX conventions (see :meth:`maximum_flow` for

181 
details). If flow_func is None, the default maximum flow function

182 
(:meth:`edmonds_karp`) is used. See below for details. The choice

183 
of the default function may change from version to version and

184 
should not be relied on. Default value: None.

185 

186 
auxiliary : NetworkX DiGraph

187 
Auxiliary digraph to compute flow based node connectivity. It has

188 
to have a graph attribute called mapping with a dictionary mapping

189 
node names in G and in the auxiliary digraph. If provided

190 
it will be reused instead of recreated. Default value: None.

191 

192 
residual : NetworkX DiGraph

193 
Residual network to compute maximum flow. If provided it will be

194 
reused instead of recreated. Default value: None.

195 

196 
Returns

197 


198 
cutset : set

199 
Set of nodes that, if removed, would destroy all paths between

200 
source and target in G.

201 

202 
Examples

203 


204 
This function is not imported in the base NetworkX namespace, so you

205 
have to explicitly import it from the connectivity package:

206 

207 
>>> from networkx.algorithms.connectivity import minimum_st_node_cut

208 

209 
We use in this example the platonic icosahedral graph, which has node

210 
connectivity 5.

211 

212 
>>> G = nx.icosahedral_graph()

213 
>>> len(minimum_st_node_cut(G, 0, 6))

214 
5

215 

216 
If you need to compute local st cuts between several pairs of

217 
nodes in the same graph, it is recommended that you reuse the

218 
data structures that NetworkX uses in the computation: the

219 
auxiliary digraph for node connectivity and node cuts, and the

220 
residual network for the underlying maximum flow computation.

221 

222 
Example of how to compute local st node cuts reusing the data

223 
structures:

224 

225 
>>> # You also have to explicitly import the function for

226 
>>> # building the auxiliary digraph from the connectivity package

227 
>>> from networkx.algorithms.connectivity import (

228 
... build_auxiliary_node_connectivity)

229 
>>> H = build_auxiliary_node_connectivity(G)

230 
>>> # And the function for building the residual network from the

231 
>>> # flow package

232 
>>> from networkx.algorithms.flow import build_residual_network

233 
>>> # Note that the auxiliary digraph has an edge attribute named capacity

234 
>>> R = build_residual_network(H, 'capacity')

235 
>>> # Reuse the auxiliary digraph and the residual network by passing them

236 
>>> # as parameters

237 
>>> len(minimum_st_node_cut(G, 0, 6, auxiliary=H, residual=R))

238 
5

239 

240 
You can also use alternative flow algorithms for computing minimum st

241 
node cuts. For instance, in dense networks the algorithm

242 
:meth:`shortest_augmenting_path` will usually perform better than

243 
the default :meth:`edmonds_karp` which is faster for sparse

244 
networks with highly skewed degree distributions. Alternative flow

245 
functions have to be explicitly imported from the flow package.

246 

247 
>>> from networkx.algorithms.flow import shortest_augmenting_path

248 
>>> len(minimum_st_node_cut(G, 0, 6, flow_func=shortest_augmenting_path))

249 
5

250 

251 
Notes

252 


253 
This is a flow based implementation of minimum node cut. The algorithm

254 
is based in solving a number of maximum flow computations to determine

255 
the capacity of the minimum cut on an auxiliary directed network that

256 
corresponds to the minimum node cut of G. It handles both directed

257 
and undirected graphs. This implementation is based on algorithm 11

258 
in [1]_.

259 

260 
See also

261 


262 
:meth:`minimum_node_cut`

263 
:meth:`minimum_edge_cut`

264 
:meth:`stoer_wagner`

265 
:meth:`node_connectivity`

266 
:meth:`edge_connectivity`

267 
:meth:`maximum_flow`

268 
:meth:`edmonds_karp`

269 
:meth:`preflow_push`

270 
:meth:`shortest_augmenting_path`

271 

272 
References

273 


274 
.. [1] AbdolHossein Esfahanian. Connectivity Algorithms.

275 
http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

276 

277 
"""

278 
if auxiliary is None: 
279 
H = build_auxiliary_node_connectivity(G) 
280 
else:

281 
H = auxiliary 
282  
283 
mapping = H.graph.get('mapping', None) 
284 
if mapping is None: 
285 
raise nx.NetworkXError('Invalid auxiliary digraph.') 
286 
if G.has_edge(s, t) or G.has_edge(t, s): 
287 
return []

288 
kwargs = dict(flow_func=flow_func, residual=residual, auxiliary=H)

289  
290 
# The edge cut in the auxiliary digraph corresponds to the node cut in the

291 
# original graph.

292 
edge_cut = minimum_st_edge_cut(H, '%sB' % mapping[s], '%sA' % mapping[t], 
293 
**kwargs) 
294 
# Each node in the original graph maps to two nodes of the auxiliary graph

295 
node_cut = set(H.nodes[node]['id'] for edge in edge_cut for node in edge) 
296 
return node_cut  set([s, t]) 
297  
298  
299 
def minimum_node_cut(G, s=None, t=None, flow_func=None): 
300 
r"""Returns a set of nodes of minimum cardinality that disconnects G.

301 

302 
If source and target nodes are provided, this function returns the

303 
set of nodes of minimum cardinality that, if removed, would destroy

304 
all paths among source and target in G. If not, it returns a set

305 
of nodes of minimum cardinality that disconnects G.

306 

307 
Parameters

308 


309 
G : NetworkX graph

310 

311 
s : node

312 
Source node. Optional. Default value: None.

313 

314 
t : node

315 
Target node. Optional. Default value: None.

316 

317 
flow_func : function

318 
A function for computing the maximum flow among a pair of nodes.

319 
The function has to accept at least three parameters: a Digraph,

320 
a source node, and a target node. And return a residual network

321 
that follows NetworkX conventions (see :meth:`maximum_flow` for

322 
details). If flow_func is None, the default maximum flow function

323 
(:meth:`edmonds_karp`) is used. See below for details. The

324 
choice of the default function may change from version

325 
to version and should not be relied on. Default value: None.

326 

327 
Returns

328 


329 
cutset : set

330 
Set of nodes that, if removed, would disconnect G. If source

331 
and target nodes are provided, the set contains the nodes that

332 
if removed, would destroy all paths between source and target.

333 

334 
Examples

335 


336 
>>> # Platonic icosahedral graph has node connectivity 5

337 
>>> G = nx.icosahedral_graph()

338 
>>> node_cut = nx.minimum_node_cut(G)

339 
>>> len(node_cut)

340 
5

341 

342 
You can use alternative flow algorithms for the underlying maximum

343 
flow computation. In dense networks the algorithm

344 
:meth:`shortest_augmenting_path` will usually perform better

345 
than the default :meth:`edmonds_karp`, which is faster for

346 
sparse networks with highly skewed degree distributions. Alternative

347 
flow functions have to be explicitly imported from the flow package.

348 

349 
>>> from networkx.algorithms.flow import shortest_augmenting_path

350 
>>> node_cut == nx.minimum_node_cut(G, flow_func=shortest_augmenting_path)

351 
True

352 

353 
If you specify a pair of nodes (source and target) as parameters,

354 
this function returns a local st node cut.

355 

356 
>>> len(nx.minimum_node_cut(G, 3, 7))

357 
5

358 

359 
If you need to perform several local st cuts among different

360 
pairs of nodes on the same graph, it is recommended that you reuse

361 
the data structures used in the maximum flow computations. See

362 
:meth:`minimum_st_node_cut` for details.

363 

364 
Notes

365 


366 
This is a flow based implementation of minimum node cut. The algorithm

367 
is based in solving a number of maximum flow computations to determine

368 
the capacity of the minimum cut on an auxiliary directed network that

369 
corresponds to the minimum node cut of G. It handles both directed

370 
and undirected graphs. This implementation is based on algorithm 11

371 
in [1]_.

372 

373 
See also

374 


375 
:meth:`minimum_st_node_cut`

376 
:meth:`minimum_cut`

377 
:meth:`minimum_edge_cut`

378 
:meth:`stoer_wagner`

379 
:meth:`node_connectivity`

380 
:meth:`edge_connectivity`

381 
:meth:`maximum_flow`

382 
:meth:`edmonds_karp`

383 
:meth:`preflow_push`

384 
:meth:`shortest_augmenting_path`

385 

386 
References

387 


388 
.. [1] AbdolHossein Esfahanian. Connectivity Algorithms.

389 
http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

390 

391 
"""

392 
if (s is not None and t is None) or (s is None and t is not None): 
393 
raise nx.NetworkXError('Both source and target must be specified.') 
394  
395 
# Local minimum node cut.

396 
if s is not None and t is not None: 
397 
if s not in G: 
398 
raise nx.NetworkXError('node %s not in graph' % s) 
399 
if t not in G: 
400 
raise nx.NetworkXError('node %s not in graph' % t) 
401 
return minimum_st_node_cut(G, s, t, flow_func=flow_func)

402  
403 
# Global minimum node cut.

404 
# Analog to the algorithm 11 for global node connectivity in [1].

405 
if G.is_directed():

406 
if not nx.is_weakly_connected(G): 
407 
raise nx.NetworkXError('Input graph is not connected') 
408 
iter_func = itertools.permutations 
409  
410 
def neighbors(v): 
411 
return itertools.chain.from_iterable([G.predecessors(v),

412 
G.successors(v)]) 
413 
else:

414 
if not nx.is_connected(G): 
415 
raise nx.NetworkXError('Input graph is not connected') 
416 
iter_func = itertools.combinations 
417 
neighbors = G.neighbors 
418  
419 
# Reuse the auxiliary digraph and the residual network.

420 
H = build_auxiliary_node_connectivity(G) 
421 
R = build_residual_network(H, 'capacity')

422 
kwargs = dict(flow_func=flow_func, auxiliary=H, residual=R)

423  
424 
# Choose a node with minimum degree.

425 
v = min(G, key=G.degree)

426 
# Initial node cutset is all neighbors of the node with minimum degree.

427 
min_cut = set(G[v])

428 
# Compute st node cuts between v and all its nonneighbors nodes in G.

429 
for w in set(G)  set(neighbors(v))  set([v]): 
430 
this_cut = minimum_st_node_cut(G, v, w, **kwargs) 
431 
if len(min_cut) >= len(this_cut): 
432 
min_cut = this_cut 
433 
# Also for non adjacent pairs of neighbors of v.

434 
for x, y in iter_func(neighbors(v), 2): 
435 
if y in G[x]: 
436 
continue

437 
this_cut = minimum_st_node_cut(G, x, y, **kwargs) 
438 
if len(min_cut) >= len(this_cut): 
439 
min_cut = this_cut 
440  
441 
return min_cut

442  
443  
444 
def minimum_edge_cut(G, s=None, t=None, flow_func=None): 
445 
r"""Returns a set of edges of minimum cardinality that disconnects G.

446 

447 
If source and target nodes are provided, this function returns the

448 
set of edges of minimum cardinality that, if removed, would break

449 
all paths among source and target in G. If not, it returns a set of

450 
edges of minimum cardinality that disconnects G.

451 

452 
Parameters

453 


454 
G : NetworkX graph

455 

456 
s : node

457 
Source node. Optional. Default value: None.

458 

459 
t : node

460 
Target node. Optional. Default value: None.

461 

462 
flow_func : function

463 
A function for computing the maximum flow among a pair of nodes.

464 
The function has to accept at least three parameters: a Digraph,

465 
a source node, and a target node. And return a residual network

466 
that follows NetworkX conventions (see :meth:`maximum_flow` for

467 
details). If flow_func is None, the default maximum flow function

468 
(:meth:`edmonds_karp`) is used. See below for details. The

469 
choice of the default function may change from version

470 
to version and should not be relied on. Default value: None.

471 

472 
Returns

473 


474 
cutset : set

475 
Set of edges that, if removed, would disconnect G. If source

476 
and target nodes are provided, the set contains the edges that

477 
if removed, would destroy all paths between source and target.

478 

479 
Examples

480 


481 
>>> # Platonic icosahedral graph has edge connectivity 5

482 
>>> G = nx.icosahedral_graph()

483 
>>> len(nx.minimum_edge_cut(G))

484 
5

485 

486 
You can use alternative flow algorithms for the underlying

487 
maximum flow computation. In dense networks the algorithm

488 
:meth:`shortest_augmenting_path` will usually perform better

489 
than the default :meth:`edmonds_karp`, which is faster for

490 
sparse networks with highly skewed degree distributions.

491 
Alternative flow functions have to be explicitly imported

492 
from the flow package.

493 

494 
>>> from networkx.algorithms.flow import shortest_augmenting_path

495 
>>> len(nx.minimum_edge_cut(G, flow_func=shortest_augmenting_path))

496 
5

497 

498 
If you specify a pair of nodes (source and target) as parameters,

499 
this function returns the value of local edge connectivity.

500 

501 
>>> nx.edge_connectivity(G, 3, 7)

502 
5

503 

504 
If you need to perform several local computations among different

505 
pairs of nodes on the same graph, it is recommended that you reuse

506 
the data structures used in the maximum flow computations. See

507 
:meth:`local_edge_connectivity` for details.

508 

509 
Notes

510 


511 
This is a flow based implementation of minimum edge cut. For

512 
undirected graphs the algorithm works by finding a 'small' dominating

513 
set of nodes of G (see algorithm 7 in [1]_) and computing the maximum

514 
flow between an arbitrary node in the dominating set and the rest of

515 
nodes in it. This is an implementation of algorithm 6 in [1]_. For

516 
directed graphs, the algorithm does n calls to the max flow function.

517 
The function raises an error if the directed graph is not weakly

518 
connected and returns an empty set if it is weakly connected.

519 
It is an implementation of algorithm 8 in [1]_.

520 

521 
See also

522 


523 
:meth:`minimum_st_edge_cut`

524 
:meth:`minimum_node_cut`

525 
:meth:`stoer_wagner`

526 
:meth:`node_connectivity`

527 
:meth:`edge_connectivity`

528 
:meth:`maximum_flow`

529 
:meth:`edmonds_karp`

530 
:meth:`preflow_push`

531 
:meth:`shortest_augmenting_path`

532 

533 
References

534 


535 
.. [1] AbdolHossein Esfahanian. Connectivity Algorithms.

536 
http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

537 

538 
"""

539 
if (s is not None and t is None) or (s is None and t is not None): 
540 
raise nx.NetworkXError('Both source and target must be specified.') 
541  
542 
# reuse auxiliary digraph and residual network

543 
H = build_auxiliary_edge_connectivity(G) 
544 
R = build_residual_network(H, 'capacity')

545 
kwargs = dict(flow_func=flow_func, residual=R, auxiliary=H)

546  
547 
# Local minimum edge cut if s and t are not None

548 
if s is not None and t is not None: 
549 
if s not in G: 
550 
raise nx.NetworkXError('node %s not in graph' % s) 
551 
if t not in G: 
552 
raise nx.NetworkXError('node %s not in graph' % t) 
553 
return minimum_st_edge_cut(H, s, t, **kwargs)

554  
555 
# Global minimum edge cut

556 
# Analog to the algorithm for global edge connectivity

557 
if G.is_directed():

558 
# Based on algorithm 8 in [1]

559 
if not nx.is_weakly_connected(G): 
560 
raise nx.NetworkXError('Input graph is not connected') 
561  
562 
# Initial cutset is all edges of a node with minimum degree

563 
node = min(G, key=G.degree)

564 
min_cut = set(G.edges(node))

565 
nodes = list(G)

566 
n = len(nodes)

567 
for i in range(n): 
568 
try:

569 
this_cut = minimum_st_edge_cut(H, nodes[i], nodes[i + 1], **kwargs)

570 
if len(this_cut) <= len(min_cut): 
571 
min_cut = this_cut 
572 
except IndexError: # Last node! 
573 
this_cut = minimum_st_edge_cut(H, nodes[i], nodes[0], **kwargs)

574 
if len(this_cut) <= len(min_cut): 
575 
min_cut = this_cut 
576  
577 
return min_cut

578  
579 
else: # undirected 
580 
# Based on algorithm 6 in [1]

581 
if not nx.is_connected(G): 
582 
raise nx.NetworkXError('Input graph is not connected') 
583  
584 
# Initial cutset is all edges of a node with minimum degree

585 
node = min(G, key=G.degree)

586 
min_cut = set(G.edges(node))

587 
# A dominating set is \lambdacovering

588 
# We need a dominating set with at least two nodes

589 
for node in G: 
590 
D = nx.dominating_set(G, start_with=node) 
591 
v = D.pop() 
592 
if D:

593 
break

594 
else:

595 
# in complete graphs the dominating set will always be of one node

596 
# thus we return min_cut, which now contains the edges of a node

597 
# with minimum degree

598 
return min_cut

599 
for w in D: 
600 
this_cut = minimum_st_edge_cut(H, v, w, **kwargs) 
601 
if len(this_cut) <= len(min_cut): 
602 
min_cut = this_cut 
603  
604 
return min_cut
