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

Comece revisando graphlib.TopologicalSorter e o PR relacionado gh-130875; em seguida, compare os exemplos propostos de invert() e as_transitive() com a API existente de graphlib. O trabalho estará concluído quando ambos os utilitários tiverem comportamento e implementação consistentes, e houver testes cobrindo os exemplos documentados e os casos relevantes de grafos.