petgraph/algo/
tred.rs

1//! Compute the transitive reduction and closure of a directed acyclic graph
2//!
3//! ## Transitive reduction and closure
4//! The *transitive closure* of a graph **G = (V, E)** is the graph **Gc = (V, Ec)**
5//! such that **(i, j)** belongs to **Ec** if and only if there is a path connecting
6//! **i** to **j** in **G**. The *transitive reduction* of **G** is the graph **Gr
7//! = (V, Er)** such that **Er** is minimal wrt. inclusion in **E** and the transitive
8//! closure of **Gr** is the same as that of **G**.
9//! The transitive reduction is well-defined for acyclic graphs only.
10
11use alloc::{vec, vec::Vec};
12
13use fixedbitset::FixedBitSet;
14
15use crate::adj::{List, UnweightedList};
16use crate::graph::IndexType;
17use crate::visit::{
18    GraphBase, IntoNeighbors, IntoNeighborsDirected, NodeCompactIndexable, NodeCount,
19};
20use crate::Direction;
21
22/// Creates a representation of the same graph respecting topological order for use in `tred::dag_transitive_reduction_closure`.
23///
24/// # Arguments
25/// * `g`: a directed acyclic graph.
26/// * `toposort`: a topological order on the node indices of `g` (for example obtained from [`toposort`](fn@crate::algo::toposort)).
27///
28/// # Returns
29/// Returns a tuple of:
30/// * [`UnweightedList`](type@crate::adj::UnweightedList) `res` graph.
31/// * `Vec`: reciprocal of the topological sort `revmap`.
32///
33/// `res` is the same graph as `g` with the following differences:
34/// * Node and edge weights are stripped,
35/// * Node indices are replaced by the corresponding rank in `toposort`,
36/// * Iterating on the neighbors of a node respects topological order.
37///
38/// `revmap` is handy to get back to map indices in `g` to indices in `res`.
39///
40/// # Complexity
41/// * Time complexity: **O(|V| + |E|)**.
42/// * Auxiliary space: **O(|V| + |E|)**.
43///
44/// where **|V|** is the number of nodes and **|E|** is the number of edges.
45///
46/// # Example
47///
48/// ```rust
49/// use petgraph::prelude::*;
50/// use petgraph::graph::DefaultIx;
51/// use petgraph::visit::IntoNeighbors;
52/// use petgraph::algo::tred::dag_to_toposorted_adjacency_list;
53///
54/// let mut g = Graph::<&str, (), Directed, DefaultIx>::new();
55/// let second = g.add_node("second child");
56/// let top = g.add_node("top");
57/// let first = g.add_node("first child");
58/// g.extend_with_edges(&[(top, second), (top, first), (first, second)]);
59///
60/// let toposort = vec![top, first, second];
61///
62/// let (res, revmap) = dag_to_toposorted_adjacency_list(&g, &toposort);
63///
64/// // let's compute the children of top in topological order
65/// let children: Vec<NodeIndex> = res
66///     .neighbors(revmap[top.index()])
67///     .map(|ix: NodeIndex| toposort[ix.index()])
68///     .collect();
69/// assert_eq!(children, vec![first, second])
70/// ```
71pub fn dag_to_toposorted_adjacency_list<G, Ix: IndexType>(
72    g: G,
73    toposort: &[G::NodeId],
74) -> (UnweightedList<Ix>, Vec<Ix>)
75where
76    G: GraphBase + IntoNeighborsDirected + NodeCompactIndexable + NodeCount,
77    G::NodeId: IndexType,
78{
79    let mut res = List::with_capacity(g.node_count());
80    // map from old node index to rank in toposort
81    let mut revmap = vec![Ix::default(); g.node_bound()];
82    for (ix, &old_ix) in toposort.iter().enumerate() {
83        let ix = Ix::new(ix);
84        revmap[old_ix.index()] = ix;
85        let iter = g.neighbors_directed(old_ix, Direction::Incoming);
86        let new_ix: Ix = res.add_node_with_capacity(iter.size_hint().0);
87        debug_assert_eq!(new_ix.index(), ix.index());
88        for old_pre in iter {
89            let pre: Ix = revmap[old_pre.index()];
90            res.add_edge(pre, ix, ());
91        }
92    }
93    (res, revmap)
94}
95
96/// Computes the transitive reduction and closure of a DAG.
97///
98/// The algorithm implemented here comes from [On the calculation of
99/// transitive reduction-closure of
100/// orders](https://www.sciencedirect.com/science/article/pii/0012365X9390164O) by Habib, Morvan
101/// and Rampon.
102///
103/// # Arguments
104/// * `g`: an input graph in a very specific format: an adjacency
105///   list such that node indices are a toposort, and the neighbors of all nodes are stored in topological order.
106///   To get such a representation, use the function [`dag_to_toposorted_adjacency_list`].
107///
108/// # Returns
109/// The output is the pair of the transitive reduction and the transitive closure.
110///
111/// # Complexity
112/// * Time complexity: **O(|V| + \sum_{(x, y) \in Er} d(y))** where **d(y)**
113///   denotes the outgoing degree of **y** in the transitive closure of **G**
114///   and **Er** the edge set of the transitive reduction.
115///   This is still **O(|V|³)** in the worst case like the naive algorithm but
116///   should perform better for some classes of graphs.
117/// * Auxiliary space: **O(|E|)**.
118///
119/// where **|V|** is the number of nodes and **|E|** is the number of edges.
120pub fn dag_transitive_reduction_closure<E, Ix: IndexType>(
121    g: &List<E, Ix>,
122) -> (UnweightedList<Ix>, UnweightedList<Ix>) {
123    let mut tred = List::with_capacity(g.node_count());
124    let mut tclos = List::with_capacity(g.node_count());
125    let mut mark = FixedBitSet::with_capacity(g.node_count());
126    for i in g.node_indices() {
127        tred.add_node();
128        tclos.add_node_with_capacity(g.neighbors(i).len());
129    }
130    // the algorithm relies on this iterator being toposorted
131    for i in g.node_indices().rev() {
132        // the algorighm relies on this iterator being toposorted
133        for x in g.neighbors(i) {
134            if !mark[x.index()] {
135                tred.add_edge(i, x, ());
136                tclos.add_edge(i, x, ());
137                for e in tclos.edge_indices_from(x) {
138                    let y = tclos.edge_endpoints(e).unwrap().1;
139                    if !mark[y.index()] {
140                        mark.insert(y.index());
141                        tclos.add_edge(i, y, ());
142                    }
143                }
144            }
145        }
146        for y in tclos.neighbors(i) {
147            mark.set(y.index(), false);
148        }
149    }
150    (tred, tclos)
151}
152
153#[cfg(test)]
154#[test]
155fn test_easy_tred() {
156    let mut input = List::new();
157    let a: u8 = input.add_node();
158    let b = input.add_node();
159    let c = input.add_node();
160    input.add_edge(a, b, ());
161    input.add_edge(a, c, ());
162    input.add_edge(b, c, ());
163    let (tred, tclos) = dag_transitive_reduction_closure(&input);
164    assert_eq!(tred.node_count(), 3);
165    assert_eq!(tclos.node_count(), 3);
166    assert!(tred.find_edge(a, b).is_some());
167    assert!(tred.find_edge(b, c).is_some());
168    assert!(tred.find_edge(a, c).is_none());
169    assert!(tclos.find_edge(a, b).is_some());
170    assert!(tclos.find_edge(b, c).is_some());
171    assert!(tclos.find_edge(a, c).is_some());
172}
petgraph/algo/tred.rs

petgraph/algo/
tred.rs
