1
use merc_lts::{LTS, StateIndex};
2

            
3
/// Computes the length of the longest path consisting solely of tau (hidden) transitions in the given LTS.
4
///
5
/// # Details
6
///
7
/// Assumes that the LTS does not contain any tau-cycles.
8
pub fn longest_tau_path(lts: &impl LTS) -> Vec<StateIndex> {
9
    let mut length = vec![0usize; lts.num_of_states()];
10
    let mut next = vec![None; lts.num_of_states()];
11

            
12
    loop {
13
        // For topologically sorted states, a single pass is sufficient, but this generalises to any order.
14
        let mut changed = false;
15

            
16
        for state in lts.iter_states() {
17
            for transition in lts
18
                .outgoing_transitions(state)
19
                .filter(|transition| lts.is_hidden_label(transition.label))
20
            {
21
                let new_length = length[transition.to] + 1;
22
                if new_length > length[state] {
23
                    length[state] = new_length;
24
                    next[state] = Some(transition.to);
25
                    changed = true;
26
                }
27
            }
28
        }
29

            
30
        if !changed {
31
            break;
32
        }
33
    }
34

            
35
    // Find the state with the longest path
36
    let (max_state, &max_length) = length
37
        .iter()
38
        .enumerate()
39
        .max_by_key(|(_, len)| **len)
40
        .unwrap_or((0, &0));
41

            
42
    // Reconstruct the path
43
    let mut path = Vec::with_capacity(max_length + 1);
44
    let mut current = StateIndex::new(max_state);
45
    path.push(current);
46
    
47
    while let Some(next_state) = next[current] {
48
        path.push(next_state);
49
        current = next_state;
50
    }
51

            
52
    path
53
}