Source code for networkx.algorithms.components.attracting

# -*- coding: utf-8 -*-
"""
Attracting components.
"""
#    Copyright (C) 2004-2011 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
__authors__ = "\n".join(['Christopher Ellison'])
__all__ = ['number_attracting_components', 
           'attracting_components',
           'is_attracting_component', 
           'attracting_component_subgraphs',
           ]

def attracting_components(G):
    """Returns a list of attracting components in `G`.

    An attracting component in a directed graph `G` is a strongly connected
    component with the property that a random walker on the graph will never
    leave the component, once it enters the component.

    The nodes in attracting components can also be thought of as recurrent
    nodes.  If a random walker enters the attractor containing the node, then
    the node will be visited infinitely often.

    Parameters
    ----------
    G : DiGraph, MultiDiGraph
        The graph to be analyzed.

    Returns
    -------
    attractors : list
        The list of attracting components, sorted from largest attracting
        component to smallest attracting component.

    See Also
    --------
    number_attracting_components
    is_attracting_component 
    attracting_component_subgraphs

    """
    scc = nx.strongly_connected_components(G)
    cG = nx.condensation(G, scc)
    attractors = [scc[n] for n in cG if cG.out_degree(n) == 0]
    attractors.sort(key=len,reverse=True)
    return attractors


def number_attracting_components(G):
    """Returns the number of attracting components in `G`.

    Parameters
    ----------
    G : DiGraph, MultiDiGraph
        The graph to be analyzed.

    Returns
    -------
    n : int
        The number of attracting components in G.

    See Also
    --------
    attracting_components
    is_attracting_component
    attracting_component_subgraphs

    """
    n = len(attracting_components(G))
    return n


def is_attracting_component(G):
    """Returns True if `G` consists of a single attracting component.

    Parameters
    ----------
    G : DiGraph, MultiDiGraph
        The graph to be analyzed.

    Returns
    -------
    attracting : bool
        True if `G` has a single attracting component. Otherwise, False.

    See Also
    --------
    attracting_components
    number_attracting_components
    attracting_component_subgraphs

    """
    ac = attracting_components(G)
    if len(ac[0]) == len(G):
        attracting = True
    else:
        attracting = False
    return attracting


def attracting_component_subgraphs(G):
    """Returns a list of attracting component subgraphs from `G`.

    Parameters
    ----------
    G : DiGraph, MultiDiGraph
        The graph to be analyzed.

    Returns
    -------
    subgraphs : list
        A list of node-induced subgraphs of the attracting components of `G`.
    
    Notes
    -----
    Graph, node, and edge attributes are copied to the subgraphs.

    See Also
    --------
    attracting_components
    number_attracting_components
    is_attracting_component

    """
    subgraphs = [G.subgraph(ac).copy() for ac in attracting_components(G)]
    return subgraphs