cch_rs/cch/
path.rs

1//! Path extraction and shortcut unpacking.
2//!
3//! The query phase returns a path composed of shortcut arcs in the contracted hierarchy.
4//! This module recursively unpacks those shortcuts using the `Shortcuts` data generated
5//! during the customization phase, yielding the final sequence of original graph nodes.
6
7use crate::cch::Cch;
8use crate::cch::customize::Shortcuts;
9use crate::cch::query::{Query, QueryResult, QuerySlot};
10
11impl Cch {
12    pub fn unpack(&self, rank_path: Vec<u32>, shortcuts: &Shortcuts) -> Vec<u32> {
13        if rank_path.len() < 2 {
14            return rank_path.into_iter().map(|r| self.order[r as usize]).collect();
15        }
16        let mut path = Vec::with_capacity(rank_path.len() * 2);
17        path.push(self.order[rank_path[0] as usize]);
18        rank_path.windows(2).for_each(|w| self.unpack_edge(w[0], w[1], shortcuts, &mut path));
19        path
20    }
21
22    fn unpack_edge(&self, u: u32, v: u32, sc: &Shortcuts, out: &mut Vec<u32>) {
23        let (low, high) = if u < v { (u, v) } else { (v, u) };
24        let arc_id = unsafe { self.topology.find_edge_id(low, high).expect("CCH arc must exist") as usize };
25        let mid = if u < v { sc.middles[arc_id].up } else { sc.middles[arc_id].down };
26        if mid != u32::MAX {
27            self.unpack_edge(u, mid, sc, out);
28            self.unpack_edge(mid, v, sc, out);
29        } else {
30            out.push(self.order[v as usize]);
31        }
32    }
33
34    pub fn query_path(&self, q: &Query, sc: &Shortcuts, res: &QueryResult) -> Vec<u32> {
35        let get_path = |start: u32, side: &[QuerySlot]| -> Vec<u32> {
36            std::iter::successors(Some(start).filter(|&n| n != u32::MAX), |&curr| {
37                let p = unsafe { side.get_unchecked(curr as usize).parent_node };
38                Some(p).filter(|&n| n != u32::MAX)
39            })
40            .collect()
41        };
42        let mut path = get_path(res.meeting, &q.fw);
43        path.reverse();
44        let bw_path = get_path(res.meeting, &q.bw);
45        path.extend(bw_path.into_iter().skip(1));
46        self.unpack(path, sc)
47    }
48}
cch_rs/cch/path.rs

cch_rs/cch/
path.rs
