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.
"""
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>

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.

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