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


2 
# Copyright (C) 20042019 by

3 
# Aric Hagberg <hagberg@lanl.gov>

4 
# Dan Schult <dschult@colgate.edu>

5 
# Pieter Swart <swart@lanl.gov>

6 
# All rights reserved.

7 
# BSD license.

8 
#

9 
# Authors: Jon Crall (erotemic@gmail.com)

10 
"""

11 
Algorithms for finding kedgeconnected components and subgraphs.

12 

13 
A kedgeconnected component (kedgecc) is a maximal set of nodes in G, such

14 
that all pairs of node have an edgeconnectivity of at least k.

15 

16 
A kedgeconnected subgraph (kedgesubgraph) is a maximal set of nodes in G,

17 
such that the subgraph of G defined by the nodes has an edgeconnectivity at

18 
least k.

19 
"""

20 
import networkx as nx 
21 
from networkx.utils import arbitrary_element 
22 
from networkx.utils import not_implemented_for 
23 
from networkx.algorithms import bridges 
24 
from functools import partial 
25 
import itertools as it 
26  
27 
__all__ = [ 
28 
'k_edge_components',

29 
'k_edge_subgraphs',

30 
'bridge_components',

31 
'EdgeComponentAuxGraph',

32 
] 
33  
34  
35 
@not_implemented_for('multigraph') 
36 
def k_edge_components(G, k): 
37 
"""Generates nodes in each maximal kedgeconnected component in G.

38 

39 
Parameters

40 


41 
G : NetworkX graph

42 

43 
k : Integer

44 
Desired edge connectivity

45 

46 
Returns

47 


48 
k_edge_components : a generator of kedgeccs. Each set of returned nodes

49 
will have kedgeconnectivity in the graph G.

50 

51 
See Also

52 


53 
:func:`local_edge_connectivity`

54 
:func:`k_edge_subgraphs` : similar to this function, but the subgraph

55 
defined by the nodes must also have kedgeconnectivity.

56 
:func:`k_components` : similar to this function, but uses nodeconnectivity

57 
instead of edgeconnectivity

58 

59 
Raises

60 


61 
NetworkXNotImplemented:

62 
If the input graph is a multigraph.

63 

64 
ValueError:

65 
If k is less than 1

66 

67 
Notes

68 


69 
Attempts to use the most efficient implementation available based on k.

70 
If k=1, this is simply simply connected components for directed graphs and

71 
connected components for undirected graphs.

72 
If k=2 on an efficient bridge connected component algorithm from _[1] is

73 
run based on the chain decomposition.

74 
Otherwise, the algorithm from _[2] is used.

75 

76 
Example

77 


78 
>>> import itertools as it

79 
>>> from networkx.utils import pairwise

80 
>>> paths = [

81 
... (1, 2, 4, 3, 1, 4),

82 
... (5, 6, 7, 8, 5, 7, 8, 6),

83 
... ]

84 
>>> G = nx.Graph()

85 
>>> G.add_nodes_from(it.chain(*paths))

86 
>>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))

87 
>>> # note this returns {1, 4} unlike k_edge_subgraphs

88 
>>> sorted(map(sorted, nx.k_edge_components(G, k=3)))

89 
[[1, 4], [2], [3], [5, 6, 7, 8]]

90 

91 
References

92 


93 
.. [1] https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29

94 
.. [2] Wang, Tianhao, et al. (2015) A simple algorithm for finding all

95 
kedgeconnected components.

96 
http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264

97 
"""

98 
# Compute kedgeccs using the most efficient algorithms available.

99 
if k < 1: 
100 
raise ValueError('k cannot be less than 1') 
101 
if G.is_directed():

102 
if k == 1: 
103 
return nx.strongly_connected_components(G)

104 
else:

105 
# TODO: investigate https://arxiv.org/abs/1412.6466 for k=2

106 
aux_graph = EdgeComponentAuxGraph.construct(G) 
107 
return aux_graph.k_edge_components(k)

