Pablo Galindo Salgado <pablog...@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 <rep...@bugs.python.org>
<https://bugs.python.org/issue17005>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
