xgraph 3.0.0

//! Graph search algorithms and operations
//!
//! This module provides functionality for performing various search operations on graphs,
//! including path finding, cycle detection, and node existence checks. It is designed to work
//! with both directed and undirected graphs, offering robust implementations of Depth-First
//! Search (DFS) and Breadth-First Search (BFS) algorithms.
//!
//! # Features
//! - Path existence checking using DFS
//! - Shortest path finding using BFS
//! - Cycle detection tailored for directed and undirected graphs
//! - Node existence verification
//!
//! # Examples
//!
//! Basic usage with a directed graph:
//! ```rust
//! use xgraph::graph::graph::Graph;
//! use xgraph::core::Traversal;
//!
//! let mut graph = Graph::<u32, &str, &str>::new(true);
//! let a = graph.add_node("A");
//! let b = graph.add_node("B");
//! graph.add_edge(a, b, 1, "link").unwrap();
//!
//! assert!(graph.has_path(a, b).unwrap());
//! assert_eq!(graph.bfs_path(a, b).unwrap(), Some(vec![a, b]));
//! ```

use crate::core::algo::traversal::TraversalError;
use crate::core::view::NodeId;
use crate::graph::graph::Graph;
use std::collections::HashSet;
use std::fmt::Debug;
use std::hash::Hash;

/// Error type for search operation failures.
///
/// Represents errors that may occur during graph search operations.
#[derive(Debug, thiserror::Error)]
pub enum SearchError {
    /// Indicates that a node referenced in the search does not exist in the graph.
    #[error("Invalid node reference: node ID {0} not found")]
    InvalidNode(NodeId),
}

impl From<TraversalError> for SearchError {
    fn from(error: TraversalError) -> Self {
        match error {
            TraversalError::InvalidNode(id) => SearchError::InvalidNode(id),
        }
    }
}

