Skip to main content

sas_plus/
lts.rs

1use alloc::collections::BinaryHeap;
2use alloc::vec;
3use alloc::vec::Vec;
4use core::cmp::Reverse;
5
6#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
7pub struct Transition {
8    pub src: usize,
9    pub label: usize,
10    pub dst: usize,
11}
12
13/// An explicit labeled transition system. Self-loops are kept: they matter
14/// for synchronized products (merge-and-shrink), and are ignored where they
15/// are irrelevant (distances, saturated costs).
16#[derive(Clone, Debug)]
17pub struct LabeledTransitionSystem {
18    pub num_states: usize,
19    pub num_labels: usize,
20    pub transitions: Vec<Transition>,
21    pub goal: Vec<bool>,
22    pub initial: Option<usize>,
23}
24
25impl LabeledTransitionSystem {
26    /// Cheapest cost to reach a goal state from each state, under `costs`
27    /// (indexed by label). `None` = no goal reachable.
28    pub fn goal_distances(&self, costs: &[u64]) -> Vec<Option<u64>> {
29        dijkstra(
30            &self.adjacency(costs, true),
31            self.goal.iter().enumerate().filter(|g| *g.1).map(|g| g.0),
32        )
33    }
34
35    /// Cheapest cost from the initial state to each state.
36    pub fn init_distances(&self, costs: &[u64]) -> Vec<Option<u64>> {
37        dijkstra(&self.adjacency(costs, false), self.initial)
38    }
39
40    /// Weighted edges per state, without self-loops; `reverse` follows
41    /// transitions backwards.
42    fn adjacency(&self, costs: &[u64], reverse: bool) -> Vec<Vec<(usize, u64)>> {
43        assert_eq!(costs.len(), self.num_labels, "one cost per label");
44        let mut adj = vec![Vec::new(); self.num_states];
45        for t in self.transitions.iter().filter(|t| t.src != t.dst) {
46            let (from, to) = if reverse {
47                (t.dst, t.src)
48            } else {
49                (t.src, t.dst)
50            };
51            adj[from].push((to, costs[t.label]));
52        }
53        adj
54    }
55
56    /// Sorts transitions and removes duplicates.
57    pub fn normalize(&mut self) {
58        self.transitions.sort_unstable();
59        self.transitions.dedup();
60    }
61}
62
63fn dijkstra(
64    adj: &[Vec<(usize, u64)>],
65    sources: impl IntoIterator<Item = usize>,
66) -> Vec<Option<u64>> {
67    let mut dist = vec![None; adj.len()];
68    let mut heap = BinaryHeap::new();
69    for s in sources {
70        dist[s] = Some(0);
71        heap.push(Reverse((0u64, s)));
72    }
73    while let Some(Reverse((d, s))) = heap.pop() {
74        if dist[s].is_some_and(|best| d > best) {
75            continue;
76        }
77        for &(t, c) in &adj[s] {
78            let nd = d + c;
79            if dist[t].is_none_or(|old| nd < old) {
80                dist[t] = Some(nd);
81                heap.push(Reverse((nd, t)));
82            }
83        }
84    }
85    dist
86}