xgraph 3.0.0

//! Graph traversal, written once against [`GraphView`].
//!
//! Every algorithm here is iterative. The recursive versions these replace aborted the
//! process with a stack overflow on graphs a few hundred thousand nodes deep, which is well
//! within the range a graph library is expected to handle.
//!
//! Traversals that must ignore the edge they arrived on exclude *that specific edge* rather
//! than every edge back to the parent node. On a multigraph the difference is the
//! difference between a right and a wrong answer: a pair of parallel edges is a cycle, and
//! neither of them is a bridge.

use crate::core::view::{EdgeId, GraphView, NodeId};
use std::collections::{HashMap, HashSet, VecDeque};

/// Error type for traversal failures.
#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
pub enum TraversalError {
    /// A node referenced by the caller does not exist in the graph.
    #[error("Invalid node reference: node ID {0} not found")]
    InvalidNode(NodeId),
}

/// Traversal algorithms available on every [`GraphView`].
///
/// The blanket implementation means a new view — a filtered one, a future compressed
/// storage — gets the whole set for free, and an algorithm added here becomes available to
/// every graph type at once. That is the property the duplicated `graph`/`hgraph`
/// algorithm modules lacked.
pub trait Traversal: GraphView {
    /// Explores depth-first from `start`, recording what it sees in `visited`.
    ///
    /// When `stop_at` is given the search returns as soon as that node is reached, leaving
    /// `visited` holding only the part of the graph explored up to that point. This is the
    /// single primitive behind both [`reachable_from`](Traversal::reachable_from) and
    /// [`has_path`](Traversal::has_path).
    fn explore_into(
        &self,
        start: NodeId,
        stop_at: Option<NodeId>,
        visited: &mut HashSet<NodeId>,
    ) -> Result<bool, TraversalError> {
        if !self.contains_node(start) {
            return Err(TraversalError::InvalidNode(start));
        }

        visited.insert(start);
        if stop_at == Some(start) {
            return Ok(true);
        }

        let mut stack = vec![start];
        while let Some(node) = stack.pop() {
            for link in self.links(node) {
                if stop_at == Some(link.target) {
                    visited.insert(link.target);
                    return Ok(true);
                }
                if visited.insert(link.target) {
                    stack.push(link.target);
                }
            }
        }
        Ok(false)
    }

    /// Returns every node reachable from `start`, including `start` itself.
    fn reachable_from(&self, start: NodeId) -> Result<HashSet<NodeId>, TraversalError> {
        let mut visited = HashSet::new();
        self.explore_into(start, None, &mut visited)?;
        Ok(visited)
    }

    /// Checks whether any path leads from `start` to `target`.
    ///
    /// Follows edge direction, so on a directed graph the answer is not symmetric.
    fn has_path(&self, start: NodeId, target: NodeId) -> Result<bool, TraversalError> {
        // Validated in argument order, so a call with two bad IDs names the first one.
        if !self.contains_node(start) {
            return Err(TraversalError::InvalidNode(start));
        }
        if !self.contains_node(target) {
            return Err(TraversalError::InvalidNode(target));
        }
        self.explore_into(start, Some(target), &mut HashSet::new())
    }

    /// Finds a path from `start` to `target` with the fewest edges.
    ///
    /// Weights are ignored; for weighted shortest paths use Dijkstra.
    ///
    /// # Returns
    /// - `Ok(Some(path))` beginning at `start` and ending at `target`.
    /// - `Ok(None)` if `target` is unreachable.
    fn bfs_path(
        &self,
        start: NodeId,
        target: NodeId,
    ) -> Result<Option<Vec<NodeId>>, TraversalError> {
        if !self.contains_node(start) {
            return Err(TraversalError::InvalidNode(start));
        }
        if !self.contains_node(target) {
            return Err(TraversalError::InvalidNode(target));
        }
        if start == target {
            return Ok(Some(vec![start]));
        }

        let mut predecessors: HashMap<NodeId, NodeId> = HashMap::new();
        let mut visited = HashSet::new();
        visited.insert(start);
        let mut queue = VecDeque::from([start]);

        while let Some(node) = queue.pop_front() {
            for link in self.links(node) {
                if !visited.insert(link.target) {
                    continue;
                }
                predecessors.insert(link.target, node);
                if link.target == target {
                    let mut path = vec![target];
                    let mut current = target;
                    while current != start {
                        current = predecessors[&current];
                        path.push(current);
                    }
                    path.reverse();
                    return Ok(Some(path));
                }
                queue.push_back(link.target);
            }
        }
        Ok(None)
    }

