[issue17005] Add a topological sort algorithm

Éric Araujo added the comment: See https://bugs.python.org/issue46071 for request to change the API (I preferred adding a note here than adding all people to nosy there) -- nosy: +eric.araujo ___ Python tracker

[issue17005] Add a topological sort algorithm

Adrian Garcia Badaracco added the comment: As part of working on a tool that deals with dependencies, I was building my own topological sort. I iterated through various APIs (iterable of tasks, iterable of parallelizable groups of tasks, etc.) until I found the (now stdlib) version which

[issue17005] Add a topological sort algorithm

Change by Éric Araujo : -- versions: +Python 3.9 -Python 3.8 ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue17005] Add a topological sort algorithm

Change by Raymond Hettinger : -- assignee: rhettinger -> resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker ___

[issue17005] Add a topological sort algorithm

Paddy McCarthy added the comment: Please ignore my earlier Message-id <1598493715.04.0.06462575371.issue17...@roundup.psfhosted.org>. I missed a dependency in cutting down a larger example. Sorry. -- ___ Python tracker

[issue17005] Add a topological sort algorithm

Paddy McCarthy added the comment: I've been playing with Python 3.9.0rc1 and was looking at a particular graph to see when it released tasks for processing. I ran the following code: from functools import reduce from pprint import pprint as pp from collections import defaultdict from graphlib

[issue17005] Add a topological sort algorithm

miss-islington added the comment: New changeset 0a674638a3de14dc86b5294a5db067e0c2177a51 by Miss Islington (bot) in branch '3.9': bpo-17005: Move topological sort functionality to its own module (GH-20558) https://github.com/python/cpython/commit/0a674638a3de14dc86b5294a5db067e0c2177a51

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: New changeset 2f172d8f1525defe9bba4d49e967fdfc69151731 by Pablo Galindo in branch 'master': bpo-17005: Move topological sort functionality to its own module (GH-20558) https://github.com/python/cpython/commit/2f172d8f1525defe9bba4d49e967fdfc69151731

[issue17005] Add a topological sort algorithm

Change by miss-islington : -- nosy: +miss-islington nosy_count: 19.0 -> 20.0 pull_requests: +19802 pull_request: https://github.com/python/cpython/pull/20561 ___ Python tracker

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: Opened https://github.com/python/cpython/pull/20558. I have *initially* proposed "graphlib" as it feels more in-line with other stdlib module names and as Jim pointed it does not collide with anything major. Also, I have proposed this initial name to

[issue17005] Add a topological sort algorithm

Change by Pablo Galindo Salgado : -- pull_requests: +19801 pull_request: https://github.com/python/cpython/pull/20558 ___ Python tracker ___

[issue17005] Add a topological sort algorithm

Jim Fasarakis-Hilliard added the comment: Another option, `graphlib`[1], does exist on PyPI but is not maintained and currently read-only by the author. Other flavors[2][3] of the same name also don't seem to have much adoption so they shouldn't confuse if a name like `graphlib` was chosen.

[issue17005] Add a topological sort algorithm

Eric V. Smith added the comment: I'd prefer a new module just for this. As for names, I like toposort over topsort. I already have a library on PyPI named toposort. Personally, I don't have a problem with the stdlib taking over that name, and I'd just deprecate mine at 3.9, or whatever.

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: I checked and from the list of proposed names with "graph" prefixes, only "graphutils" is not colliding with something on Pypi. For the record "cslib" and "misclib" are also available but the scope of those feel much much bigger. I am going to open

[issue17005] Add a topological sort algorithm

Raymond Hettinger added the comment: I vote for it being in its own module (like difflib). That would also be a good place to put my proposed tsort() function with its simpler API. -- ___ Python tracker

[issue17005] Add a topological sort algorithm

Tim Peters added the comment: `functools` is clearly a poor place for this. `imath` would also be. `graph_stuff_probably_limited_to_a_topsort` is the only accurate name ;-) Off-the-wall possibilities include `misclib` (stuff that just doesn't fit anywhere else - yet) and `cslib` (Computer

[issue17005] Add a topological sort algorithm

Ben Mares added the comment: dependencytools? But I don't think it qualifies yet for the plural... -- ___ Python tracker ___ ___

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: I would like to hear Raymond and Tim advise on what the best name for the new module should be :) -- ___ Python tracker ___

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: > The downside I see with any graph prefixed names is the fact that it implies > a larger collection of graph operations. I don't see that an issue. In the general term is better to have a general name and discuss further improvements than just name

[issue17005] Add a topological sort algorithm

Jim Fasarakis-Hilliard added the comment: The downside I see with any graph prefixed names is the fact that it implies a larger collection of graph operations. Add that to the fact that people might be more tempted to propose many graph related algorithms/utilities to a module with the

[issue17005] Add a topological sort algorithm