108 
else:

109 
if k == 1: 
110 
return nx.connected_components(G)

111 
elif k == 2: 
112 
return bridge_components(G)

113 
else:

114 
aux_graph = EdgeComponentAuxGraph.construct(G) 
115 
return aux_graph.k_edge_components(k)

116  
117  
118 
@not_implemented_for('multigraph') 
119 
def k_edge_subgraphs(G, k): 
120 
"""Generates nodes in each maximal kedgeconnected subgraph in G.

121 

122 
Parameters

123 


124 
G : NetworkX graph

125 

126 
k : Integer

127 
Desired edge connectivity

128 

129 
Returns

130 


131 
k_edge_subgraphs : a generator of kedgesubgraphs

132 
Each kedgesubgraph is a maximal set of nodes that defines a subgraph

133 
of G that is kedgeconnected.

134 

135 
See Also

136 


137 
:func:`edge_connectivity`

138 
:func:`k_edge_components` : similar to this function, but nodes only

139 
need to have kedgeconnctivity within the graph G and the subgraphs

140 
might not be kedgeconnected.

141 

142 
Raises

143 


144 
NetworkXNotImplemented:

145 
If the input graph is a multigraph.

146 

147 
ValueError:

148 
If k is less than 1

149 

150 
Notes

151 


152 
Attempts to use the most efficient implementation available based on k.

153 
If k=1, or k=2 and the graph is undirected, then this simply calls

154 
`k_edge_components`. Otherwise the algorithm from _[1] is used.

155 

156 
Example

157 


158 
>>> import itertools as it

159 
>>> from networkx.utils import pairwise

160 
>>> paths = [

161 
... (1, 2, 4, 3, 1, 4),

162 
... (5, 6, 7, 8, 5, 7, 8, 6),

163 
... ]

164 
>>> G = nx.Graph()

165 
>>> G.add_nodes_from(it.chain(*paths))

166 
>>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))

167 
>>> # note this does not return {1, 4} unlike k_edge_components

168 
>>> sorted(map(sorted, nx.k_edge_subgraphs(G, k=3)))

169 
[[1], [2], [3], [4], [5, 6, 7, 8]]

170 

171 
References

172 


173 
.. [1] Zhou, Liu, et al. (2012) Finding maximal kedgeconnected subgraphs

174 
from a large graph. ACM International Conference on Extending Database

175 
Technology 2012 480–491.

176 
https://openproceedings.org/2012/conf/edbt/ZhouLYLCL12.pdf

177 
"""

178 
if k < 1: 
179 
raise ValueError('k cannot be less than 1') 
180 
if G.is_directed():

181 
if k <= 1: 
182 
# For directed graphs ,

183 
# When k == 1, kedgeccs and kedgesubgraphs are the same

184 
return k_edge_components(G, k)

185 
else:

186 
return _k_edge_subgraphs_nodes(G, k)

187 
else:

188 
if k <= 2: 
189 
# For undirected graphs,

190 
# when k <= 2, kedgeccs and kedgesubgraphs are the same

191 
return k_edge_components(G, k)

192 
else:

193 
return _k_edge_subgraphs_nodes(G, k)

194  
195  
196 
def _k_edge_subgraphs_nodes(G, k): 
197 
"""Helper to get the nodes from the subgraphs.

198 

199 
This allows k_edge_subgraphs to return a generator.

200 
"""

