1
use log::trace;
2

            
3
use crate::{LTS, StateIndex};
4

            
5
/// Performs a reachability analysis on the given LTS using a depth-first search
6
/// from the initial state.
7
///
8
/// Returns the list of reachable states, where the i-th element is true iff
9
/// state i is reachable.
10
400
pub fn reachability<L: LTS>(lts: &L, state: StateIndex) -> Vec<bool> {
11
400
    let mut reachable = vec![false; lts.num_of_states()];
12
400
    reachable[state] = true;
13

            
14
400
    let mut stack = vec![state];
15

            
16
2142
    while let Some(state) = stack.pop() {
17
1742
        debug_assert!(reachable[state], "State {} must already be marked as reachable", state);
18
1742
        trace!("Visiting {}", state);
19

            
20

            
21
2372
        for transition in lts.outgoing_transitions(state) {
22
2372
            if !reachable[transition.to] {
23
1342
                trace!("Transition -[{}]-> {}", transition.label, transition.to);
24
1342
                reachable[transition.to] = true;
25
1342
                stack.push(transition.to);
26
1030
            }
27
        }
28
    }
29

            
30
400
    trace!("Finished reachability");
31
400
    reachable
32
400
}
33

            
34
/// Returns the number of states reachable from the given state of the LTS.
35
400
pub fn num_reachable_states<L: LTS>(lts: &L, state: StateIndex) -> usize {
36
400
    reachability(lts, state).iter().filter(|&&r| r).count()
37
400
}