gaborbernat added the comment: I like graphutils for what it's worth. -- ___ Python tracker ___ ___ Python-bugs-list mailing list

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: If we move it, I would prefer a new module that somehow makes clear the scope, something like graphutils or graphtheory or graph (although this las one will probably collide with many existing things). --

[issue17005] Add a topological sort algorithm

Jim Fasarakis-Hilliard added the comment: It does seem out of place in functools, intensified by it's odd interjection among the other functools objects. Considering heapq and bisect exist as standalone modules, the idea that topological sorting could go in its own module wouldn't be

[issue17005] Add a topological sort algorithm

Rémi Lapeyre added the comment: Could it make sense to have this in the often proposed imath module? It's integers per se but Both number theory and graph theory are part of discrete mathematics so it may feel more at home there? -- ___ Python

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: Any suggestions for the new module? I assume we can move this to a new topsort/topological_sort or similar... What do people think? -- ___ Python tracker

[issue17005] Add a topological sort algorithm

Ben Mares added the comment: It's great to have this feature in the standard library, but it really seems to clutter the functools documentation. Everything else in functools applies directly to functions and methods. Suddenly reading graph theory terminology was disorienting for me. (Due

[issue17005] Add a topological sort algorithm

Raymond Hettinger added the comment: How about I post a PR so we can talk about something concrete. Then you two can either fight it to its death or you can join me in making it is good as possible, hopefully the latter :-) I am not happy with the current API but do accept that both of you

[issue17005] Add a topological sort algorithm

Change by Raymond Hettinger : -- Removed message: https://bugs.python.org/msg365640 ___ Python tracker ___ ___ Python-bugs-list

[issue17005] Add a topological sort algorithm

Raymond Hettinger added the comment: How about I post a PR so we can talk about something concrete. Then you two can either fight it to its death or you can join me in making it is good as possible, hopefully the latter :-) I am not happy with the current API but do accept that both of you

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: Is also notable to mention that you can also provide the graph as a dictionary to the constructor: >>> graph = {D: {B, C}, C: {A}, B: {A}, A:{object}} >>> ts = TopologicalSorter(graph) -- ___ Python

[issue17005] Add a topological sort algorithm

Tim Peters added the comment: Possibly, sure. But I believe it's hard to beat add(node, *predecessors) for usability as a way to build the dependency graph. For example, a list of pairs is a comparative PITA for most use cases I've had. Whether it's following a recipe to bake a

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: > We may need two versions then, a full-featured TopologicalSorter() class and > a simple tsort() function that doesn't aspire to be all things to all people. How this other version would differ from using .add() + .static_order() as Tim mentions?

[issue17005] Add a topological sort algorithm

Raymond Hettinger added the comment: > If your alternative isn't equally easy to use in a parallelized > context, I'll be at best +0. We may need two versions then, a full-featured TopologicalSorter() class and a simple tsort() function that doesn't aspire to be all things to all people.

[issue17005] Add a topological sort algorithm

