use alloc::collections::BinaryHeap;
use alloc::vec;
use alloc::vec::Vec;
use core::cmp::Reverse;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Transition {
pub src: usize,
pub label: usize,
pub dst: usize,
}
#[derive(Clone, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct LabeledTransitionSystem {
pub num_states: usize,
pub num_labels: usize,
pub transitions: Vec<Transition>,
pub goal: Vec<bool>,
pub initial: Option<usize>,
}
impl LabeledTransitionSystem {
pub fn goal_distances(&self, costs: &[u64]) -> Vec<Option<u64>> {
dijkstra(
&self.adjacency(costs, true),
self.goal.iter().enumerate().filter(|g| *g.1).map(|g| g.0),
)
}
pub fn init_distances(&self, costs: &[u64]) -> Vec<Option<u64>> {
dijkstra(&self.adjacency(costs, false), self.initial)
}
fn adjacency(&self, costs: &[u64], reverse: bool) -> Vec<Vec<(usize, u64)>> {
assert_eq!(costs.len(), self.num_labels, "one cost per label");
let mut adj = vec![Vec::new(); self.num_states];
for t in self.transitions.iter().filter(|t| t.src != t.dst) {
let (from, to) = if reverse {
(t.dst, t.src)
} else {
(t.src, t.dst)
};
adj[from].push((to, costs[t.label]));
}
adj
}
pub fn normalize(&mut self) {
self.transitions.sort_unstable();
self.transitions.dedup();
}
}
fn dijkstra(
adj: &[Vec<(usize, u64)>],
sources: impl IntoIterator<Item = usize>,
) -> Vec<Option<u64>> {
let mut dist = vec![None; adj.len()];
let mut heap = BinaryHeap::new();
for s in sources {
dist[s] = Some(0);
heap.push(Reverse((0u64, s)));
}
while let Some(Reverse((d, s))) = heap.pop() {
if dist[s].is_some_and(|best| d > best) {
continue;
}
for &(t, c) in &adj[s] {
let nd = d + c;
if dist[t].is_none_or(|old| nd < old) {
dist[t] = Some(nd);
heap.push(Reverse((nd, t)));
}
}
}
dist
}