Struct DomTree 

pub struct DomTree { /* private fields */ }

The dominator tree of a computation graph.

The tree is rooted at a virtual root node that is not part of the original graph. Every real node has a unique immediate dominator, except source nodes whose only dominator is the virtual root (represented by idom(n) == None).

Implementations

impl DomTree

pub fn idom(&self, node: NodeId) -> Option<NodeId>

Returns the immediate dominator of node, or None if it is a root.

pub fn children(&self, node: NodeId) -> &[NodeId]

Returns the children of node in the dominator tree.

pub fn roots(&self) -> Vec<NodeId>

Returns all root nodes (nodes with no immediate dominator in the real graph).

pub fn dominates(&self, dominator: NodeId, node: NodeId) -> bool

Returns true if dominator dominates node.

A node always dominates itself.

pub fn dominated_by(&self, root: NodeId) -> Vec<NodeId>

Returns the set of nodes dominated by root (its subtree), including root itself.

pub fn depth(&self, node: NodeId) -> usize

Returns the depth of node in the dominator tree (root = 0).

pub fn lca(&self, a: NodeId, b: NodeId) -> NodeId

Returns the lowest common ancestor of two nodes in the dominator tree.

If one node dominates the other, it is the LCA.

Trait Implementations

impl Clone for DomTree

fn clone(&self) -> DomTree

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for DomTree

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.