graphlib.invert() and graphlib.transitive()

Feature or enhancement

Proposal:

I want to propose two utility functions to be added to the graphlib module.

First invert():

>>> graphlib.invert({"a": ["b, "c"]})
{"b": {"a"}, "c": {"a"}}

Second as_transitive():

>>> graphlib.as_transitive({"a": ["b"], "b": ["c"]})
{"a": {"b", "c"}, "b": {"c"}}

Background: I've been working with graphlib.TopologicalSorter a lot, and found it to be extremely helpful working with task graphs both for static analysis and real-time processing.

invert() is a crucial step for processing a task graph backwards or for analysing dependents instead of dependencies. For example, if you build a set of components in topological order, you might clean them in inverse topological order (if a component can be used to clean the things that depend on it).

as_transitive() is valuable for static analysis. For example in a package dependency graph the transitive closure is what you must package in order to deploy a product. The inverse transitive dependency graph is what you must revalidate when changing a package.

These two operations would round out the basic capabilities needed for graph processing tasks (as opposed to the more mathematical analysis provided by a package like NetworkX).

Has this already been discussed elsewhere?

This is a minor feature, which does not need previous discussion elsewhere

Links to previous discussion of this feature:

No response

Linked PRs

• gh-130875

Bắt đầu bằng việc xem xét graphlib.TopologicalSorter và PR liên quan gh-130875, sau đó so sánh các ví dụ invert() và as_transitive() được đề xuất với API graphlib hiện có. Công việc được xem là hoàn tất khi cả hai tiện ích có hành vi và cách triển khai thống nhất, đồng thời có các bài kiểm thử bao quát các ví dụ được tài liệu hóa và những trường hợp đồ thị liên quan.