Function bevy_internal::utils::petgraph::algo::tred::dag_transitive_reduction_closure

pub fn dag_transitive_reduction_closure<E, Ix>(
    g: &List<E, Ix>
) -> (List<(), Ix>, List<(), Ix>)
where
    Ix: IndexType,

Computes the transitive reduction and closure of a DAG.

The algorithm implemented here comes from On the calculation of transitive reduction-closure of orders by Habib, Morvan and Rampon.

The input graph must be in a very specific format: an adjacency list such that:

• Node indices are a toposort, and
• The neighbors of all nodes are stored in topological order. To get such a representation, use the function dag_to_toposorted_adjacency_list.

The output is the pair of the transitive reduction and the transitive closure.

Runtime complexity: O(|V| + \sum_{(x, y) \in Er} d(y)) where d(y) denotes the outgoing degree of y in the transitive closure of G. This is still O(|V|³) in the worst case like the naive algorithm but should perform better for some classes of graphs.

Space complexity: O(|E|).