Warning

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

# Source code for networkx.algorithms.components.weakly_connected

# -*- coding: utf-8 -*-
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#
# Authors: Aric Hagberg (hagberg@lanl.gov)
#          Christopher Ellison
"""Weakly connected components."""
import warnings as _warnings
import networkx as nx
from networkx.utils.decorators import not_implemented_for

__all__ = [
'number_weakly_connected_components',
'weakly_connected_components',
'weakly_connected_component_subgraphs',
'is_weakly_connected',
]

[docs]@not_implemented_for('undirected')
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())
>>> [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

>>> largest_cc = max(nx.weakly_connected_components(G), key=len)

--------
connected_components
strongly_connected_components

Notes
-----
For directed graphs only.

"""
seen = set()
for v in G:
if v not in seen:
c = set(_plain_bfs(G, v))
yield c
seen.update(c)

[docs]@not_implemented_for('undirected')
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.

--------
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')
def weakly_connected_component_subgraphs(G, copy=True):
"""DEPRECATED: Use (G.subgraph(c) for c in weakly_connected_components(G))

Or (G.subgraph(c).copy() for c in weakly_connected_components(G))
"""
msg = "weakly_connected_component_subgraphs is deprecated and will be removed in 2.2" \
"use (G.subgraph(c).copy() for c in weakly_connected_components(G))"
_warnings.warn(msg, DeprecationWarning)
for c in weakly_connected_components(G):
if copy:
yield G.subgraph(c).copy()
else:
yield G.subgraph(c)

[docs]@not_implemented_for('undirected')
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.

--------
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(list(weakly_connected_components(G))[0]) == len(G)

def _plain_bfs(G, 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 = set()
nextlevel = {source}
while nextlevel:
thislevel = nextlevel
nextlevel = set()
for v in thislevel:
if v not in seen:
yield v