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 进行比较。当两个实用工具的行为和实现达成一致，并且测试覆盖文档中的示例和相关图情况时，即可视为完成。