Tim Peters <t...@python.org> added the comment:
I think you should give up on this. But suit yourself ;-) Exactly the same information is conveyed whether representing a graph by successor or predecessor dicts. Some operations are more convenient in one representation than the other, but each is easily derived from the other. For your > The issue with the current form is that you can not traverse > the graph, at least not forwards. is the equal and opposite complaint that with "your" (successor) form, you cannot traverse the graph, at least not backwards. What of it? _Some_ packages maintain both predecessor and successor dicts in lockstep. For example, Kosaraju's elegant algorithm for finding strongly connected components requires efficient traversal in both directions. The topsort algorithm couldn't care less how you want to represent your graphs. But it does have a specific representation it requires if you want to use the optional `graph=` constructor argument. It's documented and works fine if used as documented. > What is important about the topo-sort is that it makes all of the > edges point in the *same* direction. Not following that. topsort applies to directed graphs, where the meanings of "predecessor" and "successor" are universally agreed upon. By definition, a topsort must begin with an element having no predecessors. The directions of the arrows are crucial to that. > It doesn't actually matter which direction that is. And credit where due, the > library picked the more-useful direction. It was a pragmatic choice, driven > by the real use case of dependency resolution. Not really. It was driven by the definition of what "topological sort" means. Most of the API was actually driven by making it easy to use correctly (race-free, deadlock-free) in a dynamic (there's no way to guess from one run to the next which order will end up being used) multiprocessing context, something few topsort packages even attempt to address. > But having the graph with arrows pointing in the wrong direction is > going to cause endless confusion. Starting when? ;-) Seriously, this is the first complaint I've seen, and you're not actually confused. > For an example of the confusion this causes, look at the API itself. The "add" > method explicitly calls out the fact that you can add nodes with no > predecessors. And what about that is confusing? If every node has to have a predecessor, a topsort can't even exist! More generally, any usable implementation of "directed graph" has to allow for isolated nodes too. Historically, the docs pointed that out to contrast it with other APIs under consideration that required special tricks to convince the function that a graph had isolated nodes. In this API, it's dead easy: just add the node with no predecessors. > This is obviously also possible with the graph argument as it currently is. Of course. Are you going to seriously contend this is "a problem", but the obvious workalike for successor dicts would not be "a problem"? (In a successor dict, it's equally easy to specify a node with no successors. Good! For a total ordering to exist, there must be at least one node with no predecessor and at least one with no successor - these aren't "problems", they're essentials.) In any case, the docs say what was intended and implemented from the start: the optional `graph` argument is a predecessor dict representation. You're not required to like that decision, but there's no case here - to my eyes - made for saying "it's a bug". ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue46071> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
