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