201 
for C in general_k_edge_subgraphs(G, k): 
202 
yield set(C.nodes()) 
203  
204  
205 
@not_implemented_for('directed') 
206 
@not_implemented_for('multigraph') 
207 
def bridge_components(G): 
208 
"""Finds all bridgeconnected components G.

209 

210 
Parameters

211 


212 
G : NetworkX undirected graph

213 

214 
Returns

215 


216 
bridge_components : a generator of 2edgeconnected components

217 

218 

219 
See Also

220 


221 
:func:`k_edge_subgraphs` : this function is a special case for an

222 
undirected graph where k=2.

223 
:func:`biconnected_components` : similar to this function, but is defined

224 
using 2nodeconnectivity instead of 2edgeconnectivity.

225 

226 
Raises

227 


228 
NetworkXNotImplemented:

229 
If the input graph is directed or a multigraph.

230 

231 
Notes

232 


233 
Bridgeconnected components are also known as 2edgeconnected components.

234 

235 
Example

236 


237 
>>> # The barbell graph with parameter zero has a single bridge

238 
>>> G = nx.barbell_graph(5, 0)

239 
>>> from networkx.algorithms.connectivity.edge_kcomponents import bridge_components

240 
>>> sorted(map(sorted, bridge_components(G)))

241 
[[0, 1, 2, 3, 4], [5, 6, 7, 8, 9]]

242 
"""

243 
H = G.copy() 
244 
H.remove_edges_from(bridges(G)) 
245 
for cc in nx.connected_components(H): 
246 
yield cc

247  
248  
249 
class EdgeComponentAuxGraph(object): 
250 
r"""A simple algorithm to find all kedgeconnected components in a graph.

251 

252 
Constructing the AuxillaryGraph (which may take some time) allows for the

253 
kedgeccs to be found in linear time for arbitrary k.

254 

255 
Notes

256 


257 
This implementation is based on [1]_. The idea is to construct an auxiliary

258 
graph from which the kedgeccs can be extracted in linear time. The

259 
auxiliary graph is constructed in $O(V\cdot F)$ operations, where F is the

260 
complexity of max flow. Querying the components takes an additional $O(V)$

261 
operations. This algorithm can be slow for large graphs, but it handles an

262 
arbitrary k and works for both directed and undirected inputs.

263 

264 
The undirected case for k=1 is exactly connected components.

265 
The undirected case for k=2 is exactly bridge connected components.

266 
The directed case for k=1 is exactly strongly connected components.

267 

268 
References

269 


270 
.. [1] Wang, Tianhao, et al. (2015) A simple algorithm for finding all

271 
kedgeconnected components.

272 
http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264

273 

274 
Example

275 


276 
>>> import itertools as it

277 
>>> from networkx.utils import pairwise

278 
>>> from networkx.algorithms.connectivity import EdgeComponentAuxGraph

279 
>>> # Build an interesting graph with multiple levels of kedgeccs

280 
>>> paths = [

281 
... (1, 2, 3, 4, 1, 3, 4, 2), # a 3edgecc (a 4 clique)

282 
... (5, 6, 7, 5), # a 2edgecc (a 3 clique)

283 
... (1, 5), # combine first two ccs into a 1edgecc

284 
... (0,), # add an additional disconnected 1edgecc

285 
... ]

286 
>>> G = nx.Graph()

287 
>>> G.add_nodes_from(it.chain(*paths))

288 
>>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))

289 
>>> # Constructing the AuxGraph takes about O(n ** 4)

290 
>>> aux_graph = EdgeComponentAuxGraph.construct(G)

291 
>>> # Once constructed, querying takes O(n)

292 
>>> sorted(map(sorted, aux_graph.k_edge_components(k=1)))

293 
[[0], [1, 2, 3, 4, 5, 6, 7]]

294 
>>> sorted(map(sorted, aux_graph.k_edge_components(k=2)))

295 
[[0], [1, 2, 3, 4], [5, 6, 7]]

296 
>>> sorted(map(sorted, aux_graph.k_edge_components(k=3)))

297 
[[0], [1, 2, 3, 4], [5], [6], [7]]

298 
>>> sorted(map(sorted, aux_graph.k_edge_components(k=4)))

299 
[[0], [1], [2], [3], [4], [5], [6], [7]]

300 

301 
Example

302 


303 
>>> # The auxiliary graph is primarilly used for kedgeccs but it

304 
>>> # can also speed up the queries of kedgesubgraphs by refining the

305 
>>> # search space.

306 
>>> import itertools as it

307 
>>> from networkx.utils import pairwise

308 
>>> from networkx.algorithms.connectivity import EdgeComponentAuxGraph

309 
>>> paths = [

310 
... (1, 2, 4, 3, 1, 4),

311 
... ]

312 
>>> G = nx.Graph()

313 
>>> G.add_nodes_from(it.chain(*paths))

314 
>>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))

315 
>>> aux_graph = EdgeComponentAuxGraph.construct(G)

316 
>>> sorted(map(sorted, aux_graph.k_edge_subgraphs(k=3)))

317 
[[1], [2], [3], [4]]

318 
>>> sorted(map(sorted, aux_graph.k_edge_components(k=3)))

319 
[[1, 4], [2], [3]]

320 
"""

