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