networkx.algorithms.connectivity.edge_kcomponents.EdgeComponentAuxGraph¶

class
EdgeComponentAuxGraph
[source]¶ A simple algorithm to find all kedgeconnected components in a graph.
Constructing the AuxillaryGraph (which may take some time) allows for the kedgeccs to be found in linear time for arbitrary k.
Notes
This implementation is based on [1]. The idea is to construct an auxiliary graph from which the kedgeccs 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
[1] Wang, Tianhao, et al. (2015) A simple algorithm for finding all kedgeconnected 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 kedgeccs >>> paths = [ ... (1, 2, 3, 4, 1, 3, 4, 2), # a 3edgecc (a 4 clique) ... (5, 6, 7, 5), # a 2edgecc (a 3 clique) ... (1, 5), # combine first two ccs into a 1edgecc ... (0,), # add an additional disconnected 1edgecc ... ] >>> 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))) [[0], [1, 2, 3, 4, 5, 6, 7]] >>> sorted(map(sorted, aux_graph.k_edge_components(k=2))) [[0], [1, 2, 3, 4], [5, 6, 7]] >>> sorted(map(sorted, aux_graph.k_edge_components(k=3))) [[0], [1, 2, 3, 4], [5], [6], [7]] >>> sorted(map(sorted, aux_graph.k_edge_components(k=4))) [[0], [1], [2], [3], [4], [5], [6], [7]]
Example
>>> # The auxiliary graph is primarilly used for kedgeccs but it >>> # can also speed up the queries of kedgesubgraphs 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))) [[1], [2], [3], [4]] >>> sorted(map(sorted, aux_graph.k_edge_components(k=3))) [[1, 4], [2], [3]]

__init__
()¶ Initialize self. See help(type(self)) for accurate signature.
Methods
construct
(G)Builds an auxiliary graph encoding edgeconnectivity between nodes. k_edge_components
(k)Queries the auxiliary graph for kedgeconnected components. k_edge_subgraphs
(k)Queries the auxiliary graph for kedgeconnected subgraphs. 