portgraph/algorithms/
dominators.rs

1use super::postorder_filtered;
2use crate::index::MaybeNodeIndex;
3use crate::unmanaged::UnmanagedDenseMap;
4use crate::{Direction, LinkView, NodeIndex, PortGraph, PortIndex, PortView, SecondaryMap};
5use std::cmp::Ordering;
6
7/// Returns a dominator tree for a [`PortGraph`], where each node is dominated
8/// by its parent.
9///
10/// The `Map` type parameter specifies the type of the secondary map that is used
11/// to store the dominator tree data. The default is [`UnmanagedDenseMap`].
12///
13/// # Example
14///
15/// The following example runs the dominator algorithm on the following branching graph:
16///    ┏> b ┓
17/// a ─┫    ┣─> c ─> e
18///    ┗> d ┛
19///
20/// ```
21/// # use ::portgraph::algorithms::*;
22/// # use ::portgraph::*;
23/// let mut graph = PortGraph::with_capacity(5, 10);
24/// let a = graph.add_node(0,2);
25/// let b = graph.add_node(1,1);
26/// let c = graph.add_node(2,1);
27/// let d = graph.add_node(1,1);
28/// let e = graph.add_node(1,0);
29///
30/// graph.link_nodes(a, 0, b, 0).unwrap();
31/// graph.link_nodes(a, 1, d, 0).unwrap();
32/// graph.link_nodes(b, 0, c, 0).unwrap();
33/// graph.link_nodes(d, 0, c, 1).unwrap();
34/// graph.link_nodes(c, 0, e, 0).unwrap();
35///
36/// let tree: DominatorTree = dominators(&graph, a, Direction::Outgoing);
37/// assert_eq!(tree.root(), a);
38/// assert_eq!(tree.immediate_dominator(a), None);
39/// assert_eq!(tree.immediate_dominator(b), Some(a));
40/// assert_eq!(tree.immediate_dominator(c), Some(a));
41/// assert_eq!(tree.immediate_dominator(d), Some(a));
42/// assert_eq!(tree.immediate_dominator(e), Some(c));
43/// ```
44pub fn dominators<Map>(
45    graph: &PortGraph,
46    entry: NodeIndex,
47    direction: Direction,
48) -> DominatorTree<Map>
49where
50    Map: SecondaryMap<NodeIndex, MaybeNodeIndex<u32>>,
51{
52    DominatorTree::new(graph, entry, direction, |_| true, |_, _| true)
53}
54
55/// Returns a dominator tree for a [`PortGraph`], where each node is dominated
56/// by its parent, applying a filter to the nodes and ports.
57///
58/// If the filter predicate returns `false` for a node or port, it is ignored
59/// when computing the dominator tree.
60///
61/// The `Map` type parameter specifies the type of the secondary map that is
62/// used to store the dominator tree data. The default is [`UnmanagedDenseMap`]. For
63/// dominator trees over sparse node indices, `HashMap` or `BTreeMap` may be
64/// more efficient.
65///
66/// # Example
67///
68/// This example runs the dominator algorithm on the following branching graph:
69/// a ─┬> b ┐ │    ├─> c ─> e f ─┴> d ┴────────^
70///
71/// ```
72/// # use ::portgraph::algorithms::*;
73/// # use ::portgraph::*;
74/// let mut graph = PortGraph::with_capacity(5, 10);
75/// let a = graph.add_node(0,2);
76/// let b = graph.add_node(1,1);
77/// let c = graph.add_node(2,1);
78/// let d = graph.add_node(2,2);
79/// let e = graph.add_node(2,0);
80/// let f = graph.add_node(0,1);
81///
82/// graph.link_nodes(a, 0, b, 0).unwrap();
83/// graph.link_nodes(a, 1, d, 0).unwrap();
84/// graph.link_nodes(b, 0, c, 0).unwrap();
85/// graph.link_nodes(d, 0, c, 1).unwrap();
86/// graph.link_nodes(c, 0, e, 0).unwrap();
87/// graph.link_nodes(d, 1, e, 1).unwrap();
88/// graph.link_nodes(f, 0, d, 1).unwrap();
89///
90/// let tree: DominatorTree = dominators_filtered(
91///     &graph,
92///     a,
93///     Direction::Outgoing,
94///     |node| node != f,
95///     |_, p| Some(p) != graph.input(e, 1),
96/// );
97/// assert_eq!(tree.root(), a);
98/// assert_eq!(tree.immediate_dominator(a), None);
99/// assert_eq!(tree.immediate_dominator(b), Some(a));
100/// assert_eq!(tree.immediate_dominator(c), Some(a));
101/// assert_eq!(tree.immediate_dominator(d), Some(a));
102/// assert_eq!(tree.immediate_dominator(e), Some(c));
103/// assert_eq!(tree.immediate_dominator(f), None);
104/// ```
105pub fn dominators_filtered<Map>(
106    graph: &PortGraph,
107    entry: NodeIndex,
108    direction: Direction,
109    node_filter: impl FnMut(NodeIndex) -> bool,
110    port_filter: impl FnMut(NodeIndex, PortIndex) -> bool,
111) -> DominatorTree<Map>
112where
113    Map: SecondaryMap<NodeIndex, MaybeNodeIndex<u32>>,
114{
115    DominatorTree::new(graph, entry, direction, node_filter, port_filter)
116}
117
118/// A dominator tree for a [`PortGraph`].
119///
120/// See [`dominators`] for more information.
121pub struct DominatorTree<Map = UnmanagedDenseMap<NodeIndex, MaybeNodeIndex<u32>>> {
122    root: NodeIndex,
123    /// The immediate dominator of each node.
124    idom: Map,
125}
126
127impl<Map> DominatorTree<Map>
128where
129    Map: SecondaryMap<NodeIndex, MaybeNodeIndex<u32>>,
130{
131    fn new(
132        graph: &PortGraph,
133        entry: NodeIndex,
134        direction: Direction,
135        mut node_filter: impl FnMut(NodeIndex) -> bool,
136        mut port_filter: impl FnMut(NodeIndex, PortIndex) -> bool,
137    ) -> Self {
138        // We traverse the graph in post order starting at the `entry` node.
139        // We associate each node that we encounter with its index within the traversal.
140        let mut node_to_index = UnmanagedDenseMap::with_capacity(graph.node_capacity());
141        let mut index_to_node = Vec::with_capacity(graph.node_capacity());
142
143        for (index, node) in postorder_filtered(
144            graph,
145            [entry],
146            direction,
147            &mut node_filter,
148            &mut port_filter,
149        )
150        .enumerate()
151        {
152            node_to_index[node] = index;
153            index_to_node.push(node);
154        }
155
156        // We keep track of node's immediate dominators by their post order index.
157        // We set the entry node (i.e. the last node in the post oder traversal) it to dominate itself.
158        let num_nodes = index_to_node.len();
159        let mut dominators = vec![usize::MAX; num_nodes];
160        *dominators.last_mut().unwrap() = num_nodes - 1;
161
162        // Iterate until we have reached a fixed point
163        let mut changed = true;
164        while changed {
165            changed = false;
166
167            for post_order_index in (0..num_nodes - 1).rev() {
168                let node = index_to_node[post_order_index];
169
170                // PERFORMANCE: Here we look up the node's predecessors every time;
171                // instead we could create an array which holds the predecessor post order indices
172                // in sequence. But given that there won't be many iterations of this at all,
173                // that is probably too costly.
174                let new_dominator = graph
175                    .ports(node, direction.reverse())
176                    .filter_map(|port| {
177                        if !port_filter(node, port) {
178                            return None;
179                        }
180                        let link = graph.port_link(port)?;
181                        let pred = graph.port_node(link)?;
182                        if !node_filter(pred) || !port_filter(pred, link) {
183                            return None;
184                        }
185                        let pred_index = node_to_index[pred];
186                        if dominators[pred_index] == usize::MAX {
187                            // No dominator yet
188                            return None;
189                        }
190                        Some(pred_index)
191                    })
192                    .reduce(|index1, index2| intersect(&dominators, index1, index2))
193                    .expect("there must be at least one predecessor with known dominator");
194
195                if new_dominator != dominators[post_order_index] {
196                    changed = true;
197                    dominators[post_order_index] = new_dominator;
198                }
199            }
200        }
201
202        // Translate into a secondary map with `NodeIndex`s.
203        let mut idom = Map::with_capacity(graph.node_capacity());
204
205        for (index, dominator) in dominators.into_iter().take(num_nodes - 1).enumerate() {
206            debug_assert_ne!(dominator, usize::MAX);
207            idom.set(index_to_node[index], index_to_node[dominator].into());
208        }
209
210        Self { root: entry, idom }
211    }
212
213    #[inline]
214    /// Returns the root of the dominator tree.
215    pub fn root(&self) -> NodeIndex {
216        self.root
217    }
218
219    #[inline]
220    /// Returns the immediate dominator of a node.
221    pub fn immediate_dominator(&self, node: NodeIndex) -> Option<NodeIndex> {
222        self.idom.get(node).to_option()
223    }
224}
225
226#[inline]
227fn intersect(dominators: &[usize], mut finger1: usize, mut finger2: usize) -> usize {
228    loop {
229        match finger1.cmp(&finger2) {
230            Ordering::Less => finger1 = dominators[finger1],
231            Ordering::Equal => return finger1,
232            Ordering::Greater => finger2 = dominators[finger2],
233        }
234    }
235}
236
237#[cfg(test)]
238mod tests {
239    use crate::{LinkMut, PortMut};
240
241    use super::*;
242
243    #[test]
244    fn test_dominators_small() {
245        //     ┏> b ┓
246        //  a ─┫    ┣─> c ─> e
247        //     ┗> d ┛
248        let mut graph = PortGraph::with_capacity(5, 10);
249        let a = graph.add_node(0, 2);
250        let b = graph.add_node(1, 1);
251        let c = graph.add_node(2, 1);
252        let d = graph.add_node(1, 1);
253        let e = graph.add_node(1, 0);
254
255        graph.link_nodes(a, 0, b, 0).unwrap();
256        graph.link_nodes(a, 1, d, 0).unwrap();
257        graph.link_nodes(b, 0, c, 0).unwrap();
258        graph.link_nodes(d, 0, c, 1).unwrap();
259        graph.link_nodes(c, 0, e, 0).unwrap();
260
261        // From `a`
262        let tree: DominatorTree = dominators(&graph, a, Direction::Outgoing);
263        assert_eq!(tree.root(), a);
264        assert_eq!(tree.immediate_dominator(a), None);
265        assert_eq!(tree.immediate_dominator(b), Some(a));
266        assert_eq!(tree.immediate_dominator(c), Some(a));
267        assert_eq!(tree.immediate_dominator(d), Some(a));
268        assert_eq!(tree.immediate_dominator(e), Some(c));
269
270        // Backwards from `c`
271        let tree: DominatorTree = dominators(&graph, c, Direction::Incoming);
272        assert_eq!(tree.root(), c);
273        assert_eq!(tree.immediate_dominator(a), Some(c));
274        assert_eq!(tree.immediate_dominator(b), Some(c));
275        assert_eq!(tree.immediate_dominator(c), None);
276        assert_eq!(tree.immediate_dominator(d), Some(c));
277        assert_eq!(tree.immediate_dominator(e), None);
278    }
279
280    #[test]
281    fn test_dominators_filtered() {
282        // a ─┬> b ┐
283        //    │    ├─> c ─> e
284        // f ─┴> d ┴────────^
285        let mut graph = PortGraph::with_capacity(5, 10);
286        let a = graph.add_node(0, 2);
287        let b = graph.add_node(1, 1);
288        let c = graph.add_node(2, 1);
289        let d = graph.add_node(2, 2);
290        let e = graph.add_node(2, 0);
291        let f = graph.add_node(0, 1);
292
293        graph.link_nodes(a, 0, b, 0).unwrap();
294        graph.link_nodes(a, 1, d, 0).unwrap();
295        graph.link_nodes(b, 0, c, 0).unwrap();
296        graph.link_nodes(d, 0, c, 1).unwrap();
297        graph.link_nodes(c, 0, e, 0).unwrap();
298        graph.link_nodes(d, 1, e, 1).unwrap();
299        graph.link_nodes(f, 0, d, 1).unwrap();
300
301        // From `a`
302        let tree: DominatorTree = dominators_filtered(
303            &graph,
304            a,
305            Direction::Outgoing,
306            |node| node != f,
307            |_, p| Some(p) != graph.input(e, 1),
308        );
309        assert_eq!(tree.root(), a);
310        assert_eq!(tree.immediate_dominator(a), None);
311        assert_eq!(tree.immediate_dominator(b), Some(a));
312        assert_eq!(tree.immediate_dominator(c), Some(a));
313        assert_eq!(tree.immediate_dominator(d), Some(a));
314        assert_eq!(tree.immediate_dominator(e), Some(c));
315        assert_eq!(tree.immediate_dominator(f), None);
316
317        // Backwards from `c`
318        let tree: DominatorTree = dominators(&graph, c, Direction::Incoming);
319        assert_eq!(tree.root(), c);
320        assert_eq!(tree.immediate_dominator(a), Some(c));
321        assert_eq!(tree.immediate_dominator(b), Some(c));
322        assert_eq!(tree.immediate_dominator(c), None);
323        assert_eq!(tree.immediate_dominator(d), Some(c));
324        assert_eq!(tree.immediate_dominator(e), None);
325    }
326
327    #[test]
328    fn test_dominators_complex() {
329        // This graph is taken from the paper "A Simple, Fast Dominance Algorithm"
330        // by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy.
331        // Figure 4, page 8.
332        let mut graph = PortGraph::with_capacity(6, 18);
333        let entry = graph.add_node(0, 2);
334        let a = graph.add_node(1, 1);
335        let b = graph.add_node(1, 2);
336        let c = graph.add_node(2, 1);
337        let d = graph.add_node(3, 2);
338        let e = graph.add_node(2, 1);
339
340        graph.link_nodes(entry, 0, a, 0).unwrap();
341        graph.link_nodes(entry, 1, b, 0).unwrap();
342        graph.link_nodes(a, 0, c, 0).unwrap();
343        graph.link_nodes(b, 0, d, 0).unwrap();
344        graph.link_nodes(b, 1, e, 0).unwrap();
345        graph.link_nodes(c, 0, d, 1).unwrap();
346        graph.link_nodes(d, 0, c, 1).unwrap();
347        graph.link_nodes(d, 1, e, 1).unwrap();
348        graph.link_nodes(e, 0, d, 2).unwrap();
349
350        let dominators: DominatorTree = dominators(&graph, entry, Direction::Outgoing);
351
352        assert_eq!(dominators.root(), entry);
353        assert_eq!(dominators.immediate_dominator(entry), None);
354        assert_eq!(dominators.immediate_dominator(a), Some(entry));
355        assert_eq!(dominators.immediate_dominator(b), Some(entry));
356        assert_eq!(dominators.immediate_dominator(c), Some(entry));
357        assert_eq!(dominators.immediate_dominator(d), Some(entry));
358        assert_eq!(dominators.immediate_dominator(e), Some(entry));
359    }
360}
portgraph/algorithms/dominators.rs

portgraph/algorithms/
dominators.rs