321  
322 
# @not_implemented_for('multigraph') # TODO: fix decor for classmethods

323 
@classmethod

324 
def construct(EdgeComponentAuxGraph, G): 
325 
"""Builds an auxiliary graph encoding edgeconnectivity between nodes.

326 

327 
Notes

328 


329 
Given G=(V, E), initialize an empty auxiliary graph A.

330 
Choose an arbitrary source node s. Initialize a set N of available

331 
nodes (that can be used as the sink). The algorithm picks an

332 
arbitrary node t from N  {s}, and then computes the minimum stcut

333 
(S, T) with value w. If G is directed the the minimum of the stcut or

334 
the tscut is used instead. Then, the edge (s, t) is added to the

335 
auxiliary graph with weight w. The algorithm is called recursively

336 
first using S as the available nodes and s as the source, and then

337 
using T and t. Recursion stops when the source is the only available

338 
node.

339 

340 
Parameters

341 


342 
G : NetworkX graph

343 
"""

344 
# workaround for classmethod decorator

345 
not_implemented_for('multigraph')(lambda G: G)(G) 
346  
347 
def _recursive_build(H, A, source, avail): 
348 
# Terminate once the flow has been compute to every node.

349 
if {source} == avail:

350 
return

351 
# pick an arbitrary node as the sink

352 
sink = arbitrary_element(avail  {source}) 
353 
# find the minimum cut and its weight

354 
value, (S, T) = nx.minimum_cut(H, source, sink) 
355 
if H.is_directed():

356 
# check if the reverse direction has a smaller cut

357 
value_, (T_, S_) = nx.minimum_cut(H, sink, source) 
358 
if value_ < value:

359 
value, S, T = value_, S_, T_ 
360 
# add edge with weight of cut to the aux graph

361 
A.add_edge(source, sink, weight=value) 
362 
# recursively call until all but one node is used

363 
_recursive_build(H, A, source, avail.intersection(S)) 
364 
_recursive_build(H, A, sink, avail.intersection(T)) 
365  
366 
# Copy input to ensure all edges have unit capacity

367 
H = G.__class__() 
368 
H.add_nodes_from(G.nodes()) 
369 
H.add_edges_from(G.edges(), capacity=1)

370  
371 
# A is the auxiliary graph to be constructed

372 
# It is a weighted undirected tree

373 
A = nx.Graph() 
374  
375 
# Pick an arbitrary node as the source

376 
if H.number_of_nodes() > 0: 
377 
source = arbitrary_element(H.nodes()) 
378 
# Initialize a set of elements that can be chosen as the sink

379 
avail = set(H.nodes())

380  
381 
# This constructs A

382 
_recursive_build(H, A, source, avail) 
383  
384 
# This class is a container the holds the auxiliary graph A and

385 
# provides access the the k_edge_components function.

386 
self = EdgeComponentAuxGraph()

387 
self.A = A

388 
self.H = H

