[issue46071] Graphlib documentation (edge direction)

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

Perhaps you've overlooking something so obvious to the module authors that I haven't thought to mention it?

The purpose here is to compute a linear order. Now not even you ;-) can pretend to be confused about what "predecessor" and "successor" mean in a linear order. There's no graph involved in the final result (unless you mentally impose a trivial linear graph on the result sequence).

And that's how to view the `graph` argument _as intended_. It maps an element to the elements that must precede it _in the result_. The element's mandatory predecessors in any acceptable imposed total ordering.

>From that intended view, this is just waaaay off base:

> I wish the docs started by saying:
>
> The graph is a dict of {'start_node': ['end_nodes',]}
> The topological sorter puts the end_nodes before their start_nodes.
>   [note: this is what the code currently does]

The words "start" and "end" there would be clearer as "banana" and "beeswax" ;-) End of what? Start of what? The "start" node has to appear _after_ all the "end" nodes? In what other context does the "start" appear after the "end"?

As is, the code puts the "start" node after all its declared mandatory predecessors. Exactly as the word "predecessors" suggests should happen.


[Dennis]
> David suggests:
>
> * static_order returns [A, B]
> * Conceptual/abstract directed graph direction is B --> A
> * mapping to be passed is {B: [A]}

IF that's what he's suggesting (I don't know), that's not a matter of preference, it's just plain wrong. The only possible topsort of the DAG  B --> A is the sequence [B, A]. For which see absolutely any text defining the terms.

There are many ways the "mapping to be passed" could be defined. David is certainly right that, by convention, most graphs in Python are represented by successor dicts. But he apparently doesn't want an option for the topsorter to accept such a dict either. (An irony in passing: under the covers, the class converts the predecessor-dict `graph` argument to a successor-dict representation.)

At this point, I not only don't know what he wants, his position gets less clear to me over time.

----------

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