Source code for networkx.algorithms.components.weakly_connected

"""Weakly connected components."""

import networkx as nx
from networkx.utils.decorators import not_implemented_for

__all__ = [
    "number_weakly_connected_components",
    "weakly_connected_components",
    "is_weakly_connected",
]


[docs] @not_implemented_for("undirected") @nx._dispatchable def weakly_connected_components(G): """Generate weakly connected components of G. Parameters ---------- G : NetworkX graph A directed graph Returns ------- comp : generator of sets A generator of sets of nodes, one for each weakly connected component of G. Raises ------ NetworkXNotImplemented If G is undirected. Examples -------- Generate a sorted list of weakly connected components, largest first. >>> G = nx.path_graph(4, create_using=nx.DiGraph()) >>> nx.add_path(G, [10, 11, 12]) >>> [ ... len(c) ... for c in sorted(nx.weakly_connected_components(G), key=len, reverse=True) ... ] [4, 3] If you only want the largest component, it's more efficient to use max instead of sort: >>> largest_cc = max(nx.weakly_connected_components(G), key=len) See Also -------- connected_components strongly_connected_components Notes ----- For directed graphs only. """ 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 = set(_plain_bfs(G, n, v)) seen.update(c) yield c
[docs] @not_implemented_for("undirected") @nx._dispatchable def number_weakly_connected_components(G): """Returns the number of weakly connected components in G. Parameters ---------- G : NetworkX graph A directed graph. Returns ------- n : integer Number of weakly connected components Raises ------ NetworkXNotImplemented If G is undirected. Examples -------- >>> G = nx.DiGraph([(0, 1), (2, 1), (3, 4)]) >>> nx.number_weakly_connected_components(G) 2 See Also -------- weakly_connected_components number_connected_components number_strongly_connected_components Notes ----- For directed graphs only. """ return sum(1 for wcc in weakly_connected_components(G))
[docs] @not_implemented_for("undirected") @nx._dispatchable def is_weakly_connected(G): """Test directed graph for weak connectivity. A directed graph is weakly connected if and only if the graph is connected when the direction of the edge between nodes is ignored. Note that if a graph is strongly connected (i.e. the graph is connected even when we account for directionality), it is by definition weakly connected as well. Parameters ---------- G : NetworkX Graph A directed graph. Returns ------- connected : bool True if the graph is weakly connected, False otherwise. Raises ------ NetworkXNotImplemented If G is undirected. Examples -------- >>> G = nx.DiGraph([(0, 1), (2, 1)]) >>> G.add_node(3) >>> nx.is_weakly_connected(G) # node 3 is not connected to the graph False >>> G.add_edge(2, 3) >>> nx.is_weakly_connected(G) True See Also -------- is_strongly_connected is_semiconnected is_connected is_biconnected weakly_connected_components Notes ----- For directed graphs only. """ if len(G) == 0: raise nx.NetworkXPointlessConcept( """Connectivity is undefined for the null graph.""" ) return len(next(weakly_connected_components(G))) == len(G)
def _plain_bfs(G, n, source): """A fast BFS node generator The direction of the edge between nodes is ignored. For directed graphs only. """ Gsucc = G._succ Gpred = G._pred seen = {source} nextlevel = [source] yield source while nextlevel: thislevel = nextlevel nextlevel = [] for v in thislevel: for w in Gsucc[v]: if w not in seen: seen.add(w) nextlevel.append(w) yield w for w in Gpred[v]: if w not in seen: seen.add(w) nextlevel.append(w) yield w if len(seen) == n: return