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