Struct ReachabilityAnalysis 

pub struct ReachabilityAnalysis {
    pub reachable_from: HashMap<usize, HashSet<usize>>,
    pub can_reach: HashMap<usize, HashSet<usize>>,
    pub sccs: Vec<HashSet<usize>>,
    pub topo_order: Option<Vec<usize>>,
}

Result of reachability analysis.

Fields

reachable_from: HashMap<usize, HashSet<usize>>

Which nodes can be reached from each node

can_reach: HashMap<usize, HashSet<usize>>

Which nodes can reach each node

sccs: Vec<HashSet<usize>>

Strongly connected components

topo_order: Option<Vec<usize>>

Topological ordering (if DAG)

Implementations

impl ReachabilityAnalysis

pub fn new() -> Self

Create a new reachability analysis.

pub fn is_reachable(&self, from: usize, to: usize) -> bool

Check if node to is reachable from node from.

pub fn get_reachable(&self, from: usize) -> HashSet<usize>

Get all nodes reachable from a given node.

pub fn get_predecessors(&self, to: usize) -> HashSet<usize>

Get all nodes that can reach a given node.

pub fn is_dag(&self) -> bool

Check if the graph is a DAG (has topological ordering).

pub fn get_topo_order(&self) -> Option<&[usize]>

Get the topological order if it exists.

pub fn get_scc(&self, node: usize) -> Option<&HashSet<usize>>

Get strongly connected component containing a node.

Trait Implementations

impl Clone for ReachabilityAnalysis

fn clone(&self) -> ReachabilityAnalysis

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for ReachabilityAnalysis

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

Formats the value using the given formatter.

impl Default for ReachabilityAnalysis

fn default() -> Self

Returns the “default value” for a type.