weavatrix_graph/algo/all_pairs/
core.rs

1use super::super::SignedPath;
2use crate::IndexGraphView;
3use crate::Vec;
4
5#[derive(Debug, Clone)]
6pub struct AllPairsShortestPaths<Node> {
7    pub(super) nodes: Vec<Node>,
8    pub(super) by_slot: Vec<Option<Node>>,
9    pub(super) distances: Vec<i64>,
10    pub(super) reachable: Vec<bool>,
11    pub(super) next: Vec<Option<usize>>,
12    pub(super) bound: usize,
13    pub(super) node_slot: fn(Node) -> usize,
14}
15
16impl<Node: Copy + Eq> AllPairsShortestPaths<Node> {
17    #[must_use]
18    pub fn nodes(&self) -> &[Node] {
19        &self.nodes
20    }
21
22    #[must_use]
23    pub fn distance(&self, source: Node, target: Node) -> Option<i64> {
24        let (source, target) = self.slots(source, target)?;
25        let index = cell(self.bound, source, target);
26        self.reachable[index].then_some(self.distances[index])
27    }
28
29    #[must_use]
30    pub fn path(&self, source: Node, target: Node) -> Option<SignedPath<Node>> {
31        let total_cost = self.distance(source, target)?;
32        let (source_slot, target_slot) = self.slots(source, target)?;
33        let mut slot = source_slot;
34        let mut nodes = vec![source];
35        while slot != target_slot {
36            slot = self.next[cell(self.bound, slot, target_slot)]?;
37            nodes.push(self.by_slot[slot]?);
38            if nodes.len() > self.nodes.len() {
39                return None;
40            }
41        }
42        Some(SignedPath::from_parts(nodes, total_cost))
43    }
44
45    fn slots(&self, source: Node, target: Node) -> Option<(usize, usize)> {
46        let source_slot = (self.node_slot)(source);
47        let target_slot = (self.node_slot)(target);
48        (self.by_slot.get(source_slot) == Some(&Some(source))
49            && self.by_slot.get(target_slot) == Some(&Some(target)))
50        .then_some((source_slot, target_slot))
51    }
52}
53
54pub(super) fn indexed_nodes<G: IndexGraphView>(graph: &G) -> (Vec<G::Node>, Vec<Option<G::Node>>) {
55    let mut nodes = graph.node_indices().collect::<Vec<_>>();
56    nodes.sort_unstable_by_key(|node| G::node_slot(*node));
57    let mut by_slot = vec![None; graph.node_bound()];
58    for &node in &nodes {
59        by_slot[G::node_slot(node)] = Some(node);
60    }
61    (nodes, by_slot)
62}
63
64pub(super) const fn cell(bound: usize, source: usize, target: usize) -> usize {
65    source * bound + target
66}
weavatrix_graph/algo/all_pairs/core.rs

weavatrix_graph/algo/all_pairs/
core.rs
