domtree

domtree provides a generic implementation to calculate the dominator tree of a directed graph. The algorithm basically follows the description in "A Simple, Fast Dominance Algorithm" by Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy. To implement the trait for your own graph structure, you need to prepare several fields:

#[derive(Clone)]
struct VecSet<Y>(Vec<Y>);
impl<Y: Clone + Default> AssocSet<usize, Y> for VecSet<Y> {
    fn get(&self, target: usize) -> Y {
        self.0[target].clone()
    }
    fn set(&mut self, key: usize, val: Y) {
        self.0[key] = val;
    }
}
#[derive(Clone, Debug)]
struct HashMemberSet<T>(HashSet<T>);

impl<T: PartialEq + Eq + Hash + Clone> MemberSet<T> for HashMemberSet<T> {
    fn contains(&self, target: T) -> bool {
        self.0.contains(&target)
    }

    fn insert(&mut self, target: T) {
        self.0.insert(target);
    }

    type MemberIter<'a> = Cloned<std::collections::hash_set::Iter<'a, T>> where Self : 'a;

    fn iter<'a>(&'a self) -> Self::MemberIter<'a> {
        self.0.iter().cloned()
    }
}

impl<T: PartialEq + Eq + Hash + Clone> MergeSet<T> for HashMemberSet<T> {
    fn subset(&self, other: &Self) -> bool {
        self.0.is_subset(&other.0)
    }

    fn union(&mut self, other: &Self) {
        for i in other.0.iter().cloned() {
            self.0.insert(i);
        }
    }
}
#[derive(Debug)]
struct Node {
    tag: usize,                                  // node's identifier
    dom: Option<usize>,                          // node's immediate dominator
    frontiers: UnsafeCell<HashMemberSet<usize>>, // node's dominance frontiers
    incoming_edges: Vec<usize>,                  // node's in-edges
    outgoing_edges: Vec<usize>                   // node's out-edges
}
#[derive(Debug)]
struct Graph {
    nodes: Vec<Node>,
}

Then, one needs to first expose some APIs such that this crate can run DFS on the graph.

use std::iter::Cloned;
use std::slice::Iter;
use domtree::dfs::DFSGraph;
impl DFSGraph for Graph {
    type Identifier = usize;
    type Set<Y> = VecSet<Y>  where Y: Clone + Default;
    type SuccessorIter<'a> = Cloned<Iter<'a, usize>> where Self: 'a;
    fn create_set<Y>(&self) -> Self::Set<Y> where Y: Clone + Default {
        let mut data = Vec::new();
        data.resize(self.nodes.len(), Default::default());
        VecSet(data)
    }
    fn outgoing_edges<'a>(&'a self, id: Self::Identifier) -> Self::SuccessorIter<'a> {
        self.nodes[id].outgoing_edges.iter().cloned()
    }
}

After this, one also need to specify how the algorithm can access the fields related to the dominance tree.

impl DomTree for Graph {
    type MutDomIter<'a> = Map<IterMut<'a, Node>, fn(&'a mut Node)->&'a mut Option<usize>> where Self: 'a;
    type PredecessorIter<'a> = Cloned<Iter<'a, usize>> where Self: 'a;
    fn dom(&self, id: Self::Identifier) -> Option<Self::Identifier> {
        self.nodes[id].dom.clone()
    }
    fn set_dom(&mut self, id: Self::Identifier, target: Option<Self::Identifier>) {
        self.nodes[id].dom = target;
    }
    fn predecessor_iter<'a>(&'a self, id: Self::Identifier) -> Self::PredecessorIter<'a> {
        self.nodes[id].incoming_edges.iter().cloned()
    }
    fn doms_mut<'a>(&'a mut self) -> Self::MutDomIter<'a> {
        self.nodes.iter_mut().map(|x|&mut x.dom)
    }
}
impl DominanceFrontier for Graph {
    type FrontierSet = HashMemberSet<usize>;
    type NodeIter<'a> = Range<usize> where Self: 'a ;
    fn frontiers_cell(&self, id: Self::Identifier) -> &UnsafeCell<Self::FrontierSet> {
        &self.nodes[id].frontiers
    }
    fn node_iter<'a>(&'a self) -> Self::NodeIter<'a> {
        0..self.nodes.len()
    }
}

Then, one can just run populate the dominance tree and the dominance frontiers

let mut g = random_graph(10000);
dump_graph(&g);
g.populate_dom(0);
g.populate_frontiers();