is_strongly_connected#

is_strongly_connected(G)[source]#

确定给定的比赛图是否是强连通的。

此函数在理论上的效率高于 is_strongly_connected() 函数。

给定的图必须是一个比赛图，否则此函数的行为是未定义的。

Parameters:

GNetworkX 图: 一个表示比赛图的有向图。

Returns:

bool: 比赛图是否是强连通的。

Notes

尽管此函数在理论上的效率高于通用的强连通性函数，但加速需要使用并行性。虽然将来可能会实现，但当前的实现并未使用并行性，因此您可能看不到太多的加速。

此算法来自 [1]。

References

[1]

Tantau, Till. “A note on the complexity of the reachability problem for tournaments.” Electronic Colloquium on Computational Complexity. 2001. <http://eccc.hpi-web.de/report/2001/092/>

Examples

>>> G = nx.DiGraph([(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 0)])
>>> nx.is_tournament(G)
True
>>> nx.tournament.is_strongly_connected(G)
True
>>> G.remove_edge(3, 0)
>>> G.add_edge(0, 3)
>>> nx.is_tournament(G)
True
>>> nx.tournament.is_strongly_connected(G)
False

Additional backends implement this function

parallelParallel backend for NetworkX algorithms

The parallel computation is implemented by dividing the nodes into chunks and then checking whether each node is reachable from each other node in parallel.

Additional parameters:

get_chunksstr, function (default = “chunks”): A function that takes in a list of all the nodes as input and returns an iterable node_chunks. The default chunking is done by slicing the nodes into n chunks, where n is the total number of CPU cores available.

[Source]