[issue46071] Graphlib documentation (edge direction)

Change by David Mc Dougall : -- stage: patch review -> resolved status: open -> closed ___ Python tracker ___ ___ Python-bugs-list m

[issue46071] Graphlib documentation (edge direction)

Tim Peters added the comment: > I know that there are many different ways to represent > a graph, but your graph format *is just plain wrong.* Yet when I offered to support an option to support the graph format you insist is uniquely "right", you poo-poo'ed the idea. So what is your real comp

[issue46071] Graphlib documentation (edge direction)

Change by David Mc Dougall : -- nosy: -dam1784 ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.

[issue46071] Graphlib documentation (edge direction)

David Mc Dougall added the comment: > 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 stat

[issue46071] Graphlib documentation (edge direction)

Tim Peters 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 o

[issue46071] Graphlib documentation (edge direction)

Dennis Sweeney 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] * Co

[issue46071] Graphlib documentation (edge direction)

David Mc Dougall added the comment: No, the code works fine. I just wish the docs weren't so muddled. 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 cod

[issue46071] Graphlib documentation (edge direction)

Tim Peters added the comment: Now you may be getting somewhere ;-) Complaining about the docs wasn't getting traction because they're using standard terminology with the standard meanings, and tell the plain truth about what the class requires and delivers. You wish it required something els

[issue46071] Graphlib documentation (edge direction)

David Mc Dougall added the comment: I can post literally hundreds of examples of directed graphs that are traversable in the forward direction. This might be the only one which is *only* traversable backwards. > As to the meaning of "point to" Here is one: If I have a pointer in memory, I

[issue46071] Graphlib documentation (edge direction)

Tim Peters added the comment: >> the meanings of "predecessor" and "successor" are >> universally agreed upon > I disagree. I can post literally hundreds of citations that all agree: in u -> v, u is a direct predecessor of v, and v is a direct successor of u. Here's one: http://pages.cs.wi

[issue46071] Graphlib documentation (edge direction)

Dennis Sweeney added the comment: > It's not obvious if the "predecessor" should be the start or the end point of > the edge https://en.wikipedia.org/wiki/Directed_graph#Basic_terminology : """If a path leads from x to y, then y is said to be a successor of x and reachable from x, and x is s

[issue46071] Graphlib documentation (edge direction)

David Mc Dougall added the comment: > you're not actually confused. I was when I first read it! > the meanings of "predecessor" and "successor" are universally agreed upon I disagree. The universally agreed upon terms are "directed edge u -> v". It's not obvious if the "predecessor" should

[issue46071] Graphlib documentation (edge direction)

Tim Peters 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 derive

[issue46071] Graphlib documentation (edge direction)

David Mc Dougall added the comment: > The argument passed is the predecessor form of the graph B -> A where graph = {'A' : ['B']} This is part that I'm objecting to. The form of the graph should be A -> B, not B -> A. The issue with the current form is that you can not traverse the graph, a

[issue46071] Graphlib documentation (edge direction)

Tim Peters added the comment: I'm going to leave this to Pablo - adding the `graph` argument was his idea ;-) It would, I think, have been better if this argument had been named, say, "preds" instead of "graph". The docs, to my eyes, are entirely clear about that `graph` is a representation

[issue46071] Graphlib documentation (edge direction)

David Mc Dougall added the comment: > If the way the user collects their data stores only successor links (which, > as above, seems odd in applications that actually use topsorts), then they > need something like this instead: Actually they only need to do this: ts = TopologicalSorter(my_fo

[issue46071] Graphlib documentation (edge direction)

David Mc Dougall added the comment: The "reverse-toposort" is actually quite a good idea. The end-user is usually going to want to iterate over the sorted output in the "reverse" order anyways, especially if they're doing task ordering / dependency resolution. Also, the underlying algorithm

[issue46071] Graphlib documentation (edge direction)

Tim Peters added the comment: For the purpose of topological sorting, yes, it's by far most natural to give, for each node, the collection of that node's predecessors. And that's the way topsort applications typically collect their data to begin with, like, "here, for each recipe, is a list

[issue46071] Graphlib documentation (edge direction)

Change by David Mc Dougall : -- title: Graphlib documentation -> Graphlib documentation (edge direction) ___ Python tracker ___ ___

[issue46071] Graphlib documentation

Change by David Mc Dougall : -- pull_requests: +28446 pull_request: https://github.com/python/cpython/pull/30223 ___ Python tracker ___

[issue46071] Graphlib documentation

Change by Éric Araujo : -- assignee: docs@python -> components: +Library (Lib) -Documentation nosy: -docs@python versions: -Python 3.10, Python 3.9 ___ Python tracker ___ ___

[issue46071] Graphlib documentation

Change by Eric V. Smith : -- nosy: +eric.smith, rhettinger, tim.peters ___ Python tracker ___ ___ Python-bugs-list mailing list Unsu

[issue46071] Graphlib documentation

Change by Roundup Robot : -- keywords: +patch nosy: +python-dev nosy_count: 2.0 -> 3.0 pull_requests: +28324 stage: -> patch review pull_request: https://github.com/python/cpython/pull/30102 ___ Python tracker _

[issue46071] Graphlib documentation

New submission from David Mc Dougall : The documentation for graphlib encourages users to represent their graphs in a awkward format. Graphs are currently represented using dictionaries of nodes, for example: graph["end_node"] = ["start_node"] And this is unintuitive because you can't use the