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

Start by reviewing graphlib.TopologicalSorter and the linked PR gh-130875, then compare the proposed invert() and as_transitive() examples with the existing graphlib API. Done means both utilities have agreed behavior, implementation, and tests covering the documented examples and relevant graph cases.