pub fn dag_transitive_reduction_closure<E, Ix: IndexType>(
g: &List<E, Ix>
) -> (UnweightedList<Ix>, UnweightedList<Ix>)Expand description
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|).