| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111 |
- """Attracting components."""
- import networkx as nx
- from networkx.utils.decorators import not_implemented_for
- __all__ = [
- "number_attracting_components",
- "attracting_components",
- "is_attracting_component",
- ]
- @not_implemented_for("undirected")
- def attracting_components(G):
- """Generates the 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.
- To obtain induced subgraphs on each component use:
- ``(G.subgraph(c).copy() for c in attracting_components(G))``
- 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.
- Raises
- ------
- NetworkXNotImplemented
- If the input graph is undirected.
- See Also
- --------
- number_attracting_components
- is_attracting_component
- """
- 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.
- Raises
- ------
- NetworkXNotImplemented
- If the input graph is undirected.
- See Also
- --------
- attracting_components
- is_attracting_component
- """
- return sum(1 for ac in attracting_components(G))
- @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.
- Raises
- ------
- NetworkXNotImplemented
- If the input graph is undirected.
- See Also
- --------
- attracting_components
- number_attracting_components
- """
- ac = list(attracting_components(G))
- if len(ac) == 1:
- return len(ac[0]) == len(G)
- return False
|
