k_edge_subgraphs¶

k_edge_subgraphs(G, k)[source]¶

Generates nodes in each maximal k-edge-connected subgraph in G.

Parameters

GNetworkX graph
kInteger: Desired edge connectivity

Returns

k_edge_subgraphsa 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.

Raises

NetworkXNotImplemented: If the input graph is a multigraph.
ValueError:: If k is less than 1

See also

edge_connectivity()
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.

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 _[1] is used.

References

1: 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

Examples

>>> 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)))
[[1], [2], [3], [4], [5, 6, 7, 8]]