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

先檢視 graphlib.TopologicalSorter 和相關的 PR gh-130875，接著將提議的 invert() 與 as_transitive() 範例和現有的 graphlib API 進行比較。當兩個公用工具的行為與實作一致，且測試涵蓋文件中的範例及相關圖形案例時，即表示完成。