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.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: Eben Kenah
#          Aric Hagberg (hagberg@lanl.gov)
#          Christopher Ellison
"""Connected components."""
import networkx as nx
from networkx.utils.decorators import not_implemented_for
from ...utils import arbitrary_element

__all__ = [
    'number_connected_components',
    'connected_components',
    'connected_component_subgraphs',
    'is_connected',
    'node_connected_component',
]


[docs]@not_implemented_for('directed') def connected_components(G): """Generate connected components. Parameters ---------- G : NetworkX graph An undirected graph Returns ------- comp : generator of sets A generator of sets of nodes, one for each component of G. Raises ------ NetworkXNotImplemented: If G is undirected. Examples -------- Generate a sorted list of connected components, largest first. >>> G = nx.path_graph(4) >>> nx.add_path(G, [10, 11, 12]) >>> [len(c) for c in sorted(nx.connected_components(G), key=len, reverse=True)] [4, 3] If you only want the largest connected component, it's more efficient to use max instead of sort. >>> largest_cc = max(nx.connected_components(G), key=len) See Also -------- strongly_connected_components weakly_connected_components Notes ----- For undirected 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('directed') def connected_component_subgraphs(G, copy=True): """Generate connected components as subgraphs. Parameters ---------- G : NetworkX graph An undirected graph. copy: bool (default=True) If True make a copy of the graph attributes Returns ------- comp : generator A generator of graphs, one for each connected component of G. Raises ------ NetworkXNotImplemented: If G is undirected. Examples -------- >>> G = nx.path_graph(4) >>> G.add_edge(5,6) >>> graphs = list(nx.connected_component_subgraphs(G)) If you only want the largest connected component, it's more efficient to use max instead of sort: >>> Gc = max(nx.connected_component_subgraphs(G), key=len) See Also -------- connected_components strongly_connected_component_subgraphs weakly_connected_component_subgraphs Notes ----- For undirected graphs only. Graph, node, and edge attributes are copied to the subgraphs by default. """ for c in connected_components(G): if copy: yield G.subgraph(c).copy() else: yield G.subgraph(c)
[docs]def number_connected_components(G): """Return the number of connected components. Parameters ---------- G : NetworkX graph An undirected graph. Returns ------- n : integer Number of connected components See Also -------- connected_components number_weakly_connected_components number_strongly_connected_components Notes ----- For undirected graphs only. """ return len(list(connected_components(G)))
[docs]@not_implemented_for('directed') def is_connected(G): """Return True if the graph is connected, false otherwise. Parameters ---------- G : NetworkX Graph An undirected graph. Returns ------- connected : bool True if the graph is connected, false otherwise. Raises ------ NetworkXNotImplemented: If G is undirected. Examples -------- >>> G = nx.path_graph(4) >>> print(nx.is_connected(G)) True See Also -------- is_strongly_connected is_weakly_connected is_semiconnected is_biconnected connected_components Notes ----- For undirected graphs only. """ if len(G) == 0: raise nx.NetworkXPointlessConcept('Connectivity is undefined ', 'for the null graph.') return len(set(_plain_bfs(G, arbitrary_element(G)))) == len(G)
[docs]@not_implemented_for('directed') def node_connected_component(G, n): """Return the nodes in the component of graph containing node n. Parameters ---------- G : NetworkX Graph An undirected graph. n : node label A node in G Returns ------- comp : set A set of nodes in the component of G containing node n. Raises ------ NetworkXNotImplemented: If G is directed. See Also -------- connected_components Notes ----- For undirected graphs only. """ return set(_plain_bfs(G, n))
def _plain_bfs(G, source): """A fast BFS node generator""" G_adj = G.adj 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(G_adj[v])