xgraph 3.0.0

//! A read-optimised projection of a graph.
//!
//! The graph types here are built for mutation: slab storage with per-node adjacency
//! vectors, so that adding and removing edges stays cheap and identifiers stay stable.
//! That layout scatters a node's neighbours across the heap, and a traversal pays a cache
//! miss for each one.
//!
//! [`CsrView`] is the same graph in compressed sparse row form — every neighbour in one
//! contiguous array, indexed by an offset table. Building it costs one pass; after that a
//! traversal walks memory in order. It is immutable by construction, which is the point:
//! the write model and the read model want different layouts, and trying to serve both
//! from one is what makes graph storage a compromise.
//!
//! Every algorithm in this crate is written against [`GraphView`], so all of them run over
//! a `CsrView` unchanged.
//!
//! # What it is actually worth
//!
//! Measured on a 200×200 grid (40,000 nodes, ~80,000 edges), against the mutable graph:
//!
//! | | mutable | frozen |
//! |---|---|---|
//! | Dijkstra | 9.2 ms | 7.4 ms |
//! | reachability (BFS) | 2.35 ms | 2.36 ms |
//! | connected components | 3.6 ms | 3.4 ms |
//! | building the projection | — | 1.35 ms |
//!
//! So: about a fifth off Dijkstra, and nothing measurable off a plain breadth-first sweep.
//! The mutable graph already stores each node's neighbours in one vector, so the layout was
//! never as scattered as compressed-row storage usually improves on; what remains is the
//! indirection through the slab, which matters more when a traversal revisits nodes.
//!
//! Freezing a *filtered* view does not help either unless the filter is expensive — a
//! cheap predicate costs less than the extra copy.
//!
//! Reach for this when the same graph is queried repeatedly and shortest paths dominate.
//! Do not reach for it to speed up a single traversal: the build costs more than it saves.

use crate::core::view::{EdgeId, GraphView, Link, NodeId};

/// A frozen, read-optimised copy of a graph.
///
/// # Examples
/// ```rust
/// # #[cfg(feature = "graph")] {
/// use xgraph::core::{CsrView, GraphView, ShortestPath};
/// use xgraph::graph::Graph;
///
/// let mut graph = Graph::<u32, &str, &str>::new(false);
/// let a = graph.add_node("A");
/// let b = graph.add_node("B");
/// graph.add_edge(a, b, 5, "rail").unwrap();
///
/// let frozen = CsrView::from_view(&graph);
/// assert_eq!(frozen.node_count(), 2);
/// // Algorithms are written against the abstraction, so they apply unchanged.
/// assert_eq!(frozen.dijkstra(a).unwrap()[&b], 5);
/// # }
/// ```
#[derive(Debug, Clone)]
pub struct CsrView<W> {
    /// The node identifiers, in ascending order. Position in this vector is a node's row.
    nodes: Vec<NodeId>,
    /// Where each row's links begin in `links`, with a final entry for the end.
    ///
    /// One extra element means a row's extent is `offsets[row]..offsets[row + 1]` with no
    /// special case for the last row.
    offsets: Vec<usize>,
    /// Every link of every node, laid out row by row.
    links: Vec<Link<W>>,
    /// The endpoints of each edge, indexed the same way the source graph indexed them.
    edge_endpoints: Vec<Option<(NodeId, NodeId)>>,
    /// Which row each storage slot occupies, indexed by `NodeId::index`.
    ///
    /// A direct lookup, not a search. Binary-searching the sorted identifier list would
    /// add a `log |V|` factor to every step of every traversal, which costs more than the
    /// contiguous layout saves — measured, not assumed.
    row_of_slot: Vec<Option<usize>>,
    directed: bool,
    edge_count: usize,
}

