"""强连通分量。"""
import networkx as nx
from networkx.utils.decorators import not_implemented_for
__all__ = [
"number_strongly_connected_components",
"strongly_connected_components",
"is_strongly_connected",
"kosaraju_strongly_connected_components",
"condensation",
]
[docs]
@not_implemented_for("undirected")
@nx._dispatchable
def strongly_connected_components(G):
"""生成图中强连通分量的节点。
Parameters
----------
G : NetworkX 图
一个有向图。
Returns
-------
comp : 集合生成器
一个生成器，每个集合包含图 G 的一个强连通分量的节点。
Raises
------
NetworkXNotImplemented
如果 G 是无向图。
Examples
--------
生成一个按大小排序的强连通分量列表，从大到小。
>>> G = nx.cycle_graph(4, create_using=nx.DiGraph())
>>> nx.add_cycle(G, [10, 11, 12])
>>> [
... len(c)
... for c in sorted(nx.strongly_connected_components(G), key=len, reverse=True)
... ]
[4, 3]
如果只需要最大的分量，使用 max 比排序更高效。
>>> largest = max(nx.strongly_connected_components(G), key=len)
See Also
--------
connected_components
weakly_connected_components
kosaraju_strongly_connected_components
Notes
-----
使用 Tarjan 的算法[1]_ 结合 Nuutila 的改进[2]_。
算法的非递归版本。
References
----------
.. [1] 深度优先搜索和线性图算法，R. Tarjan
SIAM 计算杂志 1(2):146-160, (1972).
.. [2] 在有向图中寻找强连通分量。
E. Nuutila 和 E. Soisalon-Soinen
信息处理快报 49(1): 9-14, (1994).
"""
preorder = {}
lowlink = {}
scc_found = set()
scc_queue = []
i = 0 # Preorder counter
neighbors = {v: iter(G[v]) for v in G}
for source in G:
if source not in scc_found:
queue = [source]
while queue:
v = queue[-1]
if v not in preorder:
i = i + 1
preorder[v] = i
done = True
for w in neighbors[v]:
if w not in preorder:
queue.append(w)
done = False
break
if done:
lowlink[v] = preorder[v]
for w in G[v]:
if w not in scc_found:
if preorder[w] > preorder[v]:
lowlink[v] = min([lowlink[v], lowlink[w]])
else:
lowlink[v] = min([lowlink[v], preorder[w]])
queue.pop()
if lowlink[v] == preorder[v]:
scc = {v}
while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
k = scc_queue.pop()
scc.add(k)
scc_found.update(scc)
yield scc
else:
scc_queue.append(v)
[docs]
@not_implemented_for("undirected")
@nx._dispatchable
def kosaraju_strongly_connected_components(G, source=None):
"""生成图中强连通分量的节点。
Parameters
----------
G : NetworkX 图
一个有向图。
Returns
-------
comp : 集合生成器
一个生成器，每个集合代表图 G 中的一个强连通分量。
Raises
------
NetworkXNotImplemented
如果 G 是无向图。
Examples
--------
生成一个按大小排序的强连通分量列表，从大到小。
>>> G = nx.cycle_graph(4, create_using=nx.DiGraph())
>>> nx.add_cycle(G, [10, 11, 12])
>>> [
... len(c)
... for c in sorted(
... nx.kosaraju_strongly_connected_components(G), key=len, reverse=True
... )
... ]
[4, 3]
如果你只需要最大的分量，使用 max 比排序更高效。
>>> largest = max(nx.kosaraju_strongly_connected_components(G), key=len)
See Also
--------
strongly_connected_components
Notes
-----
使用 Kosaraju 算法。
"""
post = list(nx.dfs_postorder_nodes(G.reverse(copy=False), source=source))
seen = set()
while post:
r = post.pop()
if r in seen:
continue
c = nx.dfs_preorder_nodes(G, r)
new = {v for v in c if v not in seen}
seen.update(new)
yield new
[docs]
@not_implemented_for("undirected")
@nx._dispatchable
def number_strongly_connected_components(G):
"""返回图中强连通分量的数量。
Parameters
----------
G : NetworkX 图
一个有向图。
Returns
-------
n : 整数
强连通分量的数量
Raises
------
NetworkXNotImplemented
如果 G 是无向图。
Examples
--------
>>> G = nx.DiGraph(
... [(0, 1), (1, 2), (2, 0), (2, 3), (4, 5), (3, 4), (5, 6), (6, 3), (6, 7)]
... )
>>> nx.number_strongly_connected_components(G)
3
See Also
--------
strongly_connected_components
number_connected_components
number_weakly_connected_components
Notes
-----
仅适用于有向图。
"""
return sum(1 for scc in strongly_connected_components(G))
[docs]
@not_implemented_for("undirected")
@nx._dispatchable
def is_strongly_connected(G):
"""测试有向图的强连通性。
一个有向图是强连通的当且仅当图中的每个顶点都可以从其他每个顶点到达。
Parameters
----------
G : NetworkX 图
一个有向图。
Returns
-------
connected : bool
如果图是强连通的，则为 True，否则为 False。
Examples
--------
>>> G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3, 0), (2, 4), (4, 2)])
>>> nx.is_strongly_connected(G)
True
>>> G.remove_edge(2, 3)
>>> nx.is_strongly_connected(G)
False
Raises
------
NetworkXNotImplemented
如果 G 是无向的。
See Also
--------
is_weakly_connected
is_semiconnected
is_connected
is_biconnected
strongly_connected_components
Notes
-----
仅适用于有向图。
"""
if len(G) == 0:
raise nx.NetworkXPointlessConcept(
"""Connectivity is undefined for the null graph."""
)
return len(next(strongly_connected_components(G))) == len(G)
[docs]
@not_implemented_for("undirected")
@nx._dispatchable(returns_graph=True)
def condensation(G, scc=None):
"""返回 G 的缩合图。
G 的缩合图是将每个强连通分量收缩为一个单一节点的图。
Parameters
----------
G : NetworkX 有向图
一个有向图。
scc: 列表或生成器（可选，默认=None）
强连通分量。如果提供， `scc` 中的元素必须对 `G` 中的节点进行分区。如果没有提供，将计算为 scc=nx.strongly_connected_components(G)。
Returns
-------
C : NetworkX 有向图
G 的缩合图 C。节点标签是 G 的强连通分量列表中组件索引的整数。C 有一个名为 'mapping' 的图属性，包含一个字典，将原始节点映射到它们所属的 C 中的节点。C 中的每个节点还有一个 'members' 节点属性，包含形成该节点所代表的强连通分量的原始节点集合。
Raises
------
NetworkXNotImplemented
如果 G 是无向图。
Examples
--------
将两个强连通节点集合收缩为两个不同的强连通分量，使用杠铃图。
>>> G = nx.barbell_graph(4, 0)
>>> G.remove_edge(3, 4)
>>> G = nx.DiGraph(G)
>>> H = nx.condensation(G)
>>> H.nodes.data()
NodeDataView({0: {'members': {0, 1, 2, 3}}, 1: {'members': {4, 5, 6, 7}}})
>>> H.graph["mapping"]
{0: 0, 1: 0, 2: 0, 3: 0, 4: 1, 5: 1, 6: 1, 7: 1}
将一个完全图收缩为一个单一的强连通分量。
>>> G = nx.complete_graph(7, create_using=nx.DiGraph)
>>> H = nx.condensation(G)
>>> H.nodes
NodeView((0,))
>>> H.nodes.data()
NodeDataView({0: {'members': {0, 1, 2, 3, 4, 5, 6}}})
Notes
-----
将所有强连通分量收缩为一个节点后，生成的图是一个有向无环图。
"""
if scc is None:
scc = nx.strongly_connected_components(G)
mapping = {}
members = {}
C = nx.DiGraph()
# Add mapping dict as graph attribute
C.graph["mapping"] = mapping
if len(G) == 0:
return C
for i, component in enumerate(scc):
members[i] = component
mapping.update((n, i) for n in component)
number_of_components = i + 1
C.add_nodes_from(range(number_of_components))
C.add_edges_from(
(mapping[u], mapping[v]) for u, v in G.edges() if mapping[u] != mapping[v]
)
# Add a list of members (ie original nodes) to each node (ie scc) in C.
nx.set_node_attributes(C, members, "members")
return C
