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 -*-
#    Copyright (C) 2004-2017 by
#    Aric Hagberg <hagberg@lanl.gov>
#    Dan Schult <dschult@colgate.edu>
#    Pieter Swart <swart@lanl.gov>
#    All rights reserved.
#    BSD license.
#
# Authors: Aric Hagberg (hagberg@lanl.gov)
#          Christopher Ellison
"""Weakly connected components."""
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()) >>> 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() 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): """Return 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. See Also -------- weakly_connected_components number_connected_components number_strongly_connected_components Notes ----- For directed graphs only. """ return len(list(weakly_connected_components(G)))
[docs]@not_implemented_for('undirected') def weakly_connected_component_subgraphs(G, copy=True): """Generate weakly connected components as subgraphs. Parameters ---------- G : NetworkX graph A directed graph. copy: bool (default=True) If True make a copy of the graph attributes Returns ------- comp : generator A generator of graphs, 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_component_subgraphs(G), ... key=len, reverse=True)] [4, 3] If you only want the largest component, it's more efficient to use max instead of sort: >>> Gc = max(nx.weakly_connected_component_subgraphs(G), key=len) See Also -------- weakly_connected_components strongly_connected_component_subgraphs connected_component_subgraphs Notes ----- For directed graphs only. Graph, node, and edge attributes are copied to the subgraphs by default. """ for comp in weakly_connected_components(G): if copy: yield G.subgraph(comp).copy() else: yield G.subgraph(comp)
[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. 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. 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(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 seen.add(v) nextlevel.update(Gsucc[v]) nextlevel.update(Gpred[v])