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.
diff --git a/Doc/library/graphlib.rst b/Doc/library/graphlib.rst
new file mode 100644
index 0000000..820615e
--- /dev/null
+++ b/Doc/library/graphlib.rst
@@ -0,0 +1,209 @@
+:mod:`graphlib` --- Functionality to operate with graph-like structures
+=========================================================================
+
+.. module:: graphlib
+ :synopsis: Functionality to operate with graph-like structures
+
+
+**Source code:** :source:`Lib/graphlib.py`
+
+.. testsetup:: default
+
+ import graphlib
+ from graphlib import *
+
+--------------
+
+
+.. class:: TopologicalSorter(graph=None)
+
+ Provides functionality to topologically sort a graph of hashable nodes.
+
+ A topological order is a linear ordering of the vertices in a graph such that
+ for every directed edge u -> v from vertex u to vertex v, vertex u comes
+ before vertex v in the ordering. For instance, the vertices of the graph may
+ represent tasks to be performed, and the edges may represent constraints that
+ one task must be performed before another; in this example, a topological
+ ordering is just a valid sequence for the tasks. A complete topological
+ ordering is possible if and only if the graph has no directed cycles, that
+ is, if it is a directed acyclic graph.
+
+ If the optional *graph* argument is provided it must be a dictionary
+ representing a directed acyclic graph where the keys are nodes and the values
+ are iterables of all predecessors of that node in the graph (the nodes that
+ have edges that point to the value in the key). Additional nodes can be added
+ to the graph using the :meth:`~TopologicalSorter.add` method.
+
+ In the general case, the steps required to perform the sorting of a given
+ graph are as follows:
+
+ * Create an instance of the :class:`TopologicalSorter` with an optional
+ initial graph.
+ * Add additional nodes to the graph.
+ * Call :meth:`~TopologicalSorter.prepare` on the graph.
+ * While :meth:`~TopologicalSorter.is_active` is ``True``, iterate over
+ the nodes returned by :meth:`~TopologicalSorter.get_ready` and
+ process them. Call :meth:`~TopologicalSorter.done` on each node as it
+ finishes processing.
+
+ In case just an immediate sorting of the nodes in the graph is required and
+ no parallelism is involved, the convenience method
+ :meth:`TopologicalSorter.static_order` can be used directly:
+
+ .. doctest::
+
+ >>> graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}}
+ >>> ts = TopologicalSorter(graph)
+ >>> tuple(ts.static_order())
+ ('A', 'C', 'B', 'D')
+
+ The class is designed to easily support parallel processing of the nodes as
+ they become ready. For instance::
+
+ topological_sorter = TopologicalSorter()
+
+ # Add nodes to 'topological_sorter'...
+
+ topological_sorter.prepare()
+ while topological_sorter.is_active():
+ for node in topological_sorter.get_ready():
+ # Worker threads or processes take nodes to work on off the
+ # 'task_queue' queue.
+ task_queue.put(node)
+
+ # When the work for a node is done, workers put the node in
+ # 'finalized_tasks_queue' so we can get more nodes to work on.
+ # The definition of 'is_active()' guarantees that, at this point, at
+ # least one node has been placed on 'task_queue' that hasn't yet
+ # been passed to 'done()', so this blocking 'get()' must (eventually)
+ # succeed. After calling 'done()', we loop back to call 'get_ready()'
+ # again, so put newly freed nodes on 'task_queue' as soon as
+ # logically possible.
+ node = finalized_tasks_queue.get()
+ topological_sorter.done(node)
+
+ .. method:: add(node, *predecessors)
+
+ Add a new node and its predecessors to the graph. Both the *node* and all
+ elements in *predecessors* must be hashable.
+
+ If called multiple times with the same node argument, the set of
+ dependencies will be the union of all dependencies passed in.
+
+ It is possible to add a node with no dependencies (*predecessors* is not
+ provided) or to provide a dependency twice. If a node that has not been
+ provided before is included among *predecessors* it will be automatically
+ added to the graph with no predecessors of its own.
+
+ Raises :exc:`ValueError` if called after :meth:`~TopologicalSorter.prepare`.
+
+ .. method:: prepare()
+
+ Mark the graph as finished and check for cycles in the graph. If any cycle
+ is detected, :exc:`CycleError` will be raised, but
+ :meth:`~TopologicalSorter.get_ready` can still be used to obtain as many
+ nodes as possible until cycles block more progress. After a call to this
+ function, the graph cannot be modified, and therefore no more nodes can be
+ added using :meth:`~TopologicalSorter.add`.
+
+ .. method:: is_active()
+
+ Returns ``True`` if more progress can be made and ``False`` otherwise.
+ Progress can be made if cycles do not block the resolution and either
+ there are still nodes ready that haven't yet been returned by
+ :meth:`TopologicalSorter.get_ready` or the number of nodes marked
+ :meth:`TopologicalSorter.done` is less than the number that have been
+ returned by :meth:`TopologicalSorter.get_ready`.
+
+ The :meth:`~TopologicalSorter.__bool__` method of this class defers to
+ this function, so instead of::
+
+ if ts.is_active():
+ ...
+
+ if possible to simply do::
+
+ if ts:
+ ...
+
+ Raises :exc:`ValueError` if called without calling
+ :meth:`~TopologicalSorter.prepare` previously.
+
+ .. method:: done(*nodes)
+
+ Marks a set of nodes returned by :meth:`TopologicalSorter.get_ready` as
+ processed, unblocking any successor of each node in *nodes* for being
+ returned in the future by a call to :meth:`TopologicalSorter.get_ready`.
+
+ Raises :exc:`ValueError` if any node in *nodes* has already been marked as
+ processed by a previous call to this method or if a node was not added to
+ the graph by using :meth:`TopologicalSorter.add`, if called without
+ calling :meth:`~TopologicalSorter.prepare` or if node has not yet been
+ returned by :meth:`~TopologicalSorter.get_ready`.
+
+ .. method:: get_ready()
+
+ Returns a ``tuple`` with all the nodes that are ready. Initially it
+ returns all nodes with no predecessors, and once those are marked as
+ processed by calling :meth:`TopologicalSorter.done`, further calls will
+ return all new nodes that have all their predecessors already processed.
+ Once no more progress can be made, empty tuples are returned.
+
+ Raises :exc:`ValueError` if called without calling
+ :meth:`~TopologicalSorter.prepare` previously.
+
+ .. method:: static_order()
+
+ Returns an iterable of nodes in a topological order. Using this method
+ does not require to call :meth:`TopologicalSorter.prepare` or
+ :meth:`TopologicalSorter.done`. This method is equivalent to::
+
+ def static_order(self):
+ self.prepare()
+ while self.is_active():
+ node_group = self.get_ready()
+ yield from node_group
+ self.done(*node_group)
+
+ The particular order that is returned may depend on the specific order in
+ which the items were inserted in the graph. For example:
+
+ .. doctest::
+
+ >>> ts = TopologicalSorter()
+ >>> ts.add(3, 2, 1)
+ >>> ts.add(1, 0)
+ >>> print([*ts.static_order()])
+ [2, 0, 1, 3]
+
+ >>> ts2 = TopologicalSorter()
+ >>> ts2.add(1, 0)
+ >>> ts2.add(3, 2, 1)
+ >>> print([*ts2.static_order()])
+ [0, 2, 1, 3]
+
+ This is due to the fact that "0" and "2" are in the same level in the
+ graph (they would have been returned in the same call to
+ :meth:`~TopologicalSorter.get_ready`) and the order between them is
+ determined by the order of insertion.
+
+
+ If any cycle is detected, :exc:`CycleError` will be raised.
+
+ .. versionadded:: 3.9
+
+
+Exceptions
+----------
+The :mod:`graphlib` module defines the following exception classes:
+
+.. exception:: CycleError
+
+ Subclass of :exc:`ValueError` raised by :meth:`TopologicalSorter.prepare` if cycles exist
+ in the working graph. If multiple cycles exist, only one undefined choice among them will
+ be reported and included in the exception.
+
+ The detected cycle can be accessed via the second element in the :attr:`~CycleError.args`
+ attribute of the exception instance and consists in a list of nodes, such that each node is,
+ in the graph, an immediate predecessor of the next node in the list. In the reported list,
+ the first and the last node will be the same, to make it clear that it is cyclic.
\ No newline at end of file