Improve graphlib.TopologicalSort by removing the prepare step

[larryhastings]

BPO	47145
Nosy	@tim-one, @larryhastings, @ericvsmith, @pablogsal, @sweeneyde

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/larryhastings'
closed_at = None
created_at = <Date 2022-03-28.16:20:34.277>
labels = ['type-feature', 'library', '3.11']
title = 'Improve graphlib.TopologicalSort by removing the prepare step'
updated_at = <Date 2022-04-02.21:50:46.302>
user = 'https://github.com/larryhastings'

bugs.python.org fields:

activity = <Date 2022-04-02.21:50:46.302>
actor = 'larry'
assignee = 'larry'
closed = False
closed_date = None
closer = None
components = ['Library (Lib)']
creation = <Date 2022-03-28.16:20:34.277>
creator = 'larry'
dependencies = []
files = []
hgrepos = []
issue_num = 47145
keywords = []
message_count = 12.0
messages = ['416182', '416306', '416321', '416322', '416323', '416324', '416404', '416405', '416407', '416408', '416592', '416594']
nosy_count = 5.0
nosy_names = ['tim.peters', 'larry', 'eric.smith', 'pablogsal', 'Dennis Sweeney']
pr_nums = []
priority = 'normal'
resolution = None
stage = 'needs patch'
status = 'open'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue47145'
versions = ['Python 3.11']

[larryhastings]

I've maintained my own topological sort class for a while now. The API I came up with (or was it Tim and I?) was adopted for graphlib.TopologicalSort(). Some of my method names are slightly different, but the APIs are so similar, I can do a little renaming and run Lib/test/test_graphlib using my implementation. (For clarity I'm going to write the rest of this issue using the names from graphlib.)

Recently I made an improvement to my version: it no longer has the modal behavior where there's a "before prepare" phase where you add nodes and an "after prepare" phase where you can call get_ready and done.

Instead, in my new and improved version the graph is always maintained in a "ready" state. You can call add, get_ready, and done in any order, as much as you like. prepare doesn't do anything besides the cycle check--but read on!

This approach required tweaking some semantics behind the scenes. My graph object now maintains an internal "dirty" flag. It's set to True after any edges are added, and only gets cleared after checking for cycles. prepare runs this cycle check, but get_ready *also* runs this cycle check. (Though in both cases, only when the dirty flag is set, of course.) In theory this means you no longer need the prepare call. However, it's still useful, because you can call it to check for a CycleError.

So, on the one hand, this means that get_ready can throw a CycleError, which it never did before. On the other hand, it won't throw for existing users of the library, because they never add edges after their prepare call. So this semantic change shouldn't break existing users, assuming they're not misusing the existing API.

Another wrinkle: adding a dependency on a node that's already been handed out by get_ready (but hasn't been returned by done) is ignored. Again, not something existing users of graphlib can do, so this shouldn't break code.

There's one final semantic change I made worth knowing about: when you return a node via done, the graph simply forgets about it. This means you could add it a second time (!) and it could go for a complete ride through the graph again, wheeee! This also means that when all nodes have been returned by done, the graph is essentially returned to its initial pristine state. This too seems completely harmless, because with the existing library it's illegal to add nodes to a graph after calling prepare, so nobody's doing it, so it won't break any code.

I'm happy to contribute my version. But I was lazy and didn't worry about speed or memory implementation; it's strewn with sets and things. I figured I could always optimize it later. But "later" could become "now" if we were interested in trying to merge this behavior into Python's graphlib.

Interested?

[ericvsmith]

My personal usage of a topological sort are restricted to maybe 100 entries max, so I can't really test this in any meaningful way.

That, and the project that uses it is stuck on 3.6, so I haven't switched to the graphlib version yet.

[sweeneyde]

Out of curiosity, what are the use cases for adding nodes after get_ready has already produced nodes?

I was wondering about avoiding the need to call prepare() by having it automatically do the cycle-checking at the first get_ready() call and then raising ValueError if add() is called any time thereafter.

Assuming we do want to be able to add() after a get_ready(), is there a reason that "forgetting" already-produced nodes is the correct behavior, as opposed to remembering all nodes ever added, and raising iff the addition creates a cycle among all nodes ever added or depends on an already-yielded node?

[sweeneyde]

depends on an already-yielded node

I mean "creates a new not-yet-yielded dependency for an already-yielded node".

[larryhastings]

I'm using my graph library to manage a list of tasks that need doing in some sort of proper order. One task may spawn other tasks at runtime, and we don't necessarily know what the tasks will be until runtime. It's way more convenient to simply add such tasks on demand, rather than trying to preemptively pre-add all such possible tasks before preparing the graph, or creating additional graphs.

For example, consider a tool that downloads and digests zip files full of music from an online store. Your initial tasks might represent "download the zip file", then "decompress and examine the contents of the zip file". You could then iterate over the contents of the zip file, adding different tasks based on what you find--one pipeline of tasks for media files (FLAC/MP3/OGG/etc), another for the playlist, a third if you don't *find* a playlist, a fourth for image files, etc. (Not that you'd necessarily write such a tool this way, but it's at least plausible.)

The new nodes needn't be connected to the existing nodes for this to still be useful. You could reuse the same graph object for all your tasks.

[larryhastings]

Assuming we do want to be able to add() after a get_ready(), is there
a reason that "forgetting" already-produced nodes is the correct
behavior, as opposed to remembering all nodes ever added, and
raising iff the addition creates a cycle among all nodes ever
added or depends on an already-yielded node?

I'm not sure "correct" applies here, because I don't have a sense that one behavior is conceptually more correct than the other. But in implementing my API change, forgetting about the done nodes seemed more practical.

The "benefit" to remembering done nodes: the library can ignore dependencies to them in the future, forever. Adding a dependency to a node that's already been marked as "done" doesn't make much conceptual sense to me, but as a practical thing maybe it's useful? I'm not sure, but it doesn't seem all that useful.

I can only come up with a marginal reason why remembering done nodes is useful. Let's say all your tasks fan out from some fundamental task, like "download master list of work" or something. One of your tasks might discover additional tasks that need to run, and conceptually those tasks might depend on your "download master list of work" task. If the graph remembers the done list forever, then adding that dependency is harmless. If the graph forgets about done nodes, then adding that dependency could re-introduce that task to the graph, which could goof things up. So maybe it's a little bit of a footgun? But on the other hand: you already know you're running, and you're a task that was dependent on the master list of work, which means you implicitly know that dependency has been met. So just skip adding the redundant dependency and you're fine.

On the other hand, forgetting about the nodes has a definite practical benefit: the graph consumes less memory. If you use a graph object for a long time, the list of done nodes it's holding references to would continue to grow and grow and grow. If we forget about done nodes, we free up all that memory, and done membership testing maybe gets faster.

I guess I'm not married to the behavior. If someone had a great conceptual or practical reason why remembering the done nodes forever was better, I'd be willing to listen to reason.

[larryhastings]

Having slept on it, I think the footgun is slightly bigger than I gave it credit for. Also the problem of nodes lingering forever is easily solved: give the user control.

My next iteration will keep the done nodes around, but I'll also add a forget() method that compels the graph to forget all done nodes.