Statistics
| Branch: | Revision:

## iof-tools / networkxMiCe / networkx-master / networkx / algorithms / connectivity / edge_kcomponents.py @ 5cef0f13

 1 ```# -*- coding: utf-8 -*- ``` ```# Copyright (C) 2004-2019 by ``` ```# Aric Hagberg ``` ```# Dan Schult ``` ```# Pieter Swart ``` ```# All rights reserved. ``` ```# BSD license. ``` ```# ``` ```# Authors: Jon Crall (erotemic@gmail.com) ``` ```""" ``` ```Algorithms for finding k-edge-connected components and subgraphs. ``` ``` ``` ```A k-edge-connected component (k-edge-cc) is a maximal set of nodes in G, such ``` ```that all pairs of node have an edge-connectivity of at least k. ``` ``` ``` ```A k-edge-connected subgraph (k-edge-subgraph) is a maximal set of nodes in G, ``` ```such that the subgraph of G defined by the nodes has an edge-connectivity at ``` ```least k. ``` ```""" ``` ```import networkx as nx ``` ```from networkx.utils import arbitrary_element ``` ```from networkx.utils import not_implemented_for ``` ```from networkx.algorithms import bridges ``` ```from functools import partial ``` ```import itertools as it ``` ```__all__ = [ ``` ``` 'k_edge_components', ``` ``` 'k_edge_subgraphs', ``` ``` 'bridge_components', ``` ``` 'EdgeComponentAuxGraph', ``` ```] ``` ```@not_implemented_for('multigraph') ``` ```def k_edge_components(G, k): ``` ``` """Generates nodes in each maximal k-edge-connected component in G. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` ``` ``` k : Integer ``` ``` Desired edge connectivity ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` k_edge_components : a generator of k-edge-ccs. Each set of returned nodes ``` ``` will have k-edge-connectivity in the graph G. ``` ``` ``` ``` See Also ``` ``` ------- ``` ``` :func:`local_edge_connectivity` ``` ``` :func:`k_edge_subgraphs` : similar to this function, but the subgraph ``` ``` defined by the nodes must also have k-edge-connectivity. ``` ``` :func:`k_components` : similar to this function, but uses node-connectivity ``` ``` instead of edge-connectivity ``` ``` ``` ``` Raises ``` ``` ------ ``` ``` NetworkXNotImplemented: ``` ``` If the input graph is a multigraph. ``` ``` ``` ``` ValueError: ``` ``` If k is less than 1 ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` Attempts to use the most efficient implementation available based on k. ``` ``` If k=1, this is simply simply connected components for directed graphs and ``` ``` connected components for undirected graphs. ``` ``` If k=2 on an efficient bridge connected component algorithm from _ is ``` ``` run based on the chain decomposition. ``` ``` Otherwise, the algorithm from _ is used. ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> import itertools as it ``` ``` >>> from networkx.utils import pairwise ``` ``` >>> paths = [ ``` ``` ... (1, 2, 4, 3, 1, 4), ``` ``` ... (5, 6, 7, 8, 5, 7, 8, 6), ``` ``` ... ] ``` ``` >>> G = nx.Graph() ``` ``` >>> G.add_nodes_from(it.chain(*paths)) ``` ``` >>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths])) ``` ``` >>> # note this returns {1, 4} unlike k_edge_subgraphs ``` ``` >>> sorted(map(sorted, nx.k_edge_components(G, k=3))) ``` ``` [[1, 4], , , [5, 6, 7, 8]] ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  https://en.wikipedia.org/wiki/Bridge_%28graph_theory%29 ``` ``` ..  Wang, Tianhao, et al. (2015) A simple algorithm for finding all ``` ``` k-edge-connected components. ``` ``` http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264 ``` ``` """ ``` ``` # Compute k-edge-ccs using the most efficient algorithms available. ``` ``` if k < 1: ``` ``` raise ValueError('k cannot be less than 1') ``` ``` if G.is_directed(): ``` ``` if k == 1: ``` ``` return nx.strongly_connected_components(G) ``` ``` else: ``` ``` # TODO: investigate https://arxiv.org/abs/1412.6466 for k=2 ``` ``` aux_graph = EdgeComponentAuxGraph.construct(G) ``` ``` return aux_graph.k_edge_components(k) ``` ``` else: ``` ``` if k == 1: ``` ``` return nx.connected_components(G) ``` ``` elif k == 2: ``` ``` return bridge_components(G) ``` ``` else: ``` ``` aux_graph = EdgeComponentAuxGraph.construct(G) ``` ``` return aux_graph.k_edge_components(k) ``` ```@not_implemented_for('multigraph') ``` ```def k_edge_subgraphs(G, k): ``` ``` """Generates nodes in each maximal k-edge-connected subgraph in G. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` ``` ``` k : Integer ``` ``` Desired edge connectivity ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` k_edge_subgraphs : a generator of k-edge-subgraphs ``` ``` Each k-edge-subgraph is a maximal set of nodes that defines a subgraph ``` ``` of G that is k-edge-connected. ``` ``` ``` ``` See Also ``` ``` ------- ``` ``` :func:`edge_connectivity` ``` ``` :func:`k_edge_components` : similar to this function, but nodes only ``` ``` need to have k-edge-connctivity within the graph G and the subgraphs ``` ``` might not be k-edge-connected. ``` ``` ``` ``` Raises ``` ``` ------ ``` ``` NetworkXNotImplemented: ``` ``` If the input graph is a multigraph. ``` ``` ``` ``` ValueError: ``` ``` If k is less than 1 ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` Attempts to use the most efficient implementation available based on k. ``` ``` If k=1, or k=2 and the graph is undirected, then this simply calls ``` ``` `k_edge_components`. Otherwise the algorithm from _ is used. ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> import itertools as it ``` ``` >>> from networkx.utils import pairwise ``` ``` >>> paths = [ ``` ``` ... (1, 2, 4, 3, 1, 4), ``` ``` ... (5, 6, 7, 8, 5, 7, 8, 6), ``` ``` ... ] ``` ``` >>> G = nx.Graph() ``` ``` >>> G.add_nodes_from(it.chain(*paths)) ``` ``` >>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths])) ``` ``` >>> # note this does not return {1, 4} unlike k_edge_components ``` ``` >>> sorted(map(sorted, nx.k_edge_subgraphs(G, k=3))) ``` ``` [, , , , [5, 6, 7, 8]] ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  Zhou, Liu, et al. (2012) Finding maximal k-edge-connected subgraphs ``` ``` from a large graph. ACM International Conference on Extending Database ``` ``` Technology 2012 480-–491. ``` ``` https://openproceedings.org/2012/conf/edbt/ZhouLYLCL12.pdf ``` ``` """ ``` ``` if k < 1: ``` ``` raise ValueError('k cannot be less than 1') ``` ``` if G.is_directed(): ``` ``` if k <= 1: ``` ``` # For directed graphs , ``` ``` # When k == 1, k-edge-ccs and k-edge-subgraphs are the same ``` ``` return k_edge_components(G, k) ``` ``` else: ``` ``` return _k_edge_subgraphs_nodes(G, k) ``` ``` else: ``` ``` if k <= 2: ``` ``` # For undirected graphs, ``` ``` # when k <= 2, k-edge-ccs and k-edge-subgraphs are the same ``` ``` return k_edge_components(G, k) ``` ``` else: ``` ``` return _k_edge_subgraphs_nodes(G, k) ``` ```def _k_edge_subgraphs_nodes(G, k): ``` ``` """Helper to get the nodes from the subgraphs. ``` ``` ``` ``` This allows k_edge_subgraphs to return a generator. ``` ``` """ ``` ``` for C in general_k_edge_subgraphs(G, k): ``` ``` yield set(C.nodes()) ``` ```@not_implemented_for('directed') ``` ```@not_implemented_for('multigraph') ``` ```def bridge_components(G): ``` ``` """Finds all bridge-connected components G. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX undirected graph ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` bridge_components : a generator of 2-edge-connected components ``` ``` ``` ``` ``` ``` See Also ``` ``` -------- ``` ``` :func:`k_edge_subgraphs` : this function is a special case for an ``` ``` undirected graph where k=2. ``` ``` :func:`biconnected_components` : similar to this function, but is defined ``` ``` using 2-node-connectivity instead of 2-edge-connectivity. ``` ``` ``` ``` Raises ``` ``` ------ ``` ``` NetworkXNotImplemented: ``` ``` If the input graph is directed or a multigraph. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` Bridge-connected components are also known as 2-edge-connected components. ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> # The barbell graph with parameter zero has a single bridge ``` ``` >>> G = nx.barbell_graph(5, 0) ``` ``` >>> from networkx.algorithms.connectivity.edge_kcomponents import bridge_components ``` ``` >>> sorted(map(sorted, bridge_components(G))) ``` ``` [[0, 1, 2, 3, 4], [5, 6, 7, 8, 9]] ``` ``` """ ``` ``` H = G.copy() ``` ``` H.remove_edges_from(bridges(G)) ``` ``` for cc in nx.connected_components(H): ``` ``` yield cc ``` ```class EdgeComponentAuxGraph(object): ``` ``` r"""A simple algorithm to find all k-edge-connected components in a graph. ``` ``` ``` ``` Constructing the AuxillaryGraph (which may take some time) allows for the ``` ``` k-edge-ccs to be found in linear time for arbitrary k. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` This implementation is based on _. The idea is to construct an auxiliary ``` ``` graph from which the k-edge-ccs can be extracted in linear time. The ``` ``` auxiliary graph is constructed in \$O(|V|\cdot F)\$ operations, where F is the ``` ``` complexity of max flow. Querying the components takes an additional \$O(|V|)\$ ``` ``` operations. This algorithm can be slow for large graphs, but it handles an ``` ``` arbitrary k and works for both directed and undirected inputs. ``` ``` ``` ``` The undirected case for k=1 is exactly connected components. ``` ``` The undirected case for k=2 is exactly bridge connected components. ``` ``` The directed case for k=1 is exactly strongly connected components. ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  Wang, Tianhao, et al. (2015) A simple algorithm for finding all ``` ``` k-edge-connected components. ``` ``` http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0136264 ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> import itertools as it ``` ``` >>> from networkx.utils import pairwise ``` ``` >>> from networkx.algorithms.connectivity import EdgeComponentAuxGraph ``` ``` >>> # Build an interesting graph with multiple levels of k-edge-ccs ``` ``` >>> paths = [ ``` ``` ... (1, 2, 3, 4, 1, 3, 4, 2), # a 3-edge-cc (a 4 clique) ``` ``` ... (5, 6, 7, 5), # a 2-edge-cc (a 3 clique) ``` ``` ... (1, 5), # combine first two ccs into a 1-edge-cc ``` ``` ... (0,), # add an additional disconnected 1-edge-cc ``` ``` ... ] ``` ``` >>> G = nx.Graph() ``` ``` >>> G.add_nodes_from(it.chain(*paths)) ``` ``` >>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths])) ``` ``` >>> # Constructing the AuxGraph takes about O(n ** 4) ``` ``` >>> aux_graph = EdgeComponentAuxGraph.construct(G) ``` ``` >>> # Once constructed, querying takes O(n) ``` ``` >>> sorted(map(sorted, aux_graph.k_edge_components(k=1))) ``` ``` [, [1, 2, 3, 4, 5, 6, 7]] ``` ``` >>> sorted(map(sorted, aux_graph.k_edge_components(k=2))) ``` ``` [, [1, 2, 3, 4], [5, 6, 7]] ``` ``` >>> sorted(map(sorted, aux_graph.k_edge_components(k=3))) ``` ``` [, [1, 2, 3, 4], , , ] ``` ``` >>> sorted(map(sorted, aux_graph.k_edge_components(k=4))) ``` ``` [, , , , , , , ] ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> # The auxiliary graph is primarilly used for k-edge-ccs but it ``` ``` >>> # can also speed up the queries of k-edge-subgraphs by refining the ``` ``` >>> # search space. ``` ``` >>> import itertools as it ``` ``` >>> from networkx.utils import pairwise ``` ``` >>> from networkx.algorithms.connectivity import EdgeComponentAuxGraph ``` ``` >>> paths = [ ``` ``` ... (1, 2, 4, 3, 1, 4), ``` ``` ... ] ``` ``` >>> G = nx.Graph() ``` ``` >>> G.add_nodes_from(it.chain(*paths)) ``` ``` >>> G.add_edges_from(it.chain(*[pairwise(path) for path in paths])) ``` ``` >>> aux_graph = EdgeComponentAuxGraph.construct(G) ``` ``` >>> sorted(map(sorted, aux_graph.k_edge_subgraphs(k=3))) ``` ``` [, , , ] ``` ``` >>> sorted(map(sorted, aux_graph.k_edge_components(k=3))) ``` ``` [[1, 4], , ] ``` ``` """ ``` ``` # @not_implemented_for('multigraph') # TODO: fix decor for classmethods ``` ``` @classmethod ``` ``` def construct(EdgeComponentAuxGraph, G): ``` ``` """Builds an auxiliary graph encoding edge-connectivity between nodes. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` Given G=(V, E), initialize an empty auxiliary graph A. ``` ``` Choose an arbitrary source node s. Initialize a set N of available ``` ``` nodes (that can be used as the sink). The algorithm picks an ``` ``` arbitrary node t from N - {s}, and then computes the minimum st-cut ``` ``` (S, T) with value w. If G is directed the the minimum of the st-cut or ``` ``` the ts-cut is used instead. Then, the edge (s, t) is added to the ``` ``` auxiliary graph with weight w. The algorithm is called recursively ``` ``` first using S as the available nodes and s as the source, and then ``` ``` using T and t. Recursion stops when the source is the only available ``` ``` node. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX graph ``` ``` """ ``` ``` # workaround for classmethod decorator ``` ``` not_implemented_for('multigraph')(lambda G: G)(G) ``` ``` def _recursive_build(H, A, source, avail): ``` ``` # Terminate once the flow has been compute to every node. ``` ``` if {source} == avail: ``` ``` return ``` ``` # pick an arbitrary node as the sink ``` ``` sink = arbitrary_element(avail - {source}) ``` ``` # find the minimum cut and its weight ``` ``` value, (S, T) = nx.minimum_cut(H, source, sink) ``` ``` if H.is_directed(): ``` ``` # check if the reverse direction has a smaller cut ``` ``` value_, (T_, S_) = nx.minimum_cut(H, sink, source) ``` ``` if value_ < value: ``` ``` value, S, T = value_, S_, T_ ``` ``` # add edge with weight of cut to the aux graph ``` ``` A.add_edge(source, sink, weight=value) ``` ``` # recursively call until all but one node is used ``` ``` _recursive_build(H, A, source, avail.intersection(S)) ``` ``` _recursive_build(H, A, sink, avail.intersection(T)) ``` ``` # Copy input to ensure all edges have unit capacity ``` ``` H = G.__class__() ``` ``` H.add_nodes_from(G.nodes()) ``` ``` H.add_edges_from(G.edges(), capacity=1) ``` ``` # A is the auxiliary graph to be constructed ``` ``` # It is a weighted undirected tree ``` ``` A = nx.Graph() ``` ``` # Pick an arbitrary node as the source ``` ``` if H.number_of_nodes() > 0: ``` ``` source = arbitrary_element(H.nodes()) ``` ``` # Initialize a set of elements that can be chosen as the sink ``` ``` avail = set(H.nodes()) ``` ``` # This constructs A ``` ``` _recursive_build(H, A, source, avail) ``` ``` # This class is a container the holds the auxiliary graph A and ``` ``` # provides access the the k_edge_components function. ``` ``` self = EdgeComponentAuxGraph() ``` ``` self.A = A ``` ``` self.H = H ``` ``` return self ``` ``` def k_edge_components(self, k): ``` ``` """Queries the auxiliary graph for k-edge-connected components. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` k : Integer ``` ``` Desired edge connectivity ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` k_edge_components : a generator of k-edge-ccs ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` Given the auxiliary graph, the k-edge-connected components can be ``` ``` determined in linear time by removing all edges with weights less than ``` ``` k from the auxiliary graph. The resulting connected components are the ``` ``` k-edge-ccs in the original graph. ``` ``` """ ``` ``` if k < 1: ``` ``` raise ValueError('k cannot be less than 1') ``` ``` A = self.A ``` ``` # "traverse the auxiliary graph A and delete all edges with weights less ``` ``` # than k" ``` ``` aux_weights = nx.get_edge_attributes(A, 'weight') ``` ``` # Create a relevant graph with the auxiliary edges with weights >= k ``` ``` R = nx.Graph() ``` ``` R.add_nodes_from(A.nodes()) ``` ``` R.add_edges_from(e for e, w in aux_weights.items() if w >= k) ``` ``` # Return the nodes that are k-edge-connected in the original graph ``` ``` for cc in nx.connected_components(R): ``` ``` yield cc ``` ``` def k_edge_subgraphs(self, k): ``` ``` """Queries the auxiliary graph for k-edge-connected subgraphs. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` k : Integer ``` ``` Desired edge connectivity ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` k_edge_subgraphs : a generator of k-edge-subgraphs ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` Refines the k-edge-ccs into k-edge-subgraphs. The running time is more ``` ``` than \$O(|V|)\$. ``` ``` ``` ``` For single values of k it is faster to use `nx.k_edge_subgraphs`. ``` ``` But for multiple values of k, it can be faster to build AuxGraph and ``` ``` then use this method. ``` ``` """ ``` ``` if k < 1: ``` ``` raise ValueError('k cannot be less than 1') ``` ``` H = self.H ``` ``` A = self.A ``` ``` # "traverse the auxiliary graph A and delete all edges with weights less ``` ``` # than k" ``` ``` aux_weights = nx.get_edge_attributes(A, 'weight') ``` ``` # Create a relevant graph with the auxiliary edges with weights >= k ``` ``` R = nx.Graph() ``` ``` R.add_nodes_from(A.nodes()) ``` ``` R.add_edges_from(e for e, w in aux_weights.items() if w >= k) ``` ``` # Return the components whose subgraphs are k-edge-connected ``` ``` for cc in nx.connected_components(R): ``` ``` if len(cc) < k: ``` ``` # Early return optimization ``` ``` for node in cc: ``` ``` yield {node} ``` ``` else: ``` ``` # Call subgraph solution to refine the results ``` ``` C = H.subgraph(cc) ``` ``` for sub_cc in k_edge_subgraphs(C, k): ``` ``` yield sub_cc ``` ```def _low_degree_nodes(G, k, nbunch=None): ``` ``` """Helper for finding nodes with degree less than k.""" ``` ``` # Nodes with degree less than k cannot be k-edge-connected. ``` ``` if G.is_directed(): ``` ``` # Consider both in and out degree in the directed case ``` ``` seen = set() ``` ``` for node, degree in G.out_degree(nbunch): ``` ``` if degree < k: ``` ``` seen.add(node) ``` ``` yield node ``` ``` for node, degree in G.in_degree(nbunch): ``` ``` if node not in seen and degree < k: ``` ``` seen.add(node) ``` ``` yield node ``` ``` else: ``` ``` # Only the degree matters in the undirected case ``` ``` for node, degree in G.degree(nbunch): ``` ``` if degree < k: ``` ``` yield node ``` ```def _high_degree_components(G, k): ``` ``` """Helper for filtering components that can't be k-edge-connected. ``` ``` ``` ``` Removes and generates each node with degree less than k. Then generates ``` ``` remaining components where all nodes have degree at least k. ``` ``` """ ``` ``` # Iteravely remove parts of the graph that are not k-edge-connected ``` ``` H = G.copy() ``` ``` singletons = set(_low_degree_nodes(H, k)) ``` ``` while singletons: ``` ``` # Only search neighbors of removed nodes ``` ``` nbunch = set(it.chain.from_iterable(map(H.neighbors, singletons))) ``` ``` nbunch.difference_update(singletons) ``` ``` H.remove_nodes_from(singletons) ``` ``` for node in singletons: ``` ``` yield {node} ``` ``` singletons = set(_low_degree_nodes(H, k, nbunch)) ``` ``` # Note: remaining connected components may not be k-edge-connected ``` ``` if G.is_directed(): ``` ``` for cc in nx.strongly_connected_components(H): ``` ``` yield cc ``` ``` else: ``` ``` for cc in nx.connected_components(H): ``` ``` yield cc ``` ```def general_k_edge_subgraphs(G, k): ``` ``` """General algorithm to find all maximal k-edge-connected subgraphs in G. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` k_edge_subgraphs : a generator of nx.Graphs that are k-edge-subgraphs ``` ``` Each k-edge-subgraph is a maximal set of nodes that defines a subgraph ``` ``` of G that is k-edge-connected. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` Implementation of the basic algorithm from _. The basic idea is to find ``` ``` a global minimum cut of the graph. If the cut value is at least k, then the ``` ``` graph is a k-edge-connected subgraph and can be added to the results. ``` ``` Otherwise, the cut is used to split the graph in two and the procedure is ``` ``` applied recursively. If the graph is just a single node, then it is also ``` ``` added to the results. At the end, each result is either guaranteed to be ``` ``` a single node or a subgraph of G that is k-edge-connected. ``` ``` ``` ``` This implementation contains optimizations for reducing the number of calls ``` ``` to max-flow, but there are other optimizations in _ that could be ``` ``` implemented. ``` ``` ``` ``` References ``` ``` ---------- ``` ``` ..  Zhou, Liu, et al. (2012) Finding maximal k-edge-connected subgraphs ``` ``` from a large graph. ACM International Conference on Extending Database ``` ``` Technology 2012 480-–491. ``` ``` https://openproceedings.org/2012/conf/edbt/ZhouLYLCL12.pdf ``` ``` ``` ``` Example ``` ``` ------- ``` ``` >>> from networkx.utils import pairwise ``` ``` >>> paths = [ ``` ``` ... (11, 12, 13, 14, 11, 13, 14, 12), # a 4-clique ``` ``` ... (21, 22, 23, 24, 21, 23, 24, 22), # another 4-clique ``` ``` ... # connect the cliques with high degree but low connectivity ``` ``` ... (50, 13), ``` ``` ... (12, 50, 22), ``` ``` ... (13, 102, 23), ``` ``` ... (14, 101, 24), ``` ``` ... ] ``` ``` >>> G = nx.Graph(it.chain(*[pairwise(path) for path in paths])) ``` ``` >>> sorted(map(len, k_edge_subgraphs(G, k=3))) ``` ``` [1, 1, 1, 4, 4] ``` ``` """ ``` ``` if k < 1: ``` ``` raise ValueError('k cannot be less than 1') ``` ``` # Node pruning optimization (incorporates early return) ``` ``` # find_ccs is either connected_components/strongly_connected_components ``` ``` find_ccs = partial(_high_degree_components, k=k) ``` ``` # Quick return optimization ``` ``` if G.number_of_nodes() < k: ``` ``` for node in G.nodes(): ``` ``` yield G.subgraph([node]).copy() ``` ``` return ``` ``` # Intermediate results ``` ``` R0 = {G.subgraph(cc).copy() for cc in find_ccs(G)} ``` ``` # Subdivide CCs in the intermediate results until they are k-conn ``` ``` while R0: ``` ``` G1 = R0.pop() ``` ``` if G1.number_of_nodes() == 1: ``` ``` yield G1 ``` ``` else: ``` ``` # Find a global minimum cut ``` ``` cut_edges = nx.minimum_edge_cut(G1) ``` ``` cut_value = len(cut_edges) ``` ``` if cut_value < k: ``` ``` # G1 is not k-edge-connected, so subdivide it ``` ``` G1.remove_edges_from(cut_edges) ``` ``` for cc in find_ccs(G1): ``` ``` R0.add(G1.subgraph(cc).copy()) ``` ``` else: ``` ``` # Otherwise we found a k-edge-connected subgraph ``` ``` yield G1 ```