is_strongly_connected

is_strongly_connected(G)

Decides whether the given tournament is strongly connected.

This function is more theoretically efficient than the is_strongly_connected() function.

The given graph must be a tournament, otherwise this function’s behavior is undefined.

Parameters:

GNetworkX graph

A directed graph representing a tournament.

Returns:

bool

Whether the tournament is strongly connected.

Notes

Although this function is more theoretically efficient than the generic strong connectivity function, a speedup requires the use of parallelism. Though it may in the future, the current implementation does not use parallelism, thus you may not see much of a speedup.

This algorithm comes from [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

parallelA networkx backend that uses joblib to run graph algorithms in parallel. Find the nx-parallel’s configuration guide here

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_jobs number of chunks.

[Source]