Note

This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.

rustworkx.transitive_reduction

transitive_reduction(graph, /)

Returns the transitive reduction of a directed acyclic graph

The transitive reduction of $G=(V,E)$ is a graph $G\prime =(V,E\prime )$ such that for all $v$ and $w$ in $V$ there is an edge $(v,w)$ in $E\prime$ if and only if $(v,w)$ is in $E$ and there is no path from $v$ to $w$ in $G$ with length greater than 1.

Parameters:

graph (PyDiGraph) – A directed acyclic graph

Returns:

a directed acyclic graph representing the transitive reduction, and a map containing the index of a node in the original graph mapped to its equivalent in the resulting graph.

Return type:

Tuple[PyGraph, dict]

Raises:

PyValueError – if graph is not a DAG