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