Change by STINNER Victor : -- nosy: +vstinner ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: I just want to echo what Tim mentioned with the extra data point that some of the maintainers of some popular and wide-used open-source libraries that indeed have to deal with this problem or the parallel version of the problem (like gaborbernat in

[issue17005] Add a topological sort algorithm

Tim Peters added the comment: Raymond, what application do you have that wouldn't be completely addressed by sticking to just .add() (to record dependencies) and .static_order() (to retrieve a linear order)? Larry Hastings and I originally worked out the fancier bits of the interface to

[issue17005] Add a topological sort algorithm

Raymond Hettinger added the comment: At some point in the next two or three weeks, I'll have a chance to work on this more and to offer a competing patch. IMO, the current checkin is over-engineered, both in its API and implementation. This could have been a simple, fast tool written as

[issue17005] Add a topological sort algorithm

Change by wim glenn : -- nosy: +wim.glenn ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: New changeset 65ecc390c1fa5acdd6348ae3f9843bbdcd8870d1 by Pablo Galindo in branch 'master': bpo-17005: Minor improvements to the documentation of TopologicalSorter (GH-18155)

[issue17005] Add a topological sort algorithm

Change by Pablo Galindo Salgado : -- pull_requests: +17541 pull_request: https://github.com/python/cpython/pull/18155 ___ Python tracker ___

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: New changeset 99e6c260d60655f3d2885af545cbc220b808d492 by Pablo Galindo in branch 'master': bpo-17005: Add a class to perform topological sorting to the standard library (GH-11583)

[issue17005] Add a topological sort algorithm

Zahari Dim added the comment: I would like to suggest a `dependency_resolver` API that I have been using that goes in line with what Tim Peters proposes in https://bugs.python.org/issue17005#msg359702 A DAG would be an object that can be iterated in topological order with __iter__ (for

[issue17005] Add a topological sort algorithm

gaborbernat added the comment: I think the new interface feeds better for usage in both sequential or parallel workflows, which means we can use a single UI for both, so  from myself -- nosy: +gaborbernat ___ Python tracker

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: I have been playing with the API for a while and I have to say that I have fallen in love with it: I tried to reimplement many snippets of parallel and non-parallel topological-order processing of a graph with this and it always fits very nicely. I

[issue17005] Add a topological sort algorithm

Tim Peters added the comment: Oh, it's fine! Kahn's algorithm is what I meant when I wrote the "bog-standard implementation" before. I don't believe I've ever seen a context in real life where topsort speed made a lick of real difference, so I expect any linear-time (in the sum of the

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: Disregarding the API, what do you think about the approach of https://github.com/python/cpython/pull/11583 for the implementation? Under my benchmarks (check previous comments) it seems to perform very good with regards to memory and time.

[issue17005] Add a topological sort algorithm

Tim Peters added the comment: I'll add ts.py, which was a work-in-progress that implements a minor variation of most everything I typed about. If nothing else, its _find_cycle is useful as a non-recursive linear-time cycle finder (recursion is deadly here because recursive depth-first

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: Fair enough, I will read this carefully again and try to sketch a prototype soon :) -- ___ Python tracker ___

[issue17005] Add a topological sort algorithm

Tim Peters added the comment: > I am slightly confused about what .prepare() should do. Why > is this step necessary? To say "I'm done adding edges". Any call to add() after prepare() should raise an exception. Likewise, e.g., any call to get_ready() before prepare() should raise an

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: > Am I seriously suggesting this for Python? Sure. It's fun to advance the > practical state of the art :-) I think this API looks very interesting! I have some questions before start implementing it to play a bit with it: - I am slightly

[issue17005] Add a topological sort algorithm

Change by Senthil Kumaran : -- nosy: +orsenthil ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue17005] Add a topological sort algorithm

Tim Peters added the comment: Let's stir this up a bit ;-) I recently had occasion to exchange ideas with Larry Hastings about topsorts for use in a package manager he's writing. I thought his API for adding edges was ... perfect: add(node, *dependson) So, e.g., add(A, B, C) says A

[issue17005] Add a topological sort algorithm

Gareth Rees added the comment: I'd like to push back on the idea that graphs with isolated vertices are "unusual cases" as suggested by Raymond. A very common use case (possibly the most common) for topological sorting is job scheduling. In this use case you have a collection of jobs, some

[issue17005] Add a topological sort algorithm

Raymond Hettinger added the comment: Unless Łukasz gives us a nod to work out this API for the second beta, we'll need to defer this to 3.9. IMO, the API in the patch is not user friendly. It started on the right path but became contorted (for both inputs and outputs) to serve unusual

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado 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

[issue17005] Add a topological sort algorithm

Change by Raymond Hettinger : Added file: https://bugs.python.org/file48362/tsort.1.py ___ Python tracker ___ ___ Python-bugs-list mailing

[issue17005] Add a topological sort algorithm

Raymond Hettinger added the comment: Attaching some of my 2013 work on this. Here are some API notes: * spell-out the name topological_sort() * allow input as ordered pairs like the Unix tsort command https://en.wikipedia.org/wiki/Tsort#Examples * allow more convenient input as

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: (A, B, C, D, E, F) would not be correct as B is order 2 and "C" and "A" is order 1. The correct orders are the inner-group permutations of: [{'A', 'F'}, {'B', 'D', 'E'}, {'C'}] (Assuming that the lower diagram goes from top to bottom) --

[issue17005] Add a topological sort algorithm

Rémi Lapeyre added the comment: > 2) Topological sorting usually is well-defined on totally connected graphs, > so I do not know what exactly it means to topologically sort two disjoint > graphs. This was one of the main drawbacks of the tuple-based approach, but I > think it may be a good

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: Although I think the API with the dictionary may be cleaner, I still do not like it completely. 1) One of the reasons is that implementing C3 directly with the topological sort is not straightforward as the different nodes that are at the same level

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: I have updated the PR to receive a dictionary of sets as in Eric V. Smith's package. I have maintained the guts of the current algorithm as it scales much better: >>> test_data = {x:{x+n for n in range(100)} for x in range(1000)} >>> %timeit

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: I have updated the PR to receive a dictionary of sets as in Eric V. Smith's package. I have maintained the guts of the current algorithm as it scales much better: >>> test_data = {x:{x+n for n in range(100)} for x in range(1000)} >>> %timeit

[issue17005] Add a topological sort algorithm

Eric V. Smith added the comment: This is why I prefer the API exposed by https://pypi.org/project/toposort/ list(toposort({2: {11}, 9: {11, 8, 10}, 10: {11, 3}, 11: {7, 5}, 8: {7, 3}, })) returns [{3, 5, 7}, {8, 11},