/// Trait for graph search operations.
///
/// Provides fundamental algorithms for graph traversal and analysis with error handling.
///
/// # Type Parameters
/// - `W`: Edge weight type, must be copyable, have a default value, and support partial equality.
/// - `N`: Node data type, must be clonable, equatable, hashable, and debuggable.
/// - `E`: Edge data type, must be clonable and debuggable.
///
/// # Examples
/// ```rust
/// use xgraph::graph::graph::Graph;
/// use xgraph::core::Traversal;
///
/// let mut graph = Graph::<u32, u32, ()>::new(true);
/// let a = graph.add_node(0);
/// let b = graph.add_node(1);
/// graph.add_edge(a, b, 1, ()).unwrap();
///
/// assert!(graph.has_path(a, b).unwrap());
/// assert_eq!(graph.bfs_path(a, b).unwrap(), Some(vec![a, b]));
/// ```
#[deprecated(
    since = "3.0.0",
    note = "superseded by `xgraph::core::Traversal`, which is implemented for every graph \
            view — including filtered ones — and carries no unused type parameters"
)]
pub trait Search<W, N, E>
where
    W: Copy + Default + PartialEq,
    N: Clone + Eq + Hash + Debug,
    E: Clone + Default + Debug,
{
    /// Checks if a path exists between two nodes using DFS.
    ///
    /// Traverses the graph depth-first to determine if there is a valid path from `start` to `target`.
    ///
    /// # Arguments
    /// - `start`: The ID of the starting node.
    /// - `target`: The ID of the target node.
    ///
    /// # Returns
    /// - `Ok(bool)`: `true` if a path exists, `false` otherwise.
    /// - `Err(SearchError)`: If either `start` or `target` is not a valid node.
    ///
    /// # Examples
    /// ```rust
    /// use xgraph::graph::graph::Graph;
    /// use xgraph::core::Traversal;
    ///
    /// let mut graph = Graph::<u32, u32, ()>::new(true);
    /// let a = graph.add_node(0);
    /// let b = graph.add_node(1);
    /// let c = graph.add_node(2);
    /// graph.add_edge(a, b, 1, ()).unwrap();
    /// graph.add_edge(b, c, 1, ()).unwrap();
    ///
    /// assert!(graph.has_path(a, c).unwrap());
    /// assert!(!graph.has_path(c, a).unwrap()); // Directed graph
    /// ```
    fn has_path(&self, start: NodeId, target: NodeId) -> Result<bool, SearchError>;

    /// Finds the shortest path between nodes using BFS.
    ///
    /// Uses breadth-first search to find the shortest unweighted path from `start` to `target`.
    ///
    /// # Arguments
    /// - `start`: The ID of the starting node.
    /// - `target`: The ID of the target node.
    ///
    /// # Returns
    /// - `Ok(Option<Vec<NodeId>>)`: A vector of node IDs representing the shortest path, or `None` if no path exists.
    /// - `Err(SearchError)`: If either `start` or `target` is not a valid node.
    ///
    /// # Examples
    /// ```rust
    /// use xgraph::graph::graph::Graph;
    /// use xgraph::core::Traversal;
    ///
    /// let mut graph = Graph::<u32, (), ()>::new(true);
    /// let nodes = (0..4).map(|i| graph.add_node(())).collect::<Vec<_>>();
    /// graph.add_edge(nodes[0], nodes[1], 1, ()).unwrap();
    /// graph.add_edge(nodes[1], nodes[2], 1, ()).unwrap();
    /// graph.add_edge(nodes[0], nodes[3], 1, ()).unwrap();
    ///
    /// assert_eq!(
    ///     graph.bfs_path(nodes[0], nodes[2]).unwrap(),
    ///     Some(vec![nodes[0], nodes[1], nodes[2]])
    /// );
    /// ```
    fn bfs_path(&self, start: NodeId, target: NodeId) -> Result<Option<Vec<NodeId>>, SearchError>;

    /// Performs a recursive DFS to check for a path between nodes.
    ///
    /// Internal helper method for path checking, not typically called directly by users.
    ///
    /// # Arguments
    /// - `current`: The current node ID in the recursion.
    /// - `target`: The target node ID to find.
    /// - `visited`: A mutable reference to a set tracking visited nodes.
    ///
    /// # Returns
    /// - `Ok(bool)`: `true` if a path to `target` is found, `false` otherwise.
    /// - `Err(SearchError)`: If `current` or `target` is not a valid node.
    #[deprecated(
        since = "3.0.0",
        note = "an implementation detail of `has_path`; use `has_path`, or \
                `xgraph::core::Traversal::explore_into` to drive the search yourself"
    )]
    fn dfs(
        &self,
        current: NodeId,
        target: NodeId,
        visited: &mut HashSet<NodeId>,
    ) -> Result<bool, SearchError>;

    /// Checks if a node exists in the graph.
    ///
    /// Verifies whether a node with the given ID is present in the graph.
    ///
    /// # Arguments
    /// - `node`: The ID of the node to check.
    ///
    /// # Returns
    /// - `Ok(bool)`: `true` if the node exists, `false` otherwise.
    /// - `Err(SearchError)`: Never returned in this implementation, but included for consistency.
    ///
    /// # Examples
    /// ```rust
    /// use xgraph::core::NodeId;
    /// use xgraph::graph::graph::Graph;
    ///
    /// let mut graph = Graph::<i32, (), ()>::new(false);
    /// let n0 = graph.add_node(());
    /// assert!(graph.contains_node(n0));
    /// assert!(!graph.contains_node(NodeId::from_index(999)));
    /// ```
    fn has_node(&self, node: NodeId) -> Result<bool, SearchError>;

    /// Detects whether the graph contains any cycles.
    ///
    /// Uses DFS-based algorithms tailored to the graph's directionality:
    /// - Directed graphs: Uses a recursion stack to detect back edges.
    /// - Undirected graphs: Uses parent tracking to avoid false positives from bidirectional edges.
    ///
    /// # Returns
    /// - `Ok(bool)`: `true` if a cycle is detected, `false` otherwise.
    /// - `Err(SearchError)`: If an invalid node is encountered during traversal.
    ///
    /// # Examples
    /// ```rust
    /// use xgraph::graph::graph::Graph;
    /// use xgraph::core::Traversal;
    ///
    /// let mut graph = Graph::<u32, (), ()>::new(true);
    /// let nodes = (0..3).map(|i| graph.add_node(())).collect::<Vec<_>>();
    /// graph.add_edge(nodes[0], nodes[1], 1, ()).unwrap();
    /// graph.add_edge(nodes[1], nodes[2], 1, ()).unwrap();
    /// graph.add_edge(nodes[2], nodes[0], 1, ()).unwrap();
    /// assert!(graph.has_cycle().unwrap());
    /// ```
    fn has_cycle(&self) -> Result<bool, SearchError>;

    /// Helper method for cycle detection in directed graphs.
    ///
    /// Uses DFS with a recursion stack to detect cycles in directed graphs.
    ///
    /// # Arguments
    /// - `node`: The current node ID.
    /// - `visited`: A mutable reference to a set of visited nodes.
    /// - `recursion_stack`: A mutable reference to a set tracking the current recursion path.
    ///
    /// # Returns
    /// - `Ok(bool)`: `true` if a cycle is detected, `false` otherwise.
    /// - `Err(SearchError)`: If `node` is not a valid node.
    fn has_cycle_directed(
        &self,
        node: NodeId,
        visited: &mut HashSet<NodeId>,
        recursion_stack: &mut HashSet<NodeId>,
    ) -> Result<bool, SearchError>;

    /// Helper method for cycle detection in undirected graphs.
    ///
    /// Uses DFS with parent tracking to detect cycles in undirected graphs.
    ///
    /// # Arguments
    /// - `node`: The current node ID.
    /// - `parent`: The ID of the parent node in the DFS tree, or `None` if root.
    /// - `visited`: A mutable reference to a set of visited nodes.
    ///
    /// # Returns
    /// - `Ok(bool)`: `true` if a cycle is detected, `false` otherwise.
    /// - `Err(SearchError)`: If `node` is not a valid node.
    fn has_cycle_undirected(
        &self,
        node: NodeId,
        parent: Option<NodeId>,
        visited: &mut HashSet<NodeId>,
    ) -> Result<bool, SearchError>;
}

