diff options
| -rw-r--r-- | doc/release/release_dev.rst | 4 | ||||
| -rw-r--r-- | networkx/algorithms/components/semiconnected.py | 23 |
2 files changed, 18 insertions, 9 deletions
diff --git a/doc/release/release_dev.rst b/doc/release/release_dev.rst index 36021135..45084a9a 100644 --- a/doc/release/release_dev.rst +++ b/doc/release/release_dev.rst @@ -29,6 +29,10 @@ Improvements API Changes ----------- +- [`#6651 <https://github.com/networkx/networkx/pull/6651>`_] + In `is_semiconnected`, the keyword argument `topo_order` has been removed. + That argument resulted in silently incorrect results more often than not. + Deprecations diff --git a/networkx/algorithms/components/semiconnected.py b/networkx/algorithms/components/semiconnected.py index 9603f9d0..aab66619 100644 --- a/networkx/algorithms/components/semiconnected.py +++ b/networkx/algorithms/components/semiconnected.py @@ -6,20 +6,27 @@ __all__ = ["is_semiconnected"] @not_implemented_for("undirected") -def is_semiconnected(G, topo_order=None): +def is_semiconnected(G): """Returns True if the graph is semiconnected, False otherwise. - A graph is semiconnected if, and only if, for any pair of nodes, either one + A graph is semiconnected if and only if for any pair of nodes, either one is reachable from the other, or they are mutually reachable. + This function uses a theorem that states that a DAG is semiconnected + if for any topological sort, for node $v_n$ in that sort, there is an + edge $(v_i, v_{i+1})$. That allows us to check if a non-DAG `G` is + semiconnected by condensing the graph: i.e. constructing a new graph `H` + with nodes being the strongly connected components of `G`, and edges + (scc_1, scc_2) if there is a edge $(v_1, v_2)$ in `G` for some + $v_1 \in scc_1$ and $v_2 \in scc_2$. That results in a DAG, so we compute + the topological sort of `H` and check if for every $n$ there is an edge + $(scc_n, scc_{n+1})$. + Parameters ---------- G : NetworkX graph A directed graph. - topo_order: list or tuple, optional - A topological order for G (if None, the function will compute one) - Returns ------- semiconnected : bool @@ -57,8 +64,6 @@ def is_semiconnected(G, topo_order=None): if not nx.is_weakly_connected(G): return False - G = nx.condensation(G) - if topo_order is None: - topo_order = nx.topological_sort(G) + H = nx.condensation(G) - return all(G.has_edge(u, v) for u, v in pairwise(topo_order)) + return all(H.has_edge(u, v) for u, v in pairwise(nx.topological_sort(H))) |