nordisk/nornir

crates/mimir-room/src/path.rs

//! A → B: one shortest path along the chosen edge kinds, with the kind each
//! hop walked. BFS layers from the sources (MIN_PLUS), then one backward
//! step per hop (`A ANY.PAIR q`) picking the predecessor one layer up.

use anyhow::Result;
use mimir_graph::{Vector, ops};
use mimir_schema::EdgeKind;
use serde::Serialize;

use crate::Room;
use crate::evidence::Answer;
use crate::query::{Mask, Seeds};
use crate::snapshot::kind_bit;

/// One shortest path.
#[derive(Debug, Clone, PartialEq, Eq, Serialize)]
pub struct PathFound {
    /// The nodes, source first, target last.
    pub nodes: Vec<u64>,
    /// The kind each hop walked (`nodes.len() - 1` of them): when several of
    /// the requested kinds join the two nodes, the first in the order asked.
    #[serde(serialize_with = "ser_kinds")]
    pub kinds: Vec<EdgeKind>,
}

fn ser_kinds<S: serde::Serializer>(v: &[EdgeKind], s: S) -> std::result::Result<S::Ok, S::Error> {
    s.collect_seq(v.iter().map(|k| k.as_str()))
}

impl PathFound {
    /// Number of edges.
    pub fn hops(&self) -> usize {
        self.kinds.len()
    }
}

impl Room {
    /// A shortest path from any node of `from` to any node of `to` along
    /// `kinds` (at most `max_hops` edges; inside `within` when given).
    /// `None` = no such path in this room — the evidence says whether that
    /// is a fact or a gap (a kind without edges, an unknown end, the ring
    /// off). Among equally short paths: the target with the smallest
    /// ordinal, then at every hop the predecessor with the smallest ordinal
    /// (deterministic). A node in both sets is the zero-hop path.
    pub fn path<'a, 'b>(
        &self,
        from: impl Into<Seeds<'a>>,
        to: impl Into<Seeds<'b>>,
        kinds: &[EdgeKind],
        max_hops: Option<u32>,
        within: Option<&Mask>,
    ) -> Result<Answer<Option<PathFound>>> {
        let (from, to) = (from.into(), to.into());
        let mut ev = self.evidence(format!("path({kinds:?}, max_hops {max_hops:?})"), kinds.contains(&EdgeKind::InstanceOf), kinds);
        self.walk_note(&mut ev);
        let src = self.seeds(from, &mut ev)?;
        let dst = self.seeds(to, &mut ev)?;
        let ends: Vec<u64> = src.iter().chain(&dst).copied().collect();
        self.within_note(&mut ev, within, &ends);
        if src.is_empty() || dst.is_empty() {
            return Ok(Answer::new(None, ev));
        }
        let mask = kinds.iter().map(|k| kind_bit(*k)).fold(0, |a, b| a | b);
        let mut g = self.graphs();
        let n = g.n;
        let nodes = {
            // unscoped: the cached transpose answers each hop's predecessors
            // by ROW (`Aᵀ(cur, :)`), and the hop layers stop at the first one
            // holding a target — the same path, without walking everything
            // the sources reach nor a whole-matrix product per hop
            let pair = if within.is_none() { g.get_pair(mask)? } else { None };
            let scoped;
            let (a, at) = match pair {
                Some((a, at)) => (a, Some(at)),
                None => {
                    let Some(a) = g.get(mask, false)? else { return Ok(Answer::new(None, ev)) };
                    scoped = match within {
                        Some(m) => {
                            self.check_mask(m)?;
                            Some(ops::mask_by(a, &m.vector()?)?)
                        }
                        None => None,
                    };
                    (scoped.as_ref().unwrap_or(a), None)
                }
            };
            let dist = ops::min_hops_to(&Vector::<bool>::from_indices(n, &src)?, a, max_hops, &dst)?;
            // the nearest target (fewest hops, then smallest ordinal)
            let mut best: Option<(u64, u64)> = None;
            for t in &dst {
                if let Some(d) = dist.get(*t)?
                    && best.is_none_or(|(bd, _)| d < bd)
                {
                    best = Some((d, *t));
                }
            }
            let Some((d, target)) = best else { return Ok(Answer::new(None, ev)) };
            let mut nodes = vec![target];
            let mut cur = target;
            for layer in (0..d).rev() {
                // predecessors of `cur`, one hop back, by ordinal
                let preds: Vec<u64> = match at {
                    Some(at) => at.row_edges(&[cur])?.into_iter().map(|(_, p)| p).collect(),
                    None => ops::reverse_reach(&Vector::<bool>::from_indices(n, &[cur])?, a, Some(1))?.indices()?,
                };
                let mut pick = None;
                for p in preds {
                    if p != cur && dist.get(p)? == Some(layer) {
                        pick = Some(p);
                        break;
                    }
                }
                let Some(p) = pick else {
                    anyhow::bail!("path: node {cur} at hop {} has no predecessor at hop {layer} (the hop layers and the adjacency disagree)", layer + 1);
                };
                nodes.push(p);
                cur = p;
            }
            nodes.reverse();
            nodes
        };
        // the kind of every hop: the first requested kind holding that edge
        let mut walked = Vec::with_capacity(nodes.len().saturating_sub(1));
        for w in nodes.windows(2) {
            let mut found = None;
            for k in kinds {
                if let Some(m) = g.a.get(k)
                    && m.get(w[0], w[1])?.is_some()
                {
                    found = Some(*k);
                    break;
                }
            }
            match found {
                Some(k) => walked.push(k),
                None => anyhow::bail!("path: no requested kind joins {} → {}", w[0], w[1]),
            }
        }
        drop(g);
        Ok(Answer::new(Some(PathFound { nodes, kinds: walked }), ev))
    }
}