[issue17005] Add a topological sort algorithm

Terry J. Reedy added the comment: I think 'toposort' is a good name for a function that implements 'topological sorting'. https://en.wikipedia.org/wiki/Topological_sorting -- versions: +Python 3.8 -Python 3.4 ___ Python tracker

[issue17005] Add a topological sort algorithm

Gareth Rees added the comment: Just to elaborate on what I mean by "bug magnet". (I'm sure Pablo understands this, but there may be other readers who would like to see it spelled out.) Suppose that you have a directed graph represented as a mapping from a vertex to an iterable of its

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: > 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. I totally agree that `topsort` is a bad

[issue17005] Add a topological sort algorithm

Gareth Rees 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

[issue17005] Add a topological sort algorithm

Rémi Lapeyre added the comment: As the name been already discussed ? I fear that topsort might only be clear to people already knowing what it does. topoligical_sort would be more discoverable and explicit and one can always do from functools import topological_sort as tsort if he

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: The one in PR 11583 is twice as fast: >timeit for -> >topsort([(2,11),(9,11),(9,8),(9,10),(10,11),(10,3),(11,7),(11,5),(8,7),(8,3)]) 12.4 µs ± 59.1 ns per loop (mean ± std. dev. of 7 runs, 10 loops each) >timeit for ->

[issue17005] Add a topological sort algorithm

Pablo Galindo Salgado added the comment: The one in PR 11583 is twice as faster: >timeit for -> >topsort([(2,11),(9,11),(9,8),(9,10),(10,11),(10,3),(11,7),(11,5),(8,7),(8,3)]) 12.4 µs ± 59.1 ns per loop (mean ± std. dev. of 7 runs, 10 loops each) >timeit for ->

[issue17005] Add a topological sort algorithm

Raymond Hettinger added the comment: Thanks. I have some API nits to work to make this more broadly useful. I'll all those on the PR comments soonish :-) -- ___ Python tracker

[issue17005] Add a topological sort algorithm

Change by Pablo Galindo Salgado : -- pull_requests: -11268 ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue17005] Add a topological sort algorithm

Change by Pablo Galindo Salgado : -- pull_requests: -11267, 11268 ___ Python tracker ___ ___ Python-bugs-list mailing list

[issue17005] Add a topological sort algorithm

Alexander Belopolsky added the comment: Here is an implementation that I've used for years. It is somewhat shorter than the one in PR 11583: class CycleError(LogicalError, ValueError): """dependencies cycle detected """ def tsort(pairs): """topological sort Just like unix

[issue17005] Add a topological sort algorithm

Change by Pablo Galindo Salgado : -- keywords: +patch, patch pull_requests: +11266, 11267 stage: -> patch review ___ Python tracker ___

[issue17005] Add a topological sort algorithm

Change by Pablo Galindo Salgado : -- keywords: +patch, patch, patch pull_requests: +11266, 11267, 11268 stage: -> patch review ___ Python tracker ___

[issue17005] Add a topological sort algorithm

Change by Pablo Galindo Salgado : -- keywords: +patch pull_requests: +11266 stage: -> patch review ___ Python tracker ___ ___

[issue17005] Add a topological sort algorithm

Changes by Martin Panter vadmium...@gmail.com: -- nosy: +vadmium ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17005 ___ ___ Python-bugs-list

[issue17005] Add a topological sort algorithm

Alexander Belopolsky added the comment: +1 I had tsort in my own utilities library for so long that I thought it was in stdlib already. I found this issue after unsuccessfully searching docs.python.org. :-) I think functools will be a fine place for it. It is somewhat related to total

[issue17005] Add a topological sort algorithm

Changes by Tshepang Lekhonkhobe tshep...@gmail.com: -- nosy: +tshepang ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17005 ___ ___

[issue17005] Add a topological sort algorithm

Changes by Terry J. Reedy tjre...@udel.edu: -- nosy: +terry.reedy ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17005 ___ ___ Python-bugs-list

[issue17005] Add a topological sort algorithm

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

[issue17005] Add a topological sort algorithm

Christian Heimes added the comment: Good idea! I'm using http://pypi.python.org/pypi/topsort/0.9 for a couple of years. The initial code was written by Tim Peters. -- nosy: +christian.heimes ___ Python tracker rep...@bugs.python.org

[issue17005] Add a topological sort algorithm

Changes by Raymond Hettinger raymond.hettin...@gmail.com: -- assignee: - rhettinger ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17005 ___ ___

[issue17005] Add a topological sort algorithm

Eric V. Smith added the comment: +1 I'll note (by inspection only) your example code doesn't work under Python 3.x! :) (print as a statement) -- nosy: +eric.smith ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue17005