/usr/lib/python3/dist-packages/networkx/algorithms/components/attracting.py is in python3-networkx 1.11-1ubuntu2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 | # -*- coding: utf-8 -*-
"""
Attracting components.
"""
# Copyright (C) 2004-2015 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(['Christopher Ellison'])
__all__ = ['number_attracting_components',
'attracting_components',
'is_attracting_component',
'attracting_component_subgraphs',
]
@not_implemented_for('undirected')
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 sets
A generator of sets of nodes, one for each attracting component of G.
See Also
--------
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')
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(list(attracting_components(G)))
return n
@not_implemented_for('undirected')
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 = list(attracting_components(G))
if len(ac[0]) == len(G):
attracting = True
else:
attracting = False
return attracting
@not_implemented_for('undirected')
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.
See Also
--------
attracting_components
number_attracting_components
is_attracting_component
"""
for ac in attracting_components(G):
if copy:
yield G.subgraph(ac).copy()
else:
yield G.subgraph(ac)
|