is_semiconnected

is_semiconnected(G)

返回 True 如果图是半连通的，否则返回 False。

一个图是半连通的当且仅当对于任意一对节点，要么其中一个可以从另一个到达，或者它们可以相互到达。

此函数使用一个定理，该定理指出一个有向无环图（DAG）是半连通的，如果在任何拓扑排序中，对于排序中的节点 \(v_n\)，存在一条边 \((v_i, v_{i+1})\)。这允许我们通过压缩图来检查非DAG图 G 是否是半连通的：即构建一个新图 H ，其节点是 G 的强连通分量，并且如果 G 中存在一条边 \((v_1, v_2)\) 对于某些 \(v_1 \in scc_1\) 和 \(v_2 \in scc_2\)，则在 H 中存在边 (scc_1, scc_2)。这结果是一个DAG，因此我们计算 H 的拓扑排序并检查对于每个 \(n\) 是否存在一条边 \((scc_n, scc_{n+1})\)。

Parameters:

GNetworkX 图

一个有向图。

Returns:

semiconnectedbool

如果图是半连通的，返回 True，否则返回 False。

Raises:

NetworkXNotImplemented

如果输入图是无向的。

NetworkXPointlessConcept

如果图是空的。

See also

is_strongly_connected

is_weakly_connected

is_connected

is_biconnected

Examples

>>> G = nx.path_graph(4, create_using=nx.DiGraph())
>>> print(nx.is_semiconnected(G))
True
>>> G = nx.DiGraph([(1, 2), (3, 2)])
>>> print(nx.is_semiconnected(G))
False