    /// Visits every node reachable from `start` in depth-first pre-order.
    ///
    /// Nodes already present in `visited` are skipped, so repeated calls cover a
    /// disconnected graph one component at a time.
    fn dfs_preorder_into(
        &self,
        start: NodeId,
        visited: &mut HashSet<NodeId>,
        order: &mut Vec<NodeId>,
    ) -> Result<(), TraversalError> {
        if !self.contains_node(start) {
            return Err(TraversalError::InvalidNode(start));
        }
        if !visited.insert(start) {
            return Ok(());
        }

        let mut stack = vec![start];
        while let Some(node) = stack.pop() {
            order.push(node);
            for link in self.links(node) {
                if visited.insert(link.target) {
                    stack.push(link.target);
                }
            }
        }
        Ok(())
    }

    /// Visits every node reachable from `start` in depth-first post-order.
    ///
    /// A node is appended once its whole subtree is finished, which is the order Kosaraju's
    /// algorithm needs.
    fn dfs_postorder_into(
        &self,
        start: NodeId,
        visited: &mut HashSet<NodeId>,
        order: &mut Vec<NodeId>,
    ) -> Result<(), TraversalError> {
        if !self.contains_node(start) {
            return Err(TraversalError::InvalidNode(start));
        }
        if !visited.insert(start) {
            return Ok(());
        }

        // Each frame holds the node's link iterator itself. Re-deriving the position with
        // `nth` instead would make the walk quadratic in a node's degree.
        let mut stack: Vec<(NodeId, Self::Links<'_>)> = vec![(start, self.links(start))];
        while let Some(frame) = stack.last_mut() {
            let node = frame.0;
            let next = frame.1.next();

            match next {
                Some(link) => {
                    if visited.insert(link.target) {
                        stack.push((link.target, self.links(link.target)));
                    }
                }
                None => {
                    // The subtree is finished, so the node takes its place in post-order.
                    order.push(node);
                    stack.pop();
                }
            }
        }
        Ok(())
    }

    /// Detects whether the graph contains a cycle.
    ///
    /// Directed graphs are checked for a back edge into the active search path; undirected
    /// graphs, for any edge to an already-visited node other than the one just traversed.
    /// A self-loop counts as a cycle, and so does a pair of parallel edges in an undirected
    /// graph, because either one can be removed and still leave the two nodes connected.
    fn has_cycle(&self) -> Result<bool, TraversalError> {
        let mut visited = HashSet::new();
        for root in self.node_ids() {
            if visited.contains(&root) {
                continue;
            }
            if self.has_cycle_from(root, &mut visited)? {
                return Ok(true);
            }
        }
        Ok(false)
    }

    /// Detects a cycle in the component reachable from `root`.
    ///
    /// Nodes already in `visited` are treated as explored, so repeated calls sweep a
    /// disconnected graph one component at a time without re-walking anything.
    fn has_cycle_from(
        &self,
        root: NodeId,
        visited: &mut HashSet<NodeId>,
    ) -> Result<bool, TraversalError> {
        if !self.contains_node(root) {
            return Err(TraversalError::InvalidNode(root));
        }
        if !visited.insert(root) {
            return Ok(false);
        }

        if self.is_directed() {
            let mut on_path = HashSet::new();
            let mut stack: Vec<(NodeId, Self::Links<'_>)> = vec![(root, self.links(root))];
            on_path.insert(root);

            while let Some(frame) = stack.last_mut() {
                let node = frame.0;
                let next = frame.1.next();

                match next {
                    Some(link) => {
                        // A link back into the active path closes a directed cycle.
                        if on_path.contains(&link.target) {
                            return Ok(true);
                        }
                        if visited.insert(link.target) {
                            on_path.insert(link.target);
                            stack.push((link.target, self.links(link.target)));
                        }
                    }
                    None => {
                        on_path.remove(&node);
                        stack.pop();
                    }
                }
            }
        } else {
            let mut stack: Vec<(Self::Links<'_>, Option<EdgeId>)> = vec![(self.links(root), None)];

            while let Some(frame) = stack.last_mut() {
                let arrival_edge = frame.1;
                let next = frame.0.next();

                match next {
                    Some(link) => {
                        // Excluding the arrival edge, not the parent node: two parallel
                        // edges between the same pair really are a cycle.
                        if Some(link.edge) == arrival_edge {
                            continue;
                        }
                        if !visited.insert(link.target) {
                            return Ok(true);
                        }
                        stack.push((self.links(link.target), Some(link.edge)));
                    }
                    None => {
                        stack.pop();
                    }
                }
            }
        }
        Ok(false)
    }
}

impl<G: GraphView + ?Sized> Traversal for G {}

#[cfg(test)]
#[cfg(feature = "graph")]
mod tests {
    use super::*;
    use crate::core::EdgeFiltered;
    use crate::graph::Graph;

    fn path_graph(directed: bool, length: usize) -> (Graph<u32, usize, ()>, Vec<NodeId>) {
        let mut graph = Graph::<u32, usize, ()>::new(directed);
        let nodes: Vec<_> = (0..length).map(|i| graph.add_node(i)).collect();
        for pair in nodes.windows(2) {
            graph.add_edge(pair[0], pair[1], 1, ()).unwrap();
        }
        (graph, nodes)
    }

    #[test]
    fn test_has_path_follows_direction() {
        let (graph, nodes) = path_graph(true, 3);
        assert!(graph.has_path(nodes[0], nodes[2]).unwrap());
        assert!(!graph.has_path(nodes[2], nodes[0]).unwrap());
        assert!(graph.has_path(nodes[1], nodes[1]).unwrap());
        assert_eq!(
            graph.has_path(nodes[0], NodeId::from_index(999)),
            Err(TraversalError::InvalidNode(NodeId::from_index(999)))
        );
    }

    #[test]
    fn test_bfs_path_takes_the_fewest_edges() {
        let mut graph = Graph::<u32, u32, ()>::new(false);
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let d = graph.add_node(3);
        graph.add_edge(a, b, 1, ()).unwrap();
        graph.add_edge(b, d, 1, ()).unwrap();
        graph.add_edge(a, c, 1, ()).unwrap();
        graph.add_edge(c, d, 1, ()).unwrap();

        let path = graph.bfs_path(a, d).unwrap().unwrap();
        assert_eq!(path.len(), 3);
        assert_eq!((path[0], path[2]), (a, d));
        assert_eq!(graph.bfs_path(a, a).unwrap(), Some(vec![a]));
    }

    #[test]
    fn test_postorder_finishes_children_first() {
        let (graph, nodes) = path_graph(true, 4);
        let mut visited = HashSet::new();
        let mut order = Vec::new();
        graph
            .dfs_postorder_into(nodes[0], &mut visited, &mut order)
            .unwrap();

        let mut expected = nodes.clone();
        expected.reverse();
        assert_eq!(order, expected);
    }

    #[test]
    fn test_cycle_detection_distinguishes_directions() {
        let mut directed = Graph::<u32, u32, ()>::new(true);
        let a = directed.add_node(0);
        let b = directed.add_node(1);
        directed.add_edge(a, b, 1, ()).unwrap();
        assert!(!directed.has_cycle().unwrap());
        directed.add_edge(b, a, 1, ()).unwrap();
        assert!(directed.has_cycle().unwrap());

        let mut undirected = Graph::<u32, u32, ()>::new(false);
        let a = undirected.add_node(0);
        let b = undirected.add_node(1);
        undirected.add_edge(a, b, 1, ()).unwrap();
        assert!(!undirected.has_cycle().unwrap());
        // A second, distinct edge between the same pair closes a cycle of length two.
        undirected.add_edge(a, b, 1, ()).unwrap();
        assert!(undirected.has_cycle().unwrap());
    }

    /// The whole point of the filtered view: one traversal, restricted on the fly, with no
    /// second copy of the algorithm.
    #[test]
    fn test_traversal_over_a_filtered_view() {
        let mut graph = Graph::<u32, u32, &str>::new(false);
        let a = graph.add_node(0);
        let b = graph.add_node(1);
        let c = graph.add_node(2);
        let rail = graph.add_edge(a, b, 1, "rail").unwrap();
        graph.add_edge(b, c, 1, "road").unwrap();

        let rail_only = EdgeFiltered::new(&graph, |edge| edge == rail);
        assert!(graph.has_path(a, c).unwrap());
        assert!(!rail_only.has_path(a, c).unwrap());
        assert!(rail_only.has_path(a, b).unwrap());
    }

    #[test]
    fn test_deep_graph_does_not_overflow_the_stack() {
        let (graph, nodes) = path_graph(true, 200_000);
        let first = nodes[0];
        let last = *nodes.last().unwrap();

        assert!(graph.has_path(first, last).unwrap());
        assert_eq!(graph.bfs_path(first, last).unwrap().unwrap().len(), 200_000);
        assert!(!graph.has_cycle().unwrap());
        assert_eq!(graph.reachable_from(first).unwrap().len(), 200_000);

        let mut visited = HashSet::new();
        let mut order = Vec::new();
        graph
            .dfs_postorder_into(first, &mut visited, &mut order)
            .unwrap();
        assert_eq!(order.len(), 200_000);
    }
}