[New-bugs-announce] [issue17005] Add a topological sort algorithm

Raymond Hettinger report at bugs.python.org
Sun Jan 20 22:39:12 CET 2013

New submission from Raymond Hettinger:

I suggest adding a topological sort algorithm to the standard library.

In addition to being a fundamental algorithm, it is immediately useful in demonstrating how the MRO computation works and for pure Python implementations of MRO logic.   IIRC, the pgen code was also expressed in pure Python for the same reason.

I've attached a first-draft of the algorithm and an alternative that only implements a topological merge.  This is just an early draft and there are a number of open points:

* which module to put it in
* a better implementation may be possible (perhaps using fewer dictionaries and sets).

files: mro_merge.py
messages: 180319
nosy: rhettinger
priority: low
severity: normal
status: open
title: Add a topological sort algorithm
type: enhancement
versions: Python 3.4
Added file: http://bugs.python.org/file28800/mro_merge.py

Python tracker <report at bugs.python.org>

More information about the New-bugs-announce mailing list