Linear prufer coding (#3535)

* unnecessary scanning of entire range

* wrong run time in documentation

1 files changed, 6 insertions, 6 deletions

diff --git a/networkx/algorithms/tree/coding.py b/networkx/algorithms/tree/coding.py
index e77841cd..30c44fb4 100644
--- a/networkx/algorithms/tree/coding.py
+++ b/networkx/algorithms/tree/coding.py
@@ -258,7 +258,7 @@ def to_prufer_sequence(T):
     relabel the nodes of your tree to the appropriate format.
 
     This implementation is from [1]_ and has a running time of
-    $O(n \log n)$.
+    $O(n)$.
 
     See also
     --------
@@ -303,7 +303,7 @@ def to_prufer_sequence(T):
     def parents(u):
         return next(v for v in T[u] if degree[v] > 1)
 
-    index = u = min(k for k in range(n) if degree[k] == 1)
+    index = u = next(k for k in range(n) if degree[k] == 1)
     result = []
     for i in range(n - 2):
         v = parents(u)
@@ -312,7 +312,7 @@ def to_prufer_sequence(T):
         if v < index and degree[v] == 1:
             u = v
         else:
-            index = u = min(k for k in range(index + 1, n) if degree[k] == 1)
+            index = u = next(k for k in range(index + 1, n) if degree[k] == 1)
     return result
 
 
@@ -347,7 +347,7 @@ def from_prufer_sequence(sequence):
     relabel the nodes of your tree to the appropriate format.
 
     This implementation is from [1]_ and has a running time of
-    $O(n \log n)$.
+    $O(n)$.
 
     References
     ----------
@@ -387,7 +387,7 @@ def from_prufer_sequence(sequence):
     # tree. After the loop, there should be exactly two nodes that are
     # not in this set.
     not_orphaned = set()
-    index = u = min(k for k in range(n) if degree[k] == 1)
+    index = u = next(k for k in range(n) if degree[k] == 1)
     for v in sequence:
         T.add_edge(u, v)
         not_orphaned.add(u)
@@ -395,7 +395,7 @@ def from_prufer_sequence(sequence):
         if v < index and degree[v] == 1:
             u = v
         else:
-            index = u = min(k for k in range(index + 1, n) if degree[k] == 1)
+            index = u = next(k for k in range(index + 1, n) if degree[k] == 1)
     # At this point, there must be exactly two orphaned nodes; join them.
     orphans = set(T) - not_orphaned
     u, v = orphans