facett_graphview/analysis/

pathfinding.rs

//! **Pathfinding** — BFS / DFS orders, shortest paths (unweighted BFS + weighted
//! Dijkstra), and all simple paths between two nodes. Directed (over the `out` view);
//! pass an [`Adjacency`] built from undirected-doubled edges for undirected search.

use std::cmp::Ordering;
use std::collections::{BinaryHeap, VecDeque};

use super::Adjacency;

/// **BFS** order from `s` over the directed `out` view (nodes in the order first
/// visited). Includes `s` first.
#[must_use]
pub fn bfs(g: &Adjacency, s: usize) -> Vec<usize> {
    if s >= g.n {
        return Vec::new();
    }
    let mut seen = vec![false; g.n];
    let mut order = Vec::new();
    let mut q = VecDeque::new();
    seen[s] = true;
    q.push_back(s);
    while let Some(v) = q.pop_front() {
        order.push(v);
        for &(w, _) in &g.out[v] {
            if !seen[w] {
                seen[w] = true;
                q.push_back(w);
            }
        }
    }
    order
}

/// **DFS** pre-order from `s` over the directed `out` view (lowest-index neighbour
/// first, so it's deterministic). Includes `s` first.
#[must_use]
pub fn dfs(g: &Adjacency, s: usize) -> Vec<usize> {
    if s >= g.n {
        return Vec::new();
    }
    let mut seen = vec![false; g.n];
    let mut order = Vec::new();
    let mut stack = vec![s];
    seen[s] = true;
    // To emit lowest-index-first we push neighbours in reverse onto the stack.
    while let Some(v) = stack.pop() {
        order.push(v);
        let mut nbrs: Vec<usize> = g.out[v].iter().map(|&(w, _)| w).collect();
        nbrs.sort_unstable();
        for &w in nbrs.iter().rev() {
            if !seen[w] {
                seen[w] = true;
                stack.push(w);
            }
        }
    }
    order
}

/// **Unweighted shortest path** (BFS) from `s` to `t` over the directed `out` view.
/// Returns the node sequence `[s, …, t]`, or `None` if `t` is unreachable.
#[must_use]
pub fn shortest_path(g: &Adjacency, s: usize, t: usize) -> Option<Vec<usize>> {
    if s >= g.n || t >= g.n {
        return None;
    }
    if s == t {
        return Some(vec![s]);
    }
    let mut prev = vec![usize::MAX; g.n];
    let mut seen = vec![false; g.n];
    let mut q = VecDeque::new();
    seen[s] = true;
    q.push_back(s);
    while let Some(v) = q.pop_front() {
        for &(w, _) in &g.out[v] {
            if !seen[w] {
                seen[w] = true;
                prev[w] = v;
                if w == t {
                    return Some(reconstruct(&prev, s, t));
                }
                q.push_back(w);
            }
        }
    }
    None
}

/// **Weighted shortest path** (Dijkstra) from `s` to `t` over the directed `out`
/// view. Edge weights must be non-negative. Returns `(path, cost)` or `None`.
#[must_use]
pub fn dijkstra(g: &Adjacency, s: usize, t: usize) -> Option<(Vec<usize>, f32)> {
    if s >= g.n || t >= g.n {
        return None;
    }
    let mut dist = vec![f32::INFINITY; g.n];
    let mut prev = vec![usize::MAX; g.n];
    dist[s] = 0.0;
    let mut heap = BinaryHeap::new();
    heap.push(HeapItem { cost: 0.0, node: s });
    while let Some(HeapItem { cost, node }) = heap.pop() {
        if node == t {
            return Some((reconstruct(&prev, s, t), cost));
        }
        if cost > dist[node] {
            continue;
        }
        for &(w, weight) in &g.out[node] {
            let nc = cost + weight.max(0.0);
            if nc < dist[w] {
                dist[w] = nc;
                prev[w] = node;
                heap.push(HeapItem { cost: nc, node: w });
            }
        }
    }
    None
}

/// **All simple paths** from `s` to `t` (no repeated node), each up to `max_len`
/// nodes long (a guard against exponential blow-up on dense graphs). Directed.
#[must_use]
pub fn all_simple_paths(g: &Adjacency, s: usize, t: usize, max_len: usize) -> Vec<Vec<usize>> {
    let mut out = Vec::new();
    if s >= g.n || t >= g.n || max_len == 0 {
        return out;
    }
    let mut on_path = vec![false; g.n];
    let mut path = vec![s];
    on_path[s] = true;
    dfs_paths(g, s, t, max_len, &mut on_path, &mut path, &mut out);
    out
}