#[allow(deprecated)]
impl<W, N, E> Search<W, N, E> for Graph<W, N, E>
where
    W: Copy + Default + PartialEq,
    N: Clone + Eq + Hash + Debug,
    E: Clone + Default + Debug,
{
    fn has_path(&self, start: NodeId, target: NodeId) -> Result<bool, SearchError> {
        crate::core::Traversal::has_path(self, start, target).map_err(SearchError::from)
    }

    fn bfs_path(&self, start: NodeId, target: NodeId) -> Result<Option<Vec<NodeId>>, SearchError> {
        crate::core::Traversal::bfs_path(self, start, target).map_err(SearchError::from)
    }

    fn dfs(
        &self,
        current: NodeId,
        target: NodeId,
        visited: &mut HashSet<NodeId>,
    ) -> Result<bool, SearchError> {
        if !crate::core::GraphView::contains_node(self, current) {
            return Err(SearchError::InvalidNode(current));
        }
        if !crate::core::GraphView::contains_node(self, target) {
            return Err(SearchError::InvalidNode(target));
        }
        crate::core::Traversal::explore_into(self, current, Some(target), visited)
            .map_err(SearchError::from)
    }

    fn has_node(&self, node: NodeId) -> Result<bool, SearchError> {
        Ok(crate::core::GraphView::contains_node(self, node))
    }

    fn has_cycle(&self) -> Result<bool, SearchError> {
        crate::core::Traversal::has_cycle(self).map_err(SearchError::from)
    }

    fn has_cycle_directed(
        &self,
        node: NodeId,
        visited: &mut HashSet<NodeId>,
        _recursion_stack: &mut HashSet<NodeId>,
    ) -> Result<bool, SearchError> {
        crate::core::Traversal::has_cycle_from(self, node, visited).map_err(SearchError::from)
    }

    fn has_cycle_undirected(
        &self,
        node: NodeId,
        _parent: Option<NodeId>,
        visited: &mut HashSet<NodeId>,
    ) -> Result<bool, SearchError> {
        crate::core::Traversal::has_cycle_from(self, node, visited).map_err(SearchError::from)
    }
}

#[cfg(test)]
#[allow(deprecated)]
mod tests {
    use super::*;
    use crate::core::view::NodeId;

    #[test]
    fn test_has_path() {
        let mut graph = Graph::<u32, (), ()>::new(false);
        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        graph.add_edge(n0, n1, 1, ()).unwrap();

        assert!(graph.has_path(n0, n1).unwrap());
        assert!(graph.has_path(n1, n0).unwrap());
        assert!(matches!(
            graph.has_path(NodeId::from_index(999), n0),
            Err(SearchError::InvalidNode(id)) if id == NodeId::from_index(999)
        ));
    }

