[issue46071] Graphlib documentation (edge direction)

[Dennis Sweeney]

Dennis Sweeney <sweeney.dennis650 at gmail.com> added the comment:

I think I can summarize:

Tim + Current Docs:

* static_order to return [A, B]
* Conceptual/abstract directed graph direction is A --> B
* A is a predecessor of B
* predecessor mapping to be passed is {B: [A]}

David suggests:

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

It seems David places more value on the idea of the concrete mapping "pointing forwards" with respect to the abstract directed graph, while it seems Tim places more value on the idea of the abstract mapping direction corresponding to the final static order. These two goals are in conflict, assuming we don't want to change the behavior.

I think I agree more with Tim, since abstract graphs can be represented in lots of ways (set of pairs? adjacency matrix or its transpose? adjacency list/dict? Bi-directional mapping?), so the translation from the abstract to the concrete is a decent place for the "reversal".

It's very very standard for a topological sort to be conceptualized as taking a picture like
    A → B
    ↓   ↓
    C → D
and transforming it into a list/iterator like [A, B, C, D], and I think the conceptual consistency there should be preserved, even if the concrete representation of the abstract graph "points backwards".

----------

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