Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

# networkx.algorithms.connectivity.edge_kcomponents.EdgeComponentAuxGraph¶

class EdgeComponentAuxGraph[source]

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
... ]
>>> G = nx.Graph()
>>> 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_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], , ]

__init__()

Initialize self. See help(type(self)) for accurate signature.

Methods

 construct(G) Builds an auxiliary graph encoding edge-connectivity between nodes. k_edge_components(k) Queries the auxiliary graph for k-edge-connected components. k_edge_subgraphs(k) Queries the auxiliary graph for k-edge-connected subgraphs.