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#[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 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 pub fn init_distances(&self, costs: &[u64]) -> Vec<Option<u64>> {
39 dijkstra(&self.adjacency(costs, false), self.initial)
40 }
41
42 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 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}