    #[test]
    fn test_bfs_path() {
        let mut graph = Graph::<u32, (), ()>::new(true);
        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        let n2 = graph.add_node(());
        graph.add_edge(n0, n1, 1, ()).unwrap();
        graph.add_edge(n1, n2, 1, ()).unwrap();

        assert_eq!(graph.bfs_path(n0, n2).unwrap(), Some(vec![n0, n1, n2]));
        assert!(matches!(
            graph.bfs_path(NodeId::from_index(999), n0),
            Err(SearchError::InvalidNode(id)) if id == NodeId::from_index(999)
        ));
    }

    #[test]
    fn test_dfs() {
        let mut graph = Graph::<u32, (), ()>::new(false);
        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        let n2 = graph.add_node(());
        graph.add_edge(n0, n1, 1, ()).unwrap();
        graph.add_edge(n1, n2, 1, ()).unwrap();

        let mut visited = HashSet::new();
        assert!(graph.dfs(n0, n2, &mut visited).unwrap());
        assert!(matches!(
            graph.dfs(NodeId::from_index(999), n0, &mut visited),
            Err(SearchError::InvalidNode(id)) if id == NodeId::from_index(999)
        ));
    }

    #[test]
    fn test_invalid_nodes() {
        let graph = Graph::<u32, (), ()>::new(false);
        assert!(!graph.has_node(NodeId::from_index(0)).unwrap());
        assert!(matches!(
            graph.has_path(NodeId::from_index(0), NodeId::from_index(1)),
            Err(SearchError::InvalidNode(_))
        ));
        assert!(matches!(
            graph.bfs_path(NodeId::from_index(0), NodeId::from_index(1)),
            Err(SearchError::InvalidNode(_))
        ));
    }

    #[test]
    fn test_cycle_detection_directed() {
        let mut graph = Graph::<u32, (), ()>::new(true);
        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        let n2 = graph.add_node(());

        graph.add_edge(n0, n1, 1, ()).unwrap();
        graph.add_edge(n1, n2, 1, ()).unwrap();
        graph.add_edge(n2, n0, 1, ()).unwrap();

        assert!(graph.has_cycle().unwrap());
    }

    #[test]
    fn test_cycle_detection_undirected() {
        let mut graph = Graph::<u32, (), ()>::new(false);
        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        let n2 = graph.add_node(());

        graph.add_edge(n0, n1, 1, ()).unwrap();
        graph.add_edge(n1, n2, 1, ()).unwrap();
        graph.add_edge(n2, n0, 1, ()).unwrap();

        assert!(graph.has_cycle().unwrap());
    }

    #[test]
    fn test_no_cycle_directed() {
        let mut graph = Graph::<u32, (), ()>::new(true);
        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        let n2 = graph.add_node(());

        graph.add_edge(n0, n1, 1, ()).unwrap();
        graph.add_edge(n1, n2, 1, ()).unwrap();

        assert!(!graph.has_cycle().unwrap());
    }

    #[test]
    fn test_no_cycle_undirected() {
        let mut graph = Graph::<u32, (), ()>::new(false);
        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        let n2 = graph.add_node(());

        graph.add_edge(n0, n1, 1, ()).unwrap();
        graph.add_edge(n1, n2, 1, ()).unwrap();

        assert!(!graph.has_cycle().unwrap());
    }

    #[test]
    fn test_parallel_edges_form_an_undirected_cycle() {
        // Two distinct edges joining the same pair are a cycle of length two. Excluding the
        // parent by node ID would hide it; excluding only the arrival edge does not.
        let mut graph = Graph::<u32, (), ()>::new(false);
        let a = graph.add_node(());
        let b = graph.add_node(());
        graph.add_edge(a, b, 1, ()).unwrap();
        graph.add_edge(a, b, 1, ()).unwrap();

        assert!(graph.has_cycle().unwrap());
    }

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

        assert!(!graph.has_cycle().unwrap());
    }

    #[test]
    fn test_deep_chain_does_not_overflow_the_stack() {
        let mut graph = Graph::<u32, usize, ()>::new(true);
        let nodes: Vec<_> = (0..200_000).map(|i| graph.add_node(i)).collect();
        for pair in nodes.windows(2) {
            graph.add_edge(pair[0], pair[1], 1, ()).unwrap();
        }

        let first = *nodes.first().unwrap();
        let last = *nodes.last().unwrap();
        assert!(graph.has_path(first, last).unwrap());
        assert!(!graph.has_cycle().unwrap());
    }
}