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

# -*- coding: utf-8 -*-
"""
Attracting 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(['Christopher Ellison'])
__all__ = ['number_attracting_components',
'attracting_components',
'is_attracting_component',
'attracting_component_subgraphs',
]

@not_implemented_for('undirected')
[docs]def attracting_components(G):
"""Generates 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 : generator of list
The list of attracting components, sorted from largest attracting
component to smallest attracting component.

--------
number_attracting_components
is_attracting_component
attracting_component_subgraphs
"""
scc = list(nx.strongly_connected_components(G))
cG = nx.condensation(G, scc)
for n in cG:
if cG.out_degree(n) == 0:
yield scc[n]

@not_implemented_for('undirected')
[docs]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.

--------
attracting_components
is_attracting_component
attracting_component_subgraphs

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

@not_implemented_for('undirected')
[docs]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.

--------
attracting_components
number_attracting_components
attracting_component_subgraphs

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

@not_implemented_for('undirected')
[docs]def attracting_component_subgraphs(G, copy=True):
"""Generates 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.

copy : bool
If copy is True, graph, node, and edge attributes are copied to the
subgraphs.