Shortcuts on this page
r m x toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
1"""
2Algorithms for finding k-edge-connected components and subgraphs.
4A k-edge-connected component (k-edge-cc) is a maximal set of nodes in G, such
5that all pairs of node have an edge-connectivity of at least k.
7A k-edge-connected subgraph (k-edge-subgraph) is a maximal set of nodes in G,
8such that the subgraph of G defined by the nodes has an edge-connectivity at
9least k.
10"""
12import itertools as it
13from functools import partial
15import networkx as nx
16from networkx.utils import arbitrary_element, not_implemented_for
18__all__ = [
19 "k_edge_components",
20 "k_edge_subgraphs",
21 "bridge_components",
22 "EdgeComponentAuxGraph",
23]
26@not_implemented_for("multigraph")
27@nx._dispatchable
28def k_edge_components(G, k):
29 """Generates nodes in each maximal k-edge-connected component in G.
31 Parameters
32 ----------
33 G : NetworkX graph
35 k : Integer
36 Desired edge connectivity
38 Returns
39 -------
40 k_edge_components : a generator of k-edge-ccs. Each set of returned nodes
41 will have k-edge-connectivity in the graph G.
43 See Also
44 --------
45 :func:`local_edge_connectivity`
46 :func:`k_edge_subgraphs` : similar to this function, but the subgraph
47 defined by the nodes must also have k-edge-connectivity.
48 :func:`k_components` : similar to this function, but uses node-connectivity
49 instead of edge-connectivity
51 Raises
52 ------
53 NetworkXNotImplemented
54 If the input graph is a multigraph.
56 ValueError:
57 If k is less than 1
59 Notes
60 -----
61 Attempts to use the most efficient implementation available based on k.
62 If k=1, this is simply connected components for directed graphs and
63 connected components for undirected graphs.
64 If k=2 on an efficient bridge connected component algorithm from _[1] is
65 run based on the chain decomposition.
66 Otherwise, the algorithm from _[2] is used.
68 Examples
69 --------
70 >>> import itertools as it
71 >>> from networkx.utils import pairwise
72 >>> paths = [
73 ... (1, 2, 4, 3, 1, 4),
74 ... (5, 6, 7, 8, 5, 7, 8, 6),
75 ... ]
76 >>> G = nx.Graph()
77 >>> G.add_nodes_from(it.chain(*paths))
78 >>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
79 >>> # note this returns {1, 4} unlike k_edge_subgraphs
80 >>> sorted(map(sorted, nx.k_edge_components(G, k=3)))
81 [[1, 4], [2], [3], [5, 6, 7, 8]]
83 References
84 ----------
85 .. [1] https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29
86 .. [2] Wang, Tianhao, et al. (2015) A simple algorithm for finding all
87 k-edge-connected components.
88 http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264
89 """
90 # Compute k-edge-ccs using the most efficient algorithms available.
91 if k < 1:
92 raise ValueError("k cannot be less than 1")
93 if G.is_directed():
94 if k == 1:
95 return nx.strongly_connected_components(G)
96 else:
97 # TODO: investigate https://arxiv.org/abs/1412.6466 for k=2
98 aux_graph = EdgeComponentAuxGraph.construct(G)
99 return aux_graph.k_edge_components(k)
100 else:
101 if k == 1:
102 return nx.connected_components(G)
103 elif k == 2:
104 return bridge_components(G)
105 else:
106 aux_graph = EdgeComponentAuxGraph.construct(G)
107 return aux_graph.k_edge_components(k)
110@not_implemented_for("multigraph")
111@nx._dispatchable
112def k_edge_subgraphs(G, k):
113 """Generates nodes in each maximal k-edge-connected subgraph in G.
115 Parameters
116 ----------
117 G : NetworkX graph
119 k : Integer
120 Desired edge connectivity
122 Returns
123 -------
124 k_edge_subgraphs : a generator of k-edge-subgraphs
125 Each k-edge-subgraph is a maximal set of nodes that defines a subgraph
126 of G that is k-edge-connected.
128 See Also
129 --------
130 :func:`edge_connectivity`
131 :func:`k_edge_components` : similar to this function, but nodes only
132 need to have k-edge-connectivity within the graph G and the subgraphs
133 might not be k-edge-connected.
135 Raises
136 ------
137 NetworkXNotImplemented
138 If the input graph is a multigraph.
140 ValueError:
141 If k is less than 1
143 Notes
144 -----
145 Attempts to use the most efficient implementation available based on k.
146 If k=1, or k=2 and the graph is undirected, then this simply calls
147 `k_edge_components`. Otherwise the algorithm from _[1] is used.
149 Examples
150 --------
151 >>> import itertools as it
152 >>> from networkx.utils import pairwise
153 >>> paths = [
154 ... (1, 2, 4, 3, 1, 4),
155 ... (5, 6, 7, 8, 5, 7, 8, 6),
156 ... ]
157 >>> G = nx.Graph()
158 >>> G.add_nodes_from(it.chain(*paths))
159 >>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
160 >>> # note this does not return {1, 4} unlike k_edge_components
161 >>> sorted(map(sorted, nx.k_edge_subgraphs(G, k=3)))
162 [[1], [2], [3], [4], [5, 6, 7, 8]]
164 References
165 ----------
166 .. [1] Zhou, Liu, et al. (2012) Finding maximal k-edge-connected subgraphs
167 from a large graph. ACM International Conference on Extending Database
168 Technology 2012 480-–491.
169 https://openproceedings.org/2012/conf/edbt/ZhouLYLCL12.pdf
170 """
171 if k < 1:
172 raise ValueError("k cannot be less than 1")
173 if G.is_directed():
174 if k <= 1:
175 # For directed graphs ,
176 # When k == 1, k-edge-ccs and k-edge-subgraphs are the same
177 return k_edge_components(G, k)
178 else:
179 return _k_edge_subgraphs_nodes(G, k)
180 else:
181 if k <= 2:
182 # For undirected graphs,
183 # when k <= 2, k-edge-ccs and k-edge-subgraphs are the same
184 return k_edge_components(G, k)
185 else:
186 return _k_edge_subgraphs_nodes(G, k)
189def _k_edge_subgraphs_nodes(G, k):
190 """Helper to get the nodes from the subgraphs.
192 This allows k_edge_subgraphs to return a generator.
193 """
194 for C in general_k_edge_subgraphs(G, k):
195 yield set(C.nodes())
198@not_implemented_for("directed")
199@not_implemented_for("multigraph")
200@nx._dispatchable
201def bridge_components(G):
202 """Finds all bridge-connected components G.
204 Parameters
205 ----------
206 G : NetworkX undirected graph
208 Returns
209 -------
210 bridge_components : a generator of 2-edge-connected components
213 See Also
214 --------
215 :func:`k_edge_subgraphs` : this function is a special case for an
216 undirected graph where k=2.
217 :func:`biconnected_components` : similar to this function, but is defined
218 using 2-node-connectivity instead of 2-edge-connectivity.
220 Raises
221 ------
222 NetworkXNotImplemented
223 If the input graph is directed or a multigraph.
225 Notes
226 -----
227 Bridge-connected components are also known as 2-edge-connected components.
229 Examples
230 --------
231 >>> # The barbell graph with parameter zero has a single bridge
232 >>> G = nx.barbell_graph(5, 0)
233 >>> from networkx.algorithms.connectivity.edge_kcomponents import bridge_components
234 >>> sorted(map(sorted, bridge_components(G)))
235 [[0, 1, 2, 3, 4], [5, 6, 7, 8, 9]]
236 """
237 H = G.copy()
238 H.remove_edges_from(nx.bridges(G))
239 yield from nx.connected_components(H)
242class EdgeComponentAuxGraph:
243 r"""A simple algorithm to find all k-edge-connected components in a graph.
245 Constructing the auxiliary graph (which may take some time) allows for the
246 k-edge-ccs to be found in linear time for arbitrary k.
248 Notes
249 -----
250 This implementation is based on [1]_. The idea is to construct an auxiliary
251 graph from which the k-edge-ccs can be extracted in linear time. The
252 auxiliary graph is constructed in $O(|V|\cdot F)$ operations, where F is the
253 complexity of max flow. Querying the components takes an additional $O(|V|)$
254 operations. This algorithm can be slow for large graphs, but it handles an
255 arbitrary k and works for both directed and undirected inputs.
257 The undirected case for k=1 is exactly connected components.
258 The undirected case for k=2 is exactly bridge connected components.
259 The directed case for k=1 is exactly strongly connected components.
261 References
262 ----------
263 .. [1] Wang, Tianhao, et al. (2015) A simple algorithm for finding all
264 k-edge-connected components.
265 http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264
267 Examples
268 --------
269 >>> import itertools as it
270 >>> from networkx.utils import pairwise
271 >>> from networkx.algorithms.connectivity import EdgeComponentAuxGraph
272 >>> # Build an interesting graph with multiple levels of k-edge-ccs
273 >>> paths = [
274 ... (1, 2, 3, 4, 1, 3, 4, 2), # a 3-edge-cc (a 4 clique)
275 ... (5, 6, 7, 5), # a 2-edge-cc (a 3 clique)
276 ... (1, 5), # combine first two ccs into a 1-edge-cc
277 ... (0,), # add an additional disconnected 1-edge-cc
278 ... ]
279 >>> G = nx.Graph()
280 >>> G.add_nodes_from(it.chain(*paths))
281 >>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
282 >>> # Constructing the AuxGraph takes about O(n ** 4)
283 >>> aux_graph = EdgeComponentAuxGraph.construct(G)
284 >>> # Once constructed, querying takes O(n)
285 >>> sorted(map(sorted, aux_graph.k_edge_components(k=1)))
286 [[0], [1, 2, 3, 4, 5, 6, 7]]
287 >>> sorted(map(sorted, aux_graph.k_edge_components(k=2)))
288 [[0], [1, 2, 3, 4], [5, 6, 7]]
289 >>> sorted(map(sorted, aux_graph.k_edge_components(k=3)))
290 [[0], [1, 2, 3, 4], [5], [6], [7]]
291 >>> sorted(map(sorted, aux_graph.k_edge_components(k=4)))
292 [[0], [1], [2], [3], [4], [5], [6], [7]]
294 The auxiliary graph is primarily used for k-edge-ccs but it
295 can also speed up the queries of k-edge-subgraphs by refining the
296 search space.
298 >>> import itertools as it
299 >>> from networkx.utils import pairwise
300 >>> from networkx.algorithms.connectivity import EdgeComponentAuxGraph
301 >>> paths = [
302 ... (1, 2, 4, 3, 1, 4),
303 ... ]
304 >>> G = nx.Graph()
305 >>> G.add_nodes_from(it.chain(*paths))
306 >>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths]))
307 >>> aux_graph = EdgeComponentAuxGraph.construct(G)
308 >>> sorted(map(sorted, aux_graph.k_edge_subgraphs(k=3)))
309 [[1], [2], [3], [4]]
310 >>> sorted(map(sorted, aux_graph.k_edge_components(k=3)))
311 [[1, 4], [2], [3]]
312 """
314 # @not_implemented_for('multigraph') # TODO: fix decor for classmethods
315 @classmethod
316 def construct(EdgeComponentAuxGraph, G):
317 """Builds an auxiliary graph encoding edge-connectivity between nodes.
319 Notes
320 -----
321 Given G=(V, E), initialize an empty auxiliary graph A.
322 Choose an arbitrary source node s. Initialize a set N of available
323 nodes (that can be used as the sink). The algorithm picks an
324 arbitrary node t from N - {s}, and then computes the minimum st-cut
325 (S, T) with value w. If G is directed the minimum of the st-cut or
326 the ts-cut is used instead. Then, the edge (s, t) is added to the
327 auxiliary graph with weight w. The algorithm is called recursively
328 first using S as the available nodes and s as the source, and then
329 using T and t. Recursion stops when the source is the only available
330 node.
332 Parameters
333 ----------
334 G : NetworkX graph
335 """
336 # workaround for classmethod decorator
337 not_implemented_for("multigraph")(lambda G: G)(G)
339 def _recursive_build(H, A, source, avail):
340 # Terminate once the flow has been compute to every node.
341 if {source} == avail:
342 return
343 # pick an arbitrary node as the sink
344 sink = arbitrary_element(avail - {source})
345 # find the minimum cut and its weight
346 value, (S, T) = nx.minimum_cut(H, source, sink)
347 if H.is_directed():
348 # check if the reverse direction has a smaller cut
349 value_, (T_, S_) = nx.minimum_cut(H, sink, source)
350 if value_ < value:
351 value, S, T = value_, S_, T_
352 # add edge with weight of cut to the aux graph
353 A.add_edge(source, sink, weight=value)
354 # recursively call until all but one node is used
355 _recursive_build(H, A, source, avail.intersection(S))
356 _recursive_build(H, A, sink, avail.intersection(T))
358 # Copy input to ensure all edges have unit capacity
359 H = G.__class__()
360 H.add_nodes_from(G.nodes())
361 H.add_edges_from(G.edges(), capacity=1)
363 # A is the auxiliary graph to be constructed
364 # It is a weighted undirected tree
365 A = nx.Graph()
367 # Pick an arbitrary node as the source
368 if H.number_of_nodes() > 0:
369 source = arbitrary_element(H.nodes())
370 # Initialize a set of elements that can be chosen as the sink
371 avail = set(H.nodes())
373 # This constructs A
374 _recursive_build(H, A, source, avail)
376 # This class is a container the holds the auxiliary graph A and
377 # provides access the k_edge_components function.
378 self = EdgeComponentAuxGraph()
379 self.A = A
380 self.H = H
381 return self
383 def k_edge_components(self, k):
384 """Queries the auxiliary graph for k-edge-connected components.
386 Parameters
387 ----------
388 k : Integer
389 Desired edge connectivity
391 Returns
392 -------
393 k_edge_components : a generator of k-edge-ccs
395 Notes
396 -----
397 Given the auxiliary graph, the k-edge-connected components can be
398 determined in linear time by removing all edges with weights less than
399 k from the auxiliary graph. The resulting connected components are the
400 k-edge-ccs in the original graph.
401 """
402 if k < 1:
403 raise ValueError("k cannot be less than 1")
404 A = self.A
405 # "traverse the auxiliary graph A and delete all edges with weights less
406 # than k"
407 aux_weights = nx.get_edge_attributes(A, "weight")
408 # Create a relevant graph with the auxiliary edges with weights >= k
409 R = nx.Graph()
410 R.add_nodes_from(A.nodes())
411 R.add_edges_from(e for e, w in aux_weights.items() if w >= k)
413 # Return the nodes that are k-edge-connected in the original graph
414 yield from nx.connected_components(R)
416 def k_edge_subgraphs(self, k):
417 """Queries the auxiliary graph for k-edge-connected subgraphs.
419 Parameters
420 ----------
421 k : Integer
422 Desired edge connectivity
424 Returns
425 -------
426 k_edge_subgraphs : a generator of k-edge-subgraphs
428 Notes
429 -----
430 Refines the k-edge-ccs into k-edge-subgraphs. The running time is more
431 than $O(|V|)$.
433 For single values of k it is faster to use `nx.k_edge_subgraphs`.
434 But for multiple values of k, it can be faster to build AuxGraph and
435 then use this method.
436 """
437 if k < 1:
438 raise ValueError("k cannot be less than 1")
439 H = self.H
440 A = self.A
441 # "traverse the auxiliary graph A and delete all edges with weights less
442 # than k"
443 aux_weights = nx.get_edge_attributes(A, "weight")
444 # Create a relevant graph with the auxiliary edges with weights >= k
445 R = nx.Graph()
446 R.add_nodes_from(A.nodes())
447 R.add_edges_from(e for e, w in aux_weights.items() if w >= k)
449 # Return the components whose subgraphs are k-edge-connected
450 for cc in nx.connected_components(R):
451 if len(cc) < k:
452 # Early return optimization
453 for node in cc:
454 yield {node}
455 else:
456 # Call subgraph solution to refine the results
457 C = H.subgraph(cc)
458 yield from k_edge_subgraphs(C, k)
461def _low_degree_nodes(G, k, nbunch=None):
462 """Helper for finding nodes with degree less than k."""
463 # Nodes with degree less than k cannot be k-edge-connected.
464 if G.is_directed():
465 # Consider both in and out degree in the directed case
466 seen = set()
467 for node, degree in G.out_degree(nbunch):
468 if degree < k:
469 seen.add(node)
470 yield node
471 for node, degree in G.in_degree(nbunch):
472 if node not in seen and degree < k:
473 seen.add(node)
474 yield node
475 else:
476 # Only the degree matters in the undirected case
477 for node, degree in G.degree(nbunch):
478 if degree < k:
479 yield node
482def _high_degree_components(G, k):
483 """Helper for filtering components that can't be k-edge-connected.
485 Removes and generates each node with degree less than k. Then generates
486 remaining components where all nodes have degree at least k.
487 """
488 # Iteratively remove parts of the graph that are not k-edge-connected
489 H = G.copy()
490 singletons = set(_low_degree_nodes(H, k))
491 while singletons:
492 # Only search neighbors of removed nodes
493 nbunch = set(it.chain.from_iterable(map(H.neighbors, singletons)))
494 nbunch.difference_update(singletons)
495 H.remove_nodes_from(singletons)
496 for node in singletons:
497 yield {node}
498 singletons = set(_low_degree_nodes(H, k, nbunch))
500 # Note: remaining connected components may not be k-edge-connected
501 if G.is_directed():
502 yield from nx.strongly_connected_components(H)
503 else:
504 yield from nx.connected_components(H)
507@nx._dispatchable(returns_graph=True)
508def general_k_edge_subgraphs(G, k):
509 """General algorithm to find all maximal k-edge-connected subgraphs in `G`.
511 Parameters
512 ----------
513 G : nx.Graph
514 Graph in which all maximal k-edge-connected subgraphs will be found.
516 k : int
518 Yields
519 ------
520 k_edge_subgraphs : Graph instances that are k-edge-subgraphs
521 Each k-edge-subgraph contains a maximal set of nodes that defines a
522 subgraph of `G` that is k-edge-connected.
524 Notes
525 -----
526 Implementation of the basic algorithm from [1]_. The basic idea is to find
527 a global minimum cut of the graph. If the cut value is at least k, then the
528 graph is a k-edge-connected subgraph and can be added to the results.
529 Otherwise, the cut is used to split the graph in two and the procedure is
530 applied recursively. If the graph is just a single node, then it is also
531 added to the results. At the end, each result is either guaranteed to be
532 a single node or a subgraph of G that is k-edge-connected.
534 This implementation contains optimizations for reducing the number of calls
535 to max-flow, but there are other optimizations in [1]_ that could be
536 implemented.
538 References
539 ----------
540 .. [1] Zhou, Liu, et al. (2012) Finding maximal k-edge-connected subgraphs
541 from a large graph. ACM International Conference on Extending Database
542 Technology 2012 480-–491.
543 https://openproceedings.org/2012/conf/edbt/ZhouLYLCL12.pdf
545 Examples
546 --------
547 >>> from networkx.utils import pairwise
548 >>> paths = [
549 ... (11, 12, 13, 14, 11, 13, 14, 12), # a 4-clique
550 ... (21, 22, 23, 24, 21, 23, 24, 22), # another 4-clique
551 ... # connect the cliques with high degree but low connectivity
552 ... (50, 13),
553 ... (12, 50, 22),
554 ... (13, 102, 23),
555 ... (14, 101, 24),
556 ... ]
557 >>> G = nx.Graph(it.chain(*[pairwise(path) for path in paths]))
558 >>> sorted(len(k_sg) for k_sg in k_edge_subgraphs(G, k=3))
559 [1, 1, 1, 4, 4]
560 """
561 if k < 1:
562 raise ValueError("k cannot be less than 1")
564 # Node pruning optimization (incorporates early return)
565 # find_ccs is either connected_components/strongly_connected_components
566 find_ccs = partial(_high_degree_components, k=k)
568 # Quick return optimization
569 if G.number_of_nodes() < k:
570 for node in G.nodes():
571 yield G.subgraph([node]).copy()
572 return
574 # Intermediate results
575 R0 = {G.subgraph(cc).copy() for cc in find_ccs(G)}
576 # Subdivide CCs in the intermediate results until they are k-conn
577 while R0:
578 G1 = R0.pop()
579 if G1.number_of_nodes() == 1:
580 yield G1
581 else:
582 # Find a global minimum cut
583 cut_edges = nx.minimum_edge_cut(G1)
584 cut_value = len(cut_edges)
585 if cut_value < k:
586 # G1 is not k-edge-connected, so subdivide it
587 G1.remove_edges_from(cut_edges)
588 for cc in find_ccs(G1):
589 R0.add(G1.subgraph(cc).copy())
590 else:
591 # Otherwise we found a k-edge-connected subgraph
592 yield G1