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
__init__
()Initialize self.
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.