[issue17005] Add a topological sort algorithm

[Zahari Dim]

Zahari Dim <zaharid at gmail.com> added the comment:

I would like to suggest a `dependency_resolver` API that I have been using that goes in line with what Tim Peters proposes in https://bugs.python.org/issue17005#msg359702

A DAG would be an object that can be iterated in topological order with __iter__ (for simple sequential usage) or have a way of managing all the tasks that can be run in parallel. The later is done with a generator function:

```
    def dependency_resolver(self):
        """Yield the set of nodes that have all dependencies satisfied (which could be an empty set). Send the next
        completed task."""
```

which is used with something like:

```
deps = dag.dependency_resolver()
pending_tasks = deps.send(None)
if not pending_tasks:
    #Graph empty
    return
#Note this is a can be done in parallel/async
while True:
    some_task = pending_tasks.pop()
    complete_task_somehow(some_task)
    try:
       more_tasks = deps.send(some_task)
    except StopIteration:
       #Exit when we have sent in all the nodes in the graph
       break
    else:
        pending_tasks |= more_tasks

```


An implementation I have used for some time is here:


https://github.com/NNPDF/reportengine/blob/master/src/reportengine/dag.py

although I'd make simpler now. In practice I have found that the function I use most of the time to build the graph is:

dag.add_or_update_node(node=something_hashable, inputs={set of existing nodes}, outputs={set of existing nodes}).

which adds the node to the graph if it was not there and maps updates the dependencies to add inputs and outputs, which in my experience matches the way one discovers dependencies for things like packages.

----------
nosy: +Zahari.Dim

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue17005>
_______________________________________