"""Connected components."""
import networkx as nx
from networkx.utils.decorators import not_implemented_for
from ...utils import arbitrary_element
__all__ = [
"number_connected_components",
"connected_components",
"is_connected",
"node_connected_component",
]
[docs]
@not_implemented_for("directed")
@nx._dispatchable
def connected_components(G):
"""Generate connected components.
The connected components of an undirected graph partition the graph into
disjoint sets of nodes. Each of these sets induces a subgraph of graph
`G` that is connected and not part of any larger connected subgraph.
A graph is connected (:func:`is_connected`) if, for every pair of distinct
nodes, there is a path between them. If there is a pair of nodes for
which such path does not exist, the graph is not connected (also referred
to as "disconnected").
A graph consisting of a single node and no edges is connected.
Connectivity is undefined for the null graph (graph with no nodes).
Parameters
----------
G : NetworkX graph
An undirected graph
Yields
------
comp : set
A set of nodes in one connected component of the graph.
Raises
------
NetworkXNotImplemented
If G is directed.
Examples
--------
Generate a sorted list of connected components, largest first.
>>> G = nx.path_graph(4)
>>> nx.add_path(G, [10, 11, 12])
>>> [len(c) for c in sorted(nx.connected_components(G), key=len, reverse=True)]
[4, 3]
If you only want the largest connected component, it's more
efficient to use max instead of sort.
>>> largest_cc = max(nx.connected_components(G), key=len)
To create the induced subgraph of each component use:
>>> S = [G.subgraph(c).copy() for c in nx.connected_components(G)]
See Also
--------
number_connected_components
is_connected
number_weakly_connected_components
number_strongly_connected_components
Notes
-----
This function is for undirected graphs only. For directed graphs, use
:func:`strongly_connected_components` or
:func:`weakly_connected_components`.
The algorithm is based on a Breadth-First Search (BFS) traversal and its
time complexity is $O(n + m)$, where $n$ is the number of nodes and $m$ the
number of edges in the graph.
"""
seen = set()
n = len(G) # must be outside the loop to avoid performance hit with graph views
for v in G:
if v not in seen:
c = _plain_bfs(G, n - len(seen), v)
seen.update(c)
yield c
[docs]
@not_implemented_for("directed")
@nx._dispatchable
def number_connected_components(G):
"""Returns the number of connected components.
The connected components of an undirected graph partition the graph into
disjoint sets of nodes. Each of these sets induces a subgraph of graph
`G` that is connected and not part of any larger connected subgraph.
A graph is connected (:func:`is_connected`) if, for every pair of distinct
nodes, there is a path between them. If there is a pair of nodes for
which such path does not exist, the graph is not connected (also referred
to as "disconnected").
A graph consisting of a single node and no edges is connected.
Connectivity is undefined for the null graph (graph with no nodes).
Parameters
----------
G : NetworkX graph
An undirected graph.
Returns
-------
n : integer
Number of connected components
Raises
------
NetworkXNotImplemented
If G is directed.
Examples
--------
>>> G = nx.Graph([(0, 1), (1, 2), (5, 6), (3, 4)])
>>> nx.number_connected_components(G)
3
See Also
--------
connected_components
is_connected
number_weakly_connected_components
number_strongly_connected_components
Notes
-----
This function is for undirected graphs only. For directed graphs, use
:func:`number_strongly_connected_components` or
:func:`number_weakly_connected_components`.
The algorithm is based on a Breadth-First Search (BFS) traversal and its
time complexity is $O(n + m)$, where $n$ is the number of nodes and $m$ the
number of edges in the graph.
"""
return sum(1 for _ in connected_components(G))
[docs]
@not_implemented_for("directed")
@nx._dispatchable
def is_connected(G):
"""Returns True if the graph is connected, False otherwise.
A graph is connected if, for every pair of distinct nodes, there is a
path between them. If there is a pair of nodes for which such path does
not exist, the graph is not connected (also referred to as "disconnected").
A graph consisting of a single node and no edges is connected.
Connectivity is undefined for the null graph (graph with no nodes).
Parameters
----------
G : NetworkX Graph
An undirected graph.
Returns
-------
connected : bool
True if the graph is connected, False otherwise.
Raises
------
NetworkXNotImplemented
If G is directed.
Examples
--------
>>> G = nx.path_graph(4)
>>> print(nx.is_connected(G))
True
See Also
--------
is_strongly_connected
is_weakly_connected
is_semiconnected
is_biconnected
connected_components
Notes
-----
This function is for undirected graphs only. For directed graphs, use
:func:`is_strongly_connected` or :func:`is_weakly_connected`.
The algorithm is based on a Breadth-First Search (BFS) traversal and its
time complexity is $O(n + m)$, where $n$ is the number of nodes and $m$ the
number of edges in the graph.
"""
n = len(G)
if n == 0:
raise nx.NetworkXPointlessConcept(
"Connectivity is undefined for the null graph."
)
return len(next(connected_components(G))) == n
[docs]
@not_implemented_for("directed")
@nx._dispatchable
def node_connected_component(G, n):
"""Returns the set of nodes in the component of graph containing node n.
A connected component is a set of nodes that induces a subgraph of graph
`G` that is connected and not part of any larger connected subgraph.
A graph is connected (:func:`is_connected`) if, for every pair of distinct
nodes, there is a path between them. If there is a pair of nodes for
which such path does not exist, the graph is not connected (also referred
to as "disconnected").
A graph consisting of a single node and no edges is connected.
Connectivity is undefined for the null graph (graph with no nodes).
Parameters
----------
G : NetworkX Graph
An undirected graph.
n : node label
A node in G
Returns
-------
comp : set
A set of nodes in the component of G containing node n.
Raises
------
NetworkXNotImplemented
If G is directed.
Examples
--------
>>> G = nx.Graph([(0, 1), (1, 2), (5, 6), (3, 4)])
>>> nx.node_connected_component(G, 0) # nodes of component that contains node 0
{0, 1, 2}
See Also
--------
connected_components
Notes
-----
This function is for undirected graphs only.
The algorithm is based on a Breadth-First Search (BFS) traversal and its
time complexity is $O(n + m)$, where $n$ is the number of nodes and $m$ the
number of edges in the graph.
"""
return _plain_bfs(G, len(G), n)
def _plain_bfs(G, n, source):
"""A fast BFS node generator"""
adj = G._adj
seen = {source}
nextlevel = [source]
while nextlevel:
thislevel = nextlevel
nextlevel = []
for v in thislevel:
for w in adj[v]:
if w not in seen:
seen.add(w)
nextlevel.append(w)
if len(seen) == n:
return seen
return seen
