Constructing the AuxillaryGraph (which may take some time) allows for the k-edge-ccs to be found in linear time for arbitrary k.
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(
<SubstitutionRef: |value: '|V|' |>\cdot F)$ operations, where F is the complexity of max flow. Querying the components takes an additional $O(
<SubstitutionRef: |value: '|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.
A simple algorithm to find all k-edge-connected components in a graph.
>>> 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))) [[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]]
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))) [[1], [2], [3], [4]]
>>> sorted(map(sorted, aux_graph.k_edge_components(k=3))) [[1, 4], [2], [3]]See :
The following pages refer to to this document either explicitly or contain code examples using this.
networkx.algorithms.connectivity.edge_kcomponents.EdgeComponentAuxGraph
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them