[issue47145] Improve graphlib.TopologicalSort by removing the prepare step

[Larry Hastings]

Larry Hastings <larry at hastings.org> added the comment:

One final aside.  Let me preface this by saying: I'm not proposing the following for graphlib.TopologicalSort.  It's obviously too late to change that object this much.  It's just something I'm thinking about--maybe I'll use this in my own library.

Where we are now, the graphlib.TopologicalSort object is simultaneously a static representation of a graph--which the object doesn't provide a public API for you to examine!--and a stateful single-use iterator over that graph.  My proposed change to the API seems to increase the tension between these two sets of semantics.  Perhaps a better set of semantics, that more successfully maps my use case to the graph object, would be as follows:

    * you can add() nodes and edges at any time.
    * get_ready() always returns the current list of nodes with no prececessors.  There is no internal "we already told you about this one" state.
    * replace done() with remove(), which removes the node and all edges from/to it from the graph.
    * static_order() is still fine.

I think this would make it easy to reason about the object's behavior, and would be a better match to my use case where you're continually adding (and removing?) nodes, not just during an initial "populate the graph" phase.

Again, not appropriate to consider for graphlib.TopologicalSort.

----------

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