impl<W: Copy> CsrView<W> {
    /// Builds the projection from any view, in one pass.
    ///
    /// The identifiers are the source graph's own, so a route found here names nodes the
    /// original graph still recognises.
    pub fn from_view<G>(source: &G) -> Self
    where
        G: GraphView<Weight = W> + ?Sized,
    {
        let nodes: Vec<NodeId> = source.node_ids().collect();
        let highest_slot = nodes.iter().map(|id| id.index()).max();
        let mut row_of_slot: Vec<Option<usize>> =
            vec![None; highest_slot.map_or(0, |slot| slot + 1)];
        for (row, id) in nodes.iter().enumerate() {
            row_of_slot[id.index()] = Some(row);
        }
        // Identity is the slot *and* the generation, so a stale identifier naming a live
        // slot must not resolve. The row's own identifier settles it.
        let admits = |candidate: NodeId| {
            row_of_slot
                .get(candidate.index())
                .copied()
                .flatten()
                .is_some_and(|row| nodes[row] == candidate)
        };

        let mut offsets = Vec::with_capacity(nodes.len() + 1);
        let mut links = Vec::new();
        let mut highest_edge = 0usize;

        for &node in &nodes {
            offsets.push(links.len());
            for link in source.links(node) {
                highest_edge = highest_edge.max(link.edge.index());
                // A link to a node the view does not admit would dangle, so it is dropped
                // here rather than left to surprise an algorithm later.
                if admits(link.target) {
                    links.push(link);
                }
            }
        }
        offsets.push(links.len());

        let mut edge_endpoints = vec![
            None;
            if links.is_empty() {
                0
            } else {
                highest_edge + 1
            }
        ];
        for link in &links {
            if let Some(slot) = edge_endpoints.get_mut(link.edge.index()) {
                *slot = source.edge_endpoints(link.edge);
            }
        }

        Self {
            nodes,
            offsets,
            links,
            edge_endpoints,
            row_of_slot,
            directed: source.is_directed(),
            edge_count: source.edge_count(),
        }
    }

    /// The row a node occupies, if it is present.
    fn row_of(&self, node: NodeId) -> Option<usize> {
        let row = self.row_of_slot.get(node.index()).copied().flatten()?;
        // Guards against a stale identifier whose slot has been refilled.
        (self.nodes[row] == node).then_some(row)
    }
}

/// Iterator over the node identifiers of a [`CsrView`].
pub struct CsrNodeIds<'a> {
    inner: std::slice::Iter<'a, NodeId>,
}

impl<'a> Iterator for CsrNodeIds<'a> {
    type Item = NodeId;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().copied()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

/// Iterator over one node's links in a [`CsrView`].
///
/// A contiguous slice, which is the whole point of the layout.
pub struct CsrLinks<'a, W> {
    inner: std::slice::Iter<'a, Link<W>>,
}

impl<'a, W: Copy> Iterator for CsrLinks<'a, W> {
    type Item = Link<W>;

    fn next(&mut self) -> Option<Self::Item> {
        self.inner.next().copied()
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.inner.size_hint()
    }
}

impl<W: Copy> GraphView for CsrView<W> {
    type Weight = W;
    type NodeIds<'a>
        = CsrNodeIds<'a>
    where
        Self: 'a;
    type Links<'a>
        = CsrLinks<'a, W>
    where
        Self: 'a;

    fn is_directed(&self) -> bool {
        self.directed
    }

    fn node_count(&self) -> usize {
        self.nodes.len()
    }

    fn edge_count(&self) -> usize {
        self.edge_count
    }

    fn contains_node(&self, node: NodeId) -> bool {
        self.row_of(node).is_some()
    }

    fn node_ids(&self) -> Self::NodeIds<'_> {
        CsrNodeIds {
            inner: self.nodes.iter(),
        }
    }

    fn links(&self, node: NodeId) -> Self::Links<'_> {
        let range = match self.row_of(node) {
            Some(row) => self.offsets[row]..self.offsets[row + 1],
            None => 0..0,
        };
        CsrLinks {
            inner: self.links[range].iter(),
        }
    }

    fn edge_endpoints(&self, edge: EdgeId) -> Option<(NodeId, NodeId)> {
        self.edge_endpoints.get(edge.index()).copied().flatten()
    }

    fn degree(&self, node: NodeId) -> usize {
        // The offsets already record this, so counting the links would be wasteful.
        match self.row_of(node) {
            Some(row) => self.offsets[row + 1] - self.offsets[row],
            None => 0,
        }
    }
}

#[cfg(test)]
#[cfg(feature = "graph")]
mod tests {
    use super::*;
    use crate::core::{Bridges, Connectivity, EdgeFiltered, ShortestPath, Traversal};
    use crate::graph::Graph;

