[issue17005] Add a topological sort algorithm

[Pablo Galindo Salgado]

Pablo Galindo Salgado <pablogsal at gmail.com> added the comment:

> * allow input as ordered pairs like the Unix tsort command
> * allow more convenient input as dependency sequences (like graphviz):

This is how my first proposal started (and I still like it a bit more than the dictionary input), but there are some concerns (check other comments) regarding this API, like representing isolated nodes or disjoint graphs.

> return both the sorted sequence and cycles

Regarding the output, I like returning a collection of sets, where every set represents all possible elements of the same order in the result. This also helps if the user has some expectation regarding the ordering. For example, in:

['ABDGI', 'BEG', 'CEH', 'KCFHJ']

the results starting with

['A', 'B', 'D'

and

['A', 'B', 'K'

are both valid.

With the current implementation, this is the equivalent of C3 linearization:

      from itertools import tee
      from collections import defaultdict
      def c3_linearization(inheritance_seqs):
         graph = defaultdict(set)
         for seq in inheritance_seqs:
             a, b = tee(seq)
             next(b, None)
             for child, parent in zip(a,b):
                 graph[child].add(parent)
         retun ((list(group) for group in functools.toposort(graph)), [])
         return tuple(reversed(order))

      >>> class A: pass
      >>> class B(A): pass
      >>> class C(A): pass
      >>> class D(B, C): pass

       >> D.__mro__
      (__main__.D, __main__.B, __main__.C, __main__.A, object)

       >> c3_linearization([(D, B, A, object), (D, C, A, object)])
      [{__main__.D}, {__main__.B, __main__.C}, {__main__.A}, {object}]

What do you think?

----------

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