added topo_order parameter to functions that rely on topological_sort (#3447)

Fixes #3446

2 files changed, 28 insertions, 7 deletions

diff --git a/networkx/algorithms/components/semiconnected.py b/networkx/algorithms/components/semiconnected.py
index a89c82de..8170221b 100644
--- a/networkx/algorithms/components/semiconnected.py
+++ b/networkx/algorithms/components/semiconnected.py
@@ -15,7 +15,7 @@ __all__ = ['is_semiconnected']
 
 
 @not_implemented_for('undirected')
-def is_semiconnected(G):
+def is_semiconnected(G, topo_order=None):
     """Returns True if the graph is semiconnected, False otherwise.
 
     A graph is semiconnected if, and only if, for any pair of nodes, either one
@@ -26,6 +26,9 @@ def is_semiconnected(G):
     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
@@ -63,5 +66,7 @@ def is_semiconnected(G):
         return False
 
     G = nx.condensation(G)
-    path = nx.topological_sort(G)
-    return all(G.has_edge(u, v) for u, v in pairwise(path))
+    if topo_order is None:
+        topo_order = nx.topological_sort(G)
+
+    return all(G.has_edge(u, v) for u, v in pairwise(topo_order))
diff --git a/networkx/algorithms/dag.py b/networkx/algorithms/dag.py
index 4a3a1baf..c91896cd 100644
--- a/networkx/algorithms/dag.py
+++ b/networkx/algorithms/dag.py
@@ -562,7 +562,7 @@ def transitive_reduction(G):
 
 
 @not_implemented_for('undirected')
-def antichains(G):
+def antichains(G, topo_order=None):
     """Generates antichains from a directed acyclic graph (DAG).
 
     An antichain is a subset of a partially ordered set such that any
@@ -573,6 +573,9 @@ def antichains(G):
     G : NetworkX DiGraph
         A directed acyclic graph (DAG)
 
+    topo_order: list or tuple, optional
+        A topological order for G (if None, the function will compute one)
+
     Returns
     -------
     generator object
@@ -598,8 +601,11 @@ def antichains(G):
     .. [1] Free Lattices, by R. Freese, J. Jezek and J. B. Nation,
        AMS, Vol 42, 1995, p. 226.
     """
+    if topo_order is None:
+        topo_order = nx.topological_sort(G)
+
     TC = nx.transitive_closure(G)
-    antichains_stacks = [([], list(reversed(list(nx.topological_sort(G)))))]
+    antichains_stacks = [([], list(topo_order)[-1::-1])]
     while antichains_stacks:
         (antichain, stack) = antichains_stacks.pop()
         # Invariant:
@@ -615,7 +621,7 @@ def antichains(G):
 
 
 @not_implemented_for('undirected')
-def dag_longest_path(G, weight='weight', default_weight=1):
+def dag_longest_path(G, weight='weight', default_weight=1, topo_order=None):
     """Returns the longest path in a directed acyclic graph (DAG).
 
     If `G` has edges with `weight` attribute the edge data are used as
@@ -632,6 +638,9 @@ def dag_longest_path(G, weight='weight', default_weight=1):
     default_weight : int, optional
         The weight of edges that do not have a weight attribute
 
+    topo_order: list or tuple, optional
+        A topological order for G (if None, the function will compute one)
+
     Returns
     -------
     list
@@ -649,14 +658,20 @@ def dag_longest_path(G, weight='weight', default_weight=1):
     """
     if not G:
         return []
+
+    if topo_order is None:
+        topo_order = nx.topological_sort(G)
+
     dist = {}  # stores {v : (length, u)}
-    for v in nx.topological_sort(G):
+    for v in topo_order:
         us = [(dist[u][0] + data.get(weight, default_weight), u)
               for u, data in G.pred[v].items()]
+
         # Use the best predecessor if there is one and its distance is
         # non-negative, otherwise terminate.
         maxu = max(us, key=lambda x: x[0]) if us else (0, v)
         dist[v] = maxu if maxu[0] >= 0 else (0, v)
+
     u = None
     v = max(dist, key=lambda x: dist[x][0])
     path = []
@@ -664,6 +679,7 @@ def dag_longest_path(G, weight='weight', default_weight=1):
         path.append(v)
         u = v
         v = dist[v][1]
+
     path.reverse()
     return path