    fn sample() -> (Graph<u32, u32, &'static str>, Vec<NodeId>) {
        let mut graph = Graph::<u32, u32, &str>::new(false);
        let nodes: Vec<_> = (0..6).map(|i| graph.add_node(i)).collect();
        for &(a, b, w) in &[(0, 1, 1), (1, 2, 2), (2, 0, 3), (2, 3, 4), (3, 4, 5)] {
            graph.add_edge(nodes[a], nodes[b], w, "e").unwrap();
        }
        graph.add_node(99);
        (graph, nodes)
    }

    #[test]
    fn test_the_projection_describes_the_same_graph() {
        let (graph, nodes) = sample();
        let frozen = CsrView::from_view(&graph);

        assert_eq!(frozen.node_count(), graph.node_count());
        assert_eq!(frozen.edge_count(), graph.edge_count());
        assert_eq!(frozen.is_directed(), graph.is_directed());
        assert_eq!(frozen.node_id_vec(), graph.node_id_vec());

        for &node in &nodes {
            assert_eq!(frozen.degree(node), graph.degree(node));
            let mut from_csr: Vec<_> = frozen.links(node).map(|l| (l.target, l.edge)).collect();
            let mut from_graph: Vec<_> = graph.links(node).map(|l| (l.target, l.edge)).collect();
            from_csr.sort_unstable();
            from_graph.sort_unstable();
            assert_eq!(from_csr, from_graph);
        }
    }

    /// The projection exists so that the algorithms can run over it untouched.
    #[test]
    fn test_algorithms_agree_across_the_two_layouts() {
        let (graph, nodes) = sample();
        let frozen = CsrView::from_view(&graph);

        assert_eq!(
            frozen.dijkstra(nodes[0]).unwrap(),
            graph.dijkstra(nodes[0]).unwrap()
        );
        assert_eq!(frozen.bridges().unwrap(), graph.bridges().unwrap());
        assert_eq!(
            frozen.weakly_connected_components().unwrap(),
            graph.weakly_connected_components().unwrap()
        );
        assert_eq!(frozen.has_cycle().unwrap(), graph.has_cycle().unwrap());
        assert_eq!(
            frozen.reachable_from(nodes[0]).unwrap(),
            graph.reachable_from(nodes[0]).unwrap()
        );
    }

    #[test]
    fn test_an_unknown_identifier_has_no_links() {
        let (graph, _) = sample();
        let frozen = CsrView::from_view(&graph);

        let absent = NodeId::from_index(999);
        assert!(!frozen.contains_node(absent));
        assert_eq!(frozen.links(absent).count(), 0);
        assert_eq!(frozen.degree(absent), 0);
    }

    #[test]
    fn test_sparse_identifiers_are_preserved() {
        let mut graph = Graph::<u32, u32, ()>::new(false);
        let a = graph.add_node(0);
        let gap = graph.add_node(1);
        let b = graph.add_node(2);
        graph.remove_node(gap).unwrap();
        graph.add_edge(a, b, 7, ()).unwrap();

        let frozen = CsrView::from_view(&graph);
        assert_eq!(frozen.node_id_vec(), vec![a, b]);
        assert!(!frozen.contains_node(gap));
        assert_eq!(frozen.dijkstra(a).unwrap()[&b], 7);
    }

    /// Freezing a filtered view captures the filter, so the restriction costs nothing to
    /// re-apply on every later traversal.
    #[test]
    fn test_a_filtered_view_can_be_frozen() {
        let (graph, nodes) = sample();
        let cheap = EdgeFiltered::new(&graph, |edge| edge.index() < 2);
        let frozen = CsrView::from_view(&cheap);

        assert_eq!(frozen.node_count(), graph.node_count());
        assert_eq!(frozen.links(nodes[3]).count(), 0);
        assert_eq!(frozen.degree(nodes[1]), 2);
    }

    #[test]
    fn test_an_empty_graph_projects_cleanly() {
        let graph = Graph::<u32, u32, ()>::new(true);
        let frozen = CsrView::from_view(&graph);

        assert_eq!(frozen.node_count(), 0);
        assert_eq!(frozen.edge_count(), 0);
        assert!(frozen.node_id_vec().is_empty());
    }
}