Function dag_transitive_reduction_closure

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

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.

Arguments

• g: an input graph 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.

Returns

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

Complexity

• Time 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 and Er the edge set of the transitive reduction. This is still O(|V|³) in the worst case like the naive algorithm but should perform better for some classes of graphs.
• Auxiliary space: O(|E|).

where |V| is the number of nodes and |E| is the number of edges.