domtree

domtree提供了一种通用的实现，用于计算有向图的支配树。该算法基本上遵循Keith D. Cooper、Timothy J. Harvey和Ken Kennedy在"A Simple, Fast Dominance Algorithm"中的描述。要为您的自定义图结构实现trait，您需要准备几个字段

#[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>,
}

然后，您需要首先公开一些API，以便这个crate可以在图上运行DFS。

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()
    }
}

然后，您还需要指定算法如何访问与支配树相关的字段。

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()
    }
}

然后，您只需运行填充支配树和支配边界即可

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