[issue17005] Add a topological sort algorithm

[Gareth Rees]

Gareth Rees <gdr at garethrees.org> added the comment:

I approve in general with the principle of including a topological sort algorithm in the standard library. However, I have three problems with the approach in PR 11583:

1. The name "topsort" is most naturally parsed as "top sort" which could be misinterpreted (as a sort that puts items on top in some way). If the name must be abbreviated then "toposort" would be better.

2. "Topological sort" is a terrible name: the analogy with topological graph theory is (i) unlikely to be helpful to anyone; and (ii) not quite right. I know that the name is widely used in computing, but a name incorporating "linearize" or "linear order" or "total order" would be much clearer.

3. The proposed interface is not suitable for all cases! The function topsort takes a list of directed edges and returns a linear order on the vertices in those edges (if any linear order exists). But this means that if there are any isolated vertices (that is, vertices with no edges) in the dependency graph, then there is no way of passing those vertices to the function. This means that (i) it is inconvenient to use the proposed interface because you have to find the isolated vertices in your graph and add them to the linear order after calling the function; (ii) it is a bug magnet because many programmers will omit this step, meaning that their code will unexpectedly fail when their graph has an isolated vertex. The interface needs to be redesigned to take the graph in some other representation.

----------
nosy: +gdr at garethrees.org

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