Author pablogsal
Recipients belopolsky, christian.heimes, eric.smith, gdr@garethrees.org, martin.panter, pablogsal, remi.lapeyre, rhettinger, terry.reedy, tshepang
Date 2019-05-26.23:27:30
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1558913250.91.0.165863756928.issue17005@roundup.psfhosted.org>
In-reply-to
Content
> * 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?
History
Date User Action Args
2019-05-26 23:27:30pablogsalsetrecipients: + pablogsal, rhettinger, terry.reedy, belopolsky, eric.smith, christian.heimes, tshepang, gdr@garethrees.org, martin.panter, remi.lapeyre
2019-05-26 23:27:30pablogsalsetmessageid: <1558913250.91.0.165863756928.issue17005@roundup.psfhosted.org>
2019-05-26 23:27:30pablogsallinkissue17005 messages
2019-05-26 23:27:30pablogsalcreate