Remove `topo_order` kwarg from `is_semiconnected` without deprecation. (#6651)

* Remove topo_order kwarg without deprecation.

* Add release note about semiconnected removing the topo_order kwarg.

* Add to doc_string the method used to find semiconnected

---------

Co-authored-by: Dan Schult <dschult@colgate.edu>

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)))