fn dfs_paths(
    g: &Adjacency,
    v: usize,
    t: usize,
    max_len: usize,
    on_path: &mut [bool],
    path: &mut Vec<usize>,
    out: &mut Vec<Vec<usize>>,
) {
    if v == t {
        out.push(path.clone());
        return;
    }
    if path.len() >= max_len {
        return;
    }
    let mut nbrs: Vec<usize> = g.out[v].iter().map(|&(w, _)| w).collect();
    nbrs.sort_unstable();
    for w in nbrs {
        if !on_path[w] {
            on_path[w] = true;
            path.push(w);
            dfs_paths(g, w, t, max_len, on_path, path, out);
            path.pop();
            on_path[w] = false;
        }
    }
}

/// Walk `prev` back from `t` to `s` into a forward path.
fn reconstruct(prev: &[usize], s: usize, t: usize) -> Vec<usize> {
    let mut path = vec![t];
    let mut cur = t;
    while cur != s {
        cur = prev[cur];
        path.push(cur);
    }
    path.reverse();
    path
}

/// A min-heap item (Dijkstra) — ordered by cost ascending.
struct HeapItem {
    cost: f32,
    node: usize,
}
impl PartialEq for HeapItem {
    fn eq(&self, o: &Self) -> bool {
        self.cost == o.cost && self.node == o.node
    }
}
impl Eq for HeapItem {}
impl PartialOrd for HeapItem {
    fn partial_cmp(&self, o: &Self) -> Option<Ordering> {
        Some(self.cmp(o))
    }
}
impl Ord for HeapItem {
    fn cmp(&self, o: &Self) -> Ordering {
        // Reverse so BinaryHeap (a max-heap) pops the smallest cost first.
        o.cost.partial_cmp(&self.cost).unwrap_or(Ordering::Equal).then(o.node.cmp(&self.node))
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn diamond() -> Adjacency {
        // 0→1, 0→2, 1→3, 2→3 — two length-2 routes from 0 to 3.
        Adjacency::from_edges(4, &[(0, 1), (0, 2), (1, 3), (2, 3)])
    }

    #[test]
    fn bfs_and_dfs_visit_every_reachable_node() {
        let g = diamond();
        let b = bfs(&g, 0);
        assert_eq!(b[0], 0);
        assert_eq!(b.len(), 4);
        let d = dfs(&g, 0);
        assert_eq!(d[0], 0);
        assert_eq!(d.len(), 4);
        // DFS is lowest-index-first: 0,1,3,2.
        assert_eq!(d, vec![0, 1, 3, 2]);
    }

    #[test]
    fn shortest_path_finds_a_length_two_route() {
        let g = diamond();
        let p = shortest_path(&g, 0, 3).unwrap();
        assert_eq!(p.first(), Some(&0));
        assert_eq!(p.last(), Some(&3));
        assert_eq!(p.len(), 3, "two hops: 0 → x → 3");
        assert!(shortest_path(&g, 3, 0).is_none(), "directed: no route back");
        assert_eq!(shortest_path(&g, 2, 2), Some(vec![2]), "trivial self path");
    }

    #[test]
    fn dijkstra_prefers_the_cheaper_route() {
        // 0→1 (w=1) →3 (w=1) = 2; 0→2 (w=5) →3 (w=1) = 6. Cheapest is via 1.
        let g = Adjacency::from_weighted(4, &[(0, 1, 1.0), (1, 3, 1.0), (0, 2, 5.0), (2, 3, 1.0)]);
        let (path, cost) = dijkstra(&g, 0, 3).unwrap();
        assert_eq!(path, vec![0, 1, 3]);
        assert!((cost - 2.0).abs() < 1e-6, "cheapest cost is 2 (got {cost})");
    }

    #[test]
    fn all_simple_paths_enumerates_both_routes() {
        let g = diamond();
        let paths = all_simple_paths(&g, 0, 3, 8);
        assert_eq!(paths.len(), 2, "the diamond has two simple paths");
        assert!(paths.contains(&vec![0, 1, 3]));
        assert!(paths.contains(&vec![0, 2, 3]));
        // The length guard prunes.
        assert!(all_simple_paths(&g, 0, 3, 2).is_empty(), "max_len=2 admits no 3-node path");
    }
}