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 -*-
"""Weakly connected components.
"""
# Copyright (C) 2004-2013 by
# Aric Hagberg <hagberg@lanl.gov>
# Dan Schult <dschult@colgate.edu>
# Pieter Swart <swart@lanl.gov>
# All rights reserved.
# BSD license.
import networkx as nx
from networkx.utils.decorators import not_implemented_for
__authors__ = "\n".join(['Aric Hagberg (hagberg@lanl.gov)'
'Christopher Ellison'])
__all__ = ['number_weakly_connected_components',
'weakly_connected_components',
'weakly_connected_component_subgraphs',
'is_weakly_connected'
]
@not_implemented_for('undirected')
[docs]def weakly_connected_components(G):
"""Generate weakly connected components of G.
"""
seen={}
for v in G:
if v not in seen:
c=_single_source_shortest_unipath_length(G,v)
yield list(c.keys())
seen.update(c)
@not_implemented_for('undirected')
[docs]def number_weakly_connected_components(G):
"""Return the number of connected components in G.
For directed graphs only.
"""
return len(list(weakly_connected_components(G)))
@not_implemented_for('undirected')
[docs]def weakly_connected_component_subgraphs(G, copy=True):
"""Generate weakly connected components as subgraphs.
Parameters
----------
G : NetworkX Graph
A directed graph.
copy : bool
If copy is True, graph, node, and edge attributes are copied to the
subgraphs.
"""
for comp in weakly_connected_components(G):
if copy:
yield G.subgraph(comp).copy()
else:
yield G.subgraph(comp)
@not_implemented_for('undirected')
[docs]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.
Parameters
----------
G : NetworkX Graph
A directed graph.
Returns
-------
connected : bool
True if the graph is weakly connected, False otherwise.
See Also
--------
is_strongly_connected
is_semiconnected
is_connected
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 _single_source_shortest_unipath_length(G,source,cutoff=None):
"""Compute the shortest path lengths from source to all reachable nodes.
The direction of the edge between nodes is ignored.
For directed graphs only.
Parameters
----------
G : NetworkX graph
source : node
Starting node for path
cutoff : integer, optional
Depth to stop the search. Only paths of length <= cutoff are returned.
Returns
-------
lengths : dictionary
Dictionary of shortest path lengths keyed by target.
"""
# namespace speedups
Gsucc = G.succ
Gpred = G.pred
seen={} # level (number of hops) when seen in BFS
level=0 # the current level
nextlevel = set([source]) # set of nodes to check at next level
while nextlevel:
thislevel=nextlevel # advance to next level
nextlevel = set() # and start a new list (fringe)
for v in thislevel:
if v not in seen:
seen[v]=level # set the level of vertex v
nextlevel.update(Gsucc[v]) # add successors of v
nextlevel.update(Gpred[v]) # add predecessors of v
if (cutoff is not None and cutoff <= level): break
level=level+1
return seen # return all path lengths as dictionary
```