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