389 
return self 
390  
391 
def k_edge_components(self, k): 
392 
"""Queries the auxiliary graph for kedgeconnected components.

393 

394 
Parameters

395 


396 
k : Integer

397 
Desired edge connectivity

398 

399 
Returns

400 


401 
k_edge_components : a generator of kedgeccs

402 

403 
Notes

404 


405 
Given the auxiliary graph, the kedgeconnected components can be

406 
determined in linear time by removing all edges with weights less than

407 
k from the auxiliary graph. The resulting connected components are the

408 
kedgeccs in the original graph.

409 
"""

410 
if k < 1: 
411 
raise ValueError('k cannot be less than 1') 
412 
A = self.A

413 
# "traverse the auxiliary graph A and delete all edges with weights less

414 
# than k"

415 
aux_weights = nx.get_edge_attributes(A, 'weight')

416 
# Create a relevant graph with the auxiliary edges with weights >= k

417 
R = nx.Graph() 
418 
R.add_nodes_from(A.nodes()) 
419 
R.add_edges_from(e for e, w in aux_weights.items() if w >= k) 
420  
421 
# Return the nodes that are kedgeconnected in the original graph

422 
for cc in nx.connected_components(R): 
423 
yield cc

424  
425 
def k_edge_subgraphs(self, k): 
426 
"""Queries the auxiliary graph for kedgeconnected subgraphs.

427 

428 
Parameters

429 


430 
k : Integer

431 
Desired edge connectivity

432 

433 
Returns

434 


435 
k_edge_subgraphs : a generator of kedgesubgraphs

436 

437 
Notes

438 


439 
Refines the kedgeccs into kedgesubgraphs. The running time is more

440 
than $O(V)$.

441 

442 
For single values of k it is faster to use `nx.k_edge_subgraphs`.

443 
But for multiple values of k, it can be faster to build AuxGraph and

444 
then use this method.

445 
"""

446 
if k < 1: 
447 
raise ValueError('k cannot be less than 1') 
448 
H = self.H

449 
A = self.A

450 
# "traverse the auxiliary graph A and delete all edges with weights less

451 
# than k"

452 
aux_weights = nx.get_edge_attributes(A, 'weight')

453 
# Create a relevant graph with the auxiliary edges with weights >= k

454 
R = nx.Graph() 
455 
R.add_nodes_from(A.nodes()) 
456 
R.add_edges_from(e for e, w in aux_weights.items() if w >= k) 
457  
458 
# Return the components whose subgraphs are kedgeconnected

459 
for cc in nx.connected_components(R): 
460 
if len(cc) < k: 
461 
# Early return optimization

462 
for node in cc: 
463 
yield {node}

464 
else:

465 
# Call subgraph solution to refine the results

466 
C = H.subgraph(cc) 
467 
for sub_cc in k_edge_subgraphs(C, k): 
468 
yield sub_cc

469  
470  
471 
def _low_degree_nodes(G, k, nbunch=None): 
472 
"""Helper for finding nodes with degree less than k."""

473 
# Nodes with degree less than k cannot be kedgeconnected.

474 
if G.is_directed():

475 
# Consider both in and out degree in the directed case

476 
seen = set()

477 
for node, degree in G.out_degree(nbunch): 
478 
if degree < k:

479 
seen.add(node) 
480 
yield node

481 
for node, degree in G.in_degree(nbunch): 
482 
if node not in seen and degree < k: 
483 
seen.add(node) 
484 
yield node

485 
else:

486 
# Only the degree matters in the undirected case

487 
for node, degree in G.degree(nbunch): 
488 
if degree < k:

489 
yield node

490  
491  
492 
def _high_degree_components(G, k): 
493 
"""Helper for filtering components that can't be kedgeconnected.

494 

495 
Removes and generates each node with degree less than k. Then generates

496 
remaining components where all nodes have degree at least k.

497 
"""

498 
# Iteravely remove parts of the graph that are not kedgeconnected

499 
H = G.copy() 
500 
singletons = set(_low_degree_nodes(H, k))

501 
while singletons:

502 
# Only search neighbors of removed nodes

503 
nbunch = set(it.chain.from_iterable(map(H.neighbors, singletons))) 
504 
nbunch.difference_update(singletons) 
505 
H.remove_nodes_from(singletons) 
506 
for node in singletons: 
507 
yield {node}

508 
singletons = set(_low_degree_nodes(H, k, nbunch))

509  
510 
# Note: remaining connected components may not be kedgeconnected

511 
if G.is_directed():

512 
for cc in nx.strongly_connected_components(H): 
513 
yield cc

514 
else:

515 
for cc in nx.connected_components(H): 
516 
yield cc

517  
518  
519 
def general_k_edge_subgraphs(G, k): 
520 
"""General algorithm to find all maximal kedgeconnected subgraphs in G.

521 

522 
Returns

523 


524 
k_edge_subgraphs : a generator of nx.Graphs that are kedgesubgraphs

525 
Each kedgesubgraph is a maximal set of nodes that defines a subgraph

526 
of G that is kedgeconnected.

527 

528 
Notes

529 


530 
Implementation of the basic algorithm from _[1]. The basic idea is to find

531 
a global minimum cut of the graph. If the cut value is at least k, then the

532 
graph is a kedgeconnected subgraph and can be added to the results.

533 
Otherwise, the cut is used to split the graph in two and the procedure is

534 
applied recursively. If the graph is just a single node, then it is also

535 
added to the results. At the end, each result is either guaranteed to be

536 
a single node or a subgraph of G that is kedgeconnected.

537 

538 
This implementation contains optimizations for reducing the number of calls

539 
to maxflow, but there are other optimizations in _[1] that could be

540 
implemented.

541 

542 
References

543 


544 
.. [1] Zhou, Liu, et al. (2012) Finding maximal kedgeconnected subgraphs

545 
from a large graph. ACM International Conference on Extending Database

546 
Technology 2012 480–491.

547 
https://openproceedings.org/2012/conf/edbt/ZhouLYLCL12.pdf

548 

549 
Example

550 


551 
>>> from networkx.utils import pairwise

552 
>>> paths = [

553 
... (11, 12, 13, 14, 11, 13, 14, 12), # a 4clique

554 
... (21, 22, 23, 24, 21, 23, 24, 22), # another 4clique

555 
... # connect the cliques with high degree but low connectivity

556 
... (50, 13),

557 
... (12, 50, 22),

558 
... (13, 102, 23),

559 
... (14, 101, 24),

560 
... ]

561 
>>> G = nx.Graph(it.chain(*[pairwise(path) for path in paths]))

562 
>>> sorted(map(len, k_edge_subgraphs(G, k=3)))

563 
[1, 1, 1, 4, 4]

564 
"""

565 
if k < 1: 
566 
raise ValueError('k cannot be less than 1') 
567  
568 
# Node pruning optimization (incorporates early return)

569 
# find_ccs is either connected_components/strongly_connected_components

570 
find_ccs = partial(_high_degree_components, k=k) 
571  
572 
# Quick return optimization

573 
if G.number_of_nodes() < k:

574 
for node in G.nodes(): 
575 
yield G.subgraph([node]).copy()

576 
return

577  
578 
# Intermediate results

579 
R0 = {G.subgraph(cc).copy() for cc in find_ccs(G)} 
580 
# Subdivide CCs in the intermediate results until they are kconn

581 
while R0:

582 
G1 = R0.pop() 
583 
if G1.number_of_nodes() == 1: 
584 
yield G1

585 
else:

586 
# Find a global minimum cut

587 
cut_edges = nx.minimum_edge_cut(G1) 
588 
cut_value = len(cut_edges)

589 
if cut_value < k:

590 
# G1 is not kedgeconnected, so subdivide it

591 
G1.remove_edges_from(cut_edges) 
592 
for cc in find_ccs(G1): 
593 
R0.add(G1.subgraph(cc).copy()) 
594 
else:

595 
# Otherwise we found a kedgeconnected subgraph

596 
yield G1
