bpo-17005: Move topological sort functionality to its own module (GH-20558)

The topological sort functionality that was introduced initially in the
functools module has been moved to a new graphlib module to
better accommodate the new tools and keep the original scope of the
functools module. 

1 files changed, 1 insertions, 270 deletions

diff --git a/Lib/test/test_functools.py b/Lib/test/test_functools.py
index 72b7765..e726188 100644
--- a/Lib/test/test_functools.py
+++ b/Lib/test/test_functools.py
@@ -3,7 +3,7 @@ import builtins
 import collections
 import collections.abc
 import copy
-from itertools import permutations, chain
+from itertools import permutations
 import pickle
 from random import choice
 import sys
@@ -1164,275 +1164,6 @@ class Orderable_LT:
         return self.value == other.value
 
 
-class TestTopologicalSort(unittest.TestCase):
-
-    def _test_graph(self, graph, expected):
-
-        def static_order_with_groups(ts):
-            ts.prepare()
-            while ts.is_active():
-                nodes = ts.get_ready()
-                for node in nodes:
-                    ts.done(node)
-                yield nodes
-
-        ts = functools.TopologicalSorter(graph)
-        self.assertEqual(list(static_order_with_groups(ts)), list(expected))
-
-        ts = functools.TopologicalSorter(graph)
-        self.assertEqual(list(ts.static_order()), list(chain(*expected)))
-
-    def _assert_cycle(self, graph, cycle):
-        ts = functools.TopologicalSorter()
-        for node, dependson in graph.items():
-            ts.add(node, *dependson)
-        try:
-            ts.prepare()
-        except functools.CycleError as e:
-            msg, seq = e.args
-            self.assertIn(' '.join(map(str, cycle)),
-                          ' '.join(map(str, seq * 2)))
-        else:
-            raise
-
-    def test_simple_cases(self):
-        self._test_graph(
-            {2: {11},
-             9: {11, 8},
-             10: {11, 3},
-             11: {7, 5},
-             8: {7, 3}},
-            [(3, 5, 7), (11, 8), (2, 10, 9)]
-        )
-
-        self._test_graph({1: {}}, [(1,)])
-
-        self._test_graph({x: {x+1} for x in range(10)},
-                         [(x,) for x in range(10, -1, -1)])
-
-        self._test_graph({2: {3}, 3: {4}, 4: {5}, 5: {1},
-                          11: {12}, 12: {13}, 13: {14}, 14: {15}},
-                         [(1, 15), (5, 14), (4, 13), (3, 12), (2, 11)])
-
-        self._test_graph({
-                0: [1, 2],
-                1: [3],
-                2: [5, 6],
-                3: [4],
-                4: [9],
-                5: [3],
-                6: [7],
-                7: [8],
-                8: [4],
-                9: []
-            },
-            [(9,), (4,), (3, 8), (1, 5, 7), (6,), (2,), (0,)]
-        )
-
-        self._test_graph({
-                0: [1, 2],
-                1: [],
-                2: [3],
-                3: []
-            },
-            [(1, 3), (2,), (0,)]
-        )
-
-        self._test_graph({
-                0: [1, 2],
-                1: [],
-                2: [3],
-                3: [],
-                4: [5],
-                5: [6],
-                6: []
-            },
-            [(1, 3, 6), (2, 5), (0, 4)]
-        )
-
-    def test_no_dependencies(self):
-        self._test_graph(
-            {1: {2},
-             3: {4},
-             5: {6}},
-            [(2, 4, 6), (1, 3, 5)]
-        )
-
-        self._test_graph(
-            {1: set(),
-             3: set(),
-             5: set()},
-            [(1, 3, 5)]
-        )
-
-    def test_the_node_multiple_times(self):
-        # Test same node multiple times in dependencies
-        self._test_graph({1: {2}, 3: {4}, 0: [2, 4, 4, 4, 4, 4]},
-                         [(2, 4), (1, 3, 0)])
-
-        # Test adding the same dependency multiple times
-        ts = functools.TopologicalSorter()
-        ts.add(1, 2)
-        ts.add(1, 2)
-        ts.add(1, 2)
-        self.assertEqual([*ts.static_order()], [2, 1])
-
-    def test_graph_with_iterables(self):
-        dependson = (2*x + 1 for x in range(5))
-        ts = functools.TopologicalSorter({0: dependson})
-        self.assertEqual(list(ts.static_order()), [1, 3, 5, 7, 9, 0])
-
-    def test_add_dependencies_for_same_node_incrementally(self):
-        # Test same node multiple times
-        ts = functools.TopologicalSorter()
-        ts.add(1, 2)
-        ts.add(1, 3)
-        ts.add(1, 4)
-        ts.add(1, 5)
-
-        ts2 = functools.TopologicalSorter({1: {2, 3, 4, 5}})
-        self.assertEqual([*ts.static_order()], [*ts2.static_order()])
-
-    def test_empty(self):
-        self._test_graph({}, [])
-
-    def test_cycle(self):
-        # Self cycle
-        self._assert_cycle({1: {1}}, [1, 1])
-        # Simple cycle
-        self._assert_cycle({1: {2}, 2: {1}}, [1, 2, 1])
-        # Indirect cycle
-        self._assert_cycle({1: {2}, 2: {3}, 3: {1}}, [1, 3, 2, 1])
-        # not all elements involved in a cycle
-        self._assert_cycle({1: {2}, 2: {3}, 3: {1}, 5: {4}, 4: {6}}, [1, 3, 2, 1])
-        # Multiple cycles
-        self._assert_cycle({1: {2}, 2: {1}, 3: {4}, 4: {5}, 6: {7}, 7: {6}},
-                           [1, 2, 1])
-        # Cycle in the middle of the graph
-        self._assert_cycle({1: {2}, 2: {3}, 3: {2, 4}, 4: {5}}, [3, 2])
-
-    def test_calls_before_prepare(self):
-        ts = functools.TopologicalSorter()
-
-        with self.assertRaisesRegex(ValueError, r"prepare\(\) must be called first"):
-            ts.get_ready()
-        with self.assertRaisesRegex(ValueError, r"prepare\(\) must be called first"):
-            ts.done(3)
-        with self.assertRaisesRegex(ValueError, r"prepare\(\) must be called first"):
-            ts.is_active()
-
-    def test_prepare_multiple_times(self):
-        ts = functools.TopologicalSorter()
-        ts.prepare()
-        with self.assertRaisesRegex(ValueError, r"cannot prepare\(\) more than once"):
-            ts.prepare()
-
-    def test_invalid_nodes_in_done(self):
-        ts = functools.TopologicalSorter()
-        ts.add(1, 2, 3, 4)
-        ts.add(2, 3, 4)
-        ts.prepare()
-        ts.get_ready()
-
-        with self.assertRaisesRegex(ValueError, "node 2 was not passed out"):
-            ts.done(2)
-        with self.assertRaisesRegex(ValueError, r"node 24 was not added using add\(\)"):
-            ts.done(24)
-
-    def test_done(self):
-        ts = functools.TopologicalSorter()
-        ts.add(1, 2, 3, 4)
-        ts.add(2, 3)
-        ts.prepare()
-
-        self.assertEqual(ts.get_ready(), (3, 4))
-        # If we don't mark anything as done, get_ready() returns nothing
-        self.assertEqual(ts.get_ready(), ())
-        ts.done(3)
-        # Now 2 becomes available as 3 is done
-        self.assertEqual(ts.get_ready(), (2,))
-        self.assertEqual(ts.get_ready(), ())
-        ts.done(4)
-        ts.done(2)
-        # Only 1 is missing
-        self.assertEqual(ts.get_ready(), (1,))
-        self.assertEqual(ts.get_ready(), ())
-        ts.done(1)
-        self.assertEqual(ts.get_ready(), ())
-        self.assertFalse(ts.is_active())
-
-    def test_is_active(self):
-        ts = functools.TopologicalSorter()
-        ts.add(1, 2)
-        ts.prepare()
-
-        self.assertTrue(ts.is_active())
-        self.assertEqual(ts.get_ready(), (2,))
-        self.assertTrue(ts.is_active())
-        ts.done(2)
-        self.assertTrue(ts.is_active())
-        self.assertEqual(ts.get_ready(), (1,))
-        self.assertTrue(ts.is_active())
-        ts.done(1)
-        self.assertFalse(ts.is_active())
-
-    def test_not_hashable_nodes(self):
-        ts = functools.TopologicalSorter()
-        self.assertRaises(TypeError, ts.add, dict(), 1)
-        self.assertRaises(TypeError, ts.add, 1, dict())
-        self.assertRaises(TypeError, ts.add, dict(), dict())
-
-    def test_order_of_insertion_does_not_matter_between_groups(self):
-        def get_groups(ts):
-            ts.prepare()
-            while ts.is_active():
-                nodes = ts.get_ready()
-                ts.done(*nodes)
-                yield set(nodes)
-
-        ts = functools.TopologicalSorter()
-        ts.add(3, 2, 1)
-        ts.add(1, 0)
-        ts.add(4, 5)
-        ts.add(6, 7)
-        ts.add(4, 7)
-
-        ts2 = functools.TopologicalSorter()
-        ts2.add(1, 0)
-        ts2.add(3, 2, 1)
-        ts2.add(4, 7)
-        ts2.add(6, 7)
-        ts2.add(4, 5)
-
-        self.assertEqual(list(get_groups(ts)), list(get_groups(ts2)))
-
-    def test_static_order_does_not_change_with_the_hash_seed(self):
-        def check_order_with_hash_seed(seed):
-            code = """if 1:
-                import functools
-                ts = functools.TopologicalSorter()
-                ts.add('blech', 'bluch', 'hola')
-                ts.add('abcd', 'blech', 'bluch', 'a', 'b')
-                ts.add('a', 'a string', 'something', 'b')
-                ts.add('bluch', 'hola', 'abcde', 'a', 'b')
-                print(list(ts.static_order()))
-                """
-            env = os.environ.copy()
-            # signal to assert_python not to do a copy
-            # of os.environ on its own
-            env['__cleanenv'] = True
-            env['PYTHONHASHSEED'] = str(seed)
-            out = assert_python_ok('-c', code, **env)
-            return out
-
-        run1 = check_order_with_hash_seed(1234)
-        run2 = check_order_with_hash_seed(31415)
-
-        self.assertNotEqual(run1, "")
-        self.assertNotEqual(run2, "")
-        self.assertEqual(run1, run2)
-
-
 class TestCache:
     # This tests that the pass-through is working as designed.
     # The underlying functionality is tested in TestLRU.