xgraph 3.0.0

//! Graph search algorithms and operations for heterogeneous multigraphs.
//!
//! This module provides a suite of graph traversal and analysis algorithms tailored for
//! heterogeneous multigraphs, supporting both directed and undirected graphs with multiple
//! edge types between nodes. Key functionalities include:
//! - Path existence checking using Depth-First Search (DFS).
//! - Shortest path finding using Breadth-First Search (BFS).
//! - Cycle detection for directed and undirected graphs.
//! - Node existence verification.
//!
//! All methods support filtering by edge types, enabling analysis of subgraphs defined by
//! specific edge categories. The module is available only when the `hgraph` feature is enabled
//! in your `Cargo.toml`:
//! ```toml
//! [dependencies.xgraph]
//! version = "x.y.z"
//! features = ["hgraph"]
//! ```

#[cfg(feature = "hgraph")]
use crate::core::view::NodeId;
#[cfg(feature = "hgraph")]
use crate::hgraph::h_graph::HeterogeneousGraph;
#[cfg(feature = "hgraph")]
use std::collections::HashSet;
#[cfg(feature = "hgraph")]
use std::fmt::Debug;
#[cfg(feature = "hgraph")]
use std::hash::Hash;

// Error handling additions

/// Error type for graph search operation failures.
///
/// Represents errors that may occur during graph traversal or analysis, such as referencing
/// invalid nodes.
#[cfg(feature = "hgraph")]
#[derive(Debug, thiserror::Error)]
pub enum SearchError {
    /// Indicates a node referenced in the graph does not exist.
    #[error("Invalid node reference: node ID {0} not found")]
    InvalidNodeReference(NodeId),
}

#[cfg(feature = "hgraph")]
impl From<crate::core::TraversalError> for SearchError {
    fn from(error: crate::core::TraversalError) -> Self {
        match error {
            crate::core::TraversalError::InvalidNode(id) => SearchError::InvalidNodeReference(id),
        }
    }
}

/// Result type alias for search operations.
///
/// Wraps the result of search methods, enabling error handling without panicking.
#[cfg(feature = "hgraph")]
pub type Result<T> = std::result::Result<T, SearchError>;

#[cfg(feature = "hgraph")]
/// Trait for graph search operations in heterogeneous multigraphs.
///
/// Defines methods for path finding, cycle detection, and node existence checks, with support
/// for edge type filtering. All methods that may fail due to invalid input return a `Result`
/// to handle errors gracefully.
#[deprecated(
    since = "3.0.0",
    note = "superseded by `xgraph::core::Traversal`; the `*_by_types` variants become \
            `graph.of_edge_kinds(&[..])` followed by the ordinary method"
)]
pub trait HeteroSearch<W, N, E>
where
    W: Copy + Default + PartialEq + Debug,
    N: Clone + Eq + Hash + Debug + crate::hgraph::h_node::NodeType,
    E: Clone + Default + Debug + crate::hgraph::h_edge::EdgeType,
{
    /// Checks if a path exists between two nodes using DFS.
    ///
    /// # Arguments
    /// * `start` - The starting node ID.
    /// * `target` - The target node ID.
    ///
    /// # Returns
    /// `true` if a path exists from `start` to `target`, `false` otherwise.
    fn has_path(&self, start: NodeId, target: NodeId) -> bool;

    /// Checks if a path exists between two nodes using DFS, considering only specific edge types.
    ///
    /// # Arguments
    /// * `start` - The starting node ID.
    /// * `target` - The target node ID.
    /// * `edge_types` - A slice of edge type strings to filter the search.
    ///
    /// # Returns
    /// `true` if a path exists from `start` to `target` using only the specified edge types,
    /// `false` otherwise.
    fn has_path_by_types(&self, start: NodeId, target: NodeId, edge_types: &[&str]) -> bool;

    /// Finds the shortest path between nodes using BFS.
    ///
    /// Returns the path as a vector of node IDs from `start` to `target`, or an error if either
    /// node does not exist.
    ///
    /// # Arguments
    /// * `start` - The starting node ID.
    /// * `target` - The target node ID.
    ///
    /// # Returns
    /// A `Result` containing `Some(Vec<NodeId>)` with the path if found, `None` if no path exists,
    /// or an error if nodes are invalid.
    fn bfs_path(&self, start: NodeId, target: NodeId) -> Result<Option<Vec<NodeId>>>;

    /// Finds the shortest path between nodes using BFS, considering only specific edge types.
    ///
    /// Returns the path as a vector of node IDs from `start` to `target`, or an error if either
    /// node does not exist.
    ///
    /// # Arguments
    /// * `start` - The starting node ID.
    /// * `target` - The target node ID.
    /// * `edge_types` - A slice of edge type strings to filter the search.
    ///
    /// # Returns
    /// A `Result` containing `Some(Vec<NodeId>)` with the path if found, `None` if no path exists,
    /// or an error if nodes are invalid.
    fn bfs_path_by_types(
        &self,
        start: NodeId,
        target: NodeId,
        edge_types: &[&str],
    ) -> Result<Option<Vec<NodeId>>>;

    /// Recursive DFS implementation for path checking.
    ///
    /// Internal helper method for `has_path`.
    ///
    /// # Arguments
    /// * `current` - The current node ID being explored.
    /// * `target` - The target node ID.
    /// * `visited` - A set of already visited node IDs.
    ///
    /// # Returns
    /// `true` if a path to `target` is found, `false` otherwise.
    fn dfs(&self, current: NodeId, target: NodeId, visited: &mut HashSet<NodeId>) -> bool;

    /// Recursive DFS implementation for path checking with edge type filtering.
    ///
    /// Internal helper method for `has_path_by_types`.
    ///
    /// # Arguments
    /// * `current` - The current node ID being explored.
    /// * `target` - The target node ID.
    /// * `visited` - A set of already visited node IDs.
    /// * `edge_types` - A slice of edge type strings to filter the search.
    ///
    /// # Returns
    /// `true` if a path to `target` is found using specified edge types, `false` otherwise.
    fn dfs_by_types(
        &self,
        current: NodeId,
        target: NodeId,
        visited: &mut HashSet<NodeId>,
        edge_types: &[&str],
    ) -> bool;

    /// Checks if a node exists in the graph.
    ///
    /// # Arguments
    /// * `node` - The node ID to check.
    ///
    /// # Returns
    /// `true` if the node exists, `false` otherwise.
    fn has_node(&self, node: NodeId) -> bool;

    /// Detects cycles in the graph.
    ///
    /// Uses DFS-based cycle detection, differing in approach based on whether the graph is
    /// directed or undirected.
    ///
    /// # Returns
    /// `true` if the graph contains at least one cycle, `false` otherwise.
    fn has_cycle(&self) -> bool;

    /// Detects cycles in the graph, considering only specific edge types.
    ///
    /// Uses DFS-based cycle detection with edge type filtering.
    ///
    /// # Arguments
    /// * `edge_types` - A slice of edge type strings to filter the search.
    ///
    /// # Returns
    /// `true` if a cycle exists using only the specified edge types, `false` otherwise.
    fn has_cycle_by_types(&self, edge_types: &[&str]) -> bool;

    /// Helper for directed cycle detection.
    ///
    /// Internal method using DFS with a recursion stack to detect cycles in directed graphs.
    ///
    /// # Arguments
    /// * `node` - The current node ID being explored.
    /// * `visited` - A set of already visited node IDs.
    /// * `recursion_stack` - A set tracking nodes in the current recursion path.
    ///
    /// # Returns
    /// `true` if a cycle is detected, `false` otherwise.
    fn has_cycle_directed(
        &self,
        node: NodeId,
        visited: &mut HashSet<NodeId>,
        recursion_stack: &mut HashSet<NodeId>,
    ) -> bool;

    /// Helper for directed cycle detection with edge type filtering.
    ///
    /// Internal method using DFS with a recursion stack and edge type filtering.
    ///
    /// # Arguments
    /// * `node` - The current node ID being explored.
    /// * `visited` - A set of already visited node IDs.
    /// * `recursion_stack` - A set tracking nodes in the current recursion path.
    /// * `edge_types` - A slice of edge type strings to filter the search.
    ///
    /// # Returns
    /// `true` if a cycle is detected using specified edge types, `false` otherwise.
    fn has_cycle_directed_by_types(
        &self,
        node: NodeId,
        visited: &mut HashSet<NodeId>,
        recursion_stack: &mut HashSet<NodeId>,
        edge_types: &[&str],
    ) -> bool;

    /// Helper for undirected cycle detection.
    ///
    /// Internal method using DFS with parent tracking to detect cycles in undirected graphs.
    ///
    /// # Arguments
    /// * `node` - The current node ID being explored.
    /// * `parent` - The parent node ID in the DFS tree, if any.
    /// * `visited` - A set of already visited node IDs.
    ///
    /// # Returns
    /// `true` if a cycle is detected, `false` otherwise.
    fn has_cycle_undirected(
        &self,
        node: NodeId,
        parent: Option<NodeId>,
        visited: &mut HashSet<NodeId>,
    ) -> bool;

    /// Helper for undirected cycle detection with edge type filtering.
    ///
    /// Internal method using DFS with parent tracking and edge type filtering.
    ///
    /// # Arguments
    /// * `node` - The current node ID being explored.
    /// * `parent` - The parent node ID in the DFS tree, if any.
    /// * `visited` - A set of already visited node IDs.
    /// * `edge_types` - A slice of edge type strings to filter the search.
    ///
    /// # Returns
    /// `true` if a cycle is detected using specified edge types, `false` otherwise.
    fn has_cycle_undirected_by_types(
        &self,
        node: NodeId,
        parent: Option<NodeId>,
        visited: &mut HashSet<NodeId>,
        edge_types: &[&str],
    ) -> bool;
}

#[cfg(feature = "hgraph")]
#[cfg(feature = "hgraph")]
#[allow(deprecated)]
impl<W, N, E> HeteroSearch<W, N, E> for HeterogeneousGraph<W, N, E>
where
    W: Copy + Default + PartialEq + Debug,
    N: Clone + Eq + Hash + Debug + crate::hgraph::h_node::NodeType,
    E: Clone + Default + Debug + crate::hgraph::h_edge::EdgeType,
{
    fn has_path(&self, start: NodeId, target: NodeId) -> bool {
        crate::core::Traversal::has_path(self, start, target).unwrap_or(false)
    }

    fn has_path_by_types(&self, start: NodeId, target: NodeId, edge_types: &[&str]) -> bool {
        crate::core::Traversal::has_path(&self.of_edge_kinds(edge_types), start, target)
            .unwrap_or(false)
    }

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

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

    fn dfs(&self, current: NodeId, target: NodeId, visited: &mut HashSet<NodeId>) -> bool {
        crate::core::Traversal::explore_into(self, current, Some(target), visited).unwrap_or(false)
    }

    fn dfs_by_types(
        &self,
        current: NodeId,
        target: NodeId,
        visited: &mut HashSet<NodeId>,
        edge_types: &[&str],
    ) -> bool {
        crate::core::Traversal::explore_into(
            &self.of_edge_kinds(edge_types),
            current,
            Some(target),
            visited,
        )
        .unwrap_or(false)
    }

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

    fn has_cycle(&self) -> bool {
        crate::core::Traversal::has_cycle(self).unwrap_or(false)
    }

    fn has_cycle_by_types(&self, edge_types: &[&str]) -> bool {
        crate::core::Traversal::has_cycle(&self.of_edge_kinds(edge_types)).unwrap_or(false)
    }

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

    fn has_cycle_directed_by_types(
        &self,
        node: NodeId,
        visited: &mut HashSet<NodeId>,
        _recursion_stack: &mut HashSet<NodeId>,
        edge_types: &[&str],
    ) -> bool {
        crate::core::Traversal::has_cycle_from(&self.of_edge_kinds(edge_types), node, visited)
            .unwrap_or(false)
    }

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

    fn has_cycle_undirected_by_types(
        &self,
        node: NodeId,
        _parent: Option<NodeId>,
        visited: &mut HashSet<NodeId>,
        edge_types: &[&str],
    ) -> bool {
        crate::core::Traversal::has_cycle_from(&self.of_edge_kinds(edge_types), node, visited)
            .unwrap_or(false)
    }
}

#[cfg(test)]
#[cfg(feature = "hgraph")]
#[allow(deprecated)]
mod tests {
    use super::*;
    use crate::core::view::NodeId;
    use crate::hgraph::h_edge::EdgeType;
    use crate::hgraph::h_node::NodeType;

    #[derive(Clone, Eq, PartialEq, Hash, Debug)]
    struct TestNode(String);
    impl NodeType for TestNode {
        fn as_string(&self) -> String {
            self.0.clone()
        }
    }

    #[derive(Clone, Debug, Default)]
    struct TestEdge(String);
    impl EdgeType for TestEdge {
        fn as_string(&self) -> String {
            self.0.clone()
        }
    }

    #[test]
    fn test_has_path() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(false);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();

        assert!(graph.has_path(n0, n1));
        assert!(graph.has_path(n1, n0));
    }

    #[test]
    fn test_has_path_by_types() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(false);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));
        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("bridge".to_string()))
            .unwrap();

        assert!(graph.has_path_by_types(n0, n1, &["road"]));
        assert!(!graph.has_path_by_types(n0, n2, &["road"]));
        assert!(graph.has_path_by_types(n0, n2, &["road", "bridge"]));
    }

    #[test]
    fn test_bfs_path() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(true);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));
        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("bridge".to_string()))
            .unwrap();

        assert_eq!(graph.bfs_path(n0, n2).unwrap(), Some(vec![n0, n1, n2]));
    }

    #[test]
    fn test_bfs_path_by_types() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(true);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));
        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("bridge".to_string()))
            .unwrap();

        assert_eq!(
            graph.bfs_path_by_types(n0, n1, &["road"]).unwrap(),
            Some(vec![n0, n1])
        );
        assert_eq!(graph.bfs_path_by_types(n0, n2, &["road"]).unwrap(), None);
        assert_eq!(
            graph
                .bfs_path_by_types(n0, n2, &["road", "bridge"])
                .unwrap(),
            Some(vec![n0, n1, n2])
        );
    }

    #[test]
    fn test_dfs() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(false);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));
        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("bridge".to_string()))
            .unwrap();

        let mut visited = HashSet::new();
        assert!(graph.dfs(n0, n2, &mut visited));
    }

    #[test]
    fn test_invalid_nodes() {
        let graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(false);
        assert!(!graph.has_node(NodeId::from_index(0)));
        assert!(!graph.has_path(NodeId::from_index(0), NodeId::from_index(1)));
        assert!(!graph.has_path_by_types(NodeId::from_index(0), NodeId::from_index(1), &["road"]));
        assert!(matches!(
            graph.bfs_path(NodeId::from_index(0), NodeId::from_index(1)),
            Err(SearchError::InvalidNodeReference(_))
        ));
        assert!(matches!(
            graph.bfs_path_by_types(NodeId::from_index(0), NodeId::from_index(1), &["road"]),
            Err(SearchError::InvalidNodeReference(_))
        ));
    }

    #[test]
    fn test_cycle_detection_directed() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(true);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("bridge".to_string()))
            .unwrap();
        graph
            .add_edge(n2, n0, 1.0, TestEdge("path".to_string()))
            .unwrap();

        assert!(graph.has_cycle());
    }

    #[test]
    fn test_cycle_detection_directed_by_types() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(true);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("bridge".to_string()))
            .unwrap();
        graph
            .add_edge(n2, n0, 1.0, TestEdge("path".to_string()))
            .unwrap();

        assert!(graph.has_cycle_by_types(&["road", "bridge", "path"]));
        assert!(!graph.has_cycle_by_types(&["road", "bridge"]));
    }

    #[test]
    fn test_cycle_detection_undirected() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(false);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("bridge".to_string()))
            .unwrap();
        graph
            .add_edge(n2, n0, 1.0, TestEdge("path".to_string()))
            .unwrap();

        assert!(graph.has_cycle());
    }

    #[test]
    fn test_cycle_detection_undirected_by_types() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(false);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("bridge".to_string()))
            .unwrap();
        graph
            .add_edge(n2, n0, 1.0, TestEdge("path".to_string()))
            .unwrap();

        assert!(graph.has_cycle_by_types(&["road", "bridge", "path"]));
        assert!(!graph.has_cycle_by_types(&["road", "bridge"]));
    }

    #[test]
    fn test_no_cycle_directed() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(true);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("bridge".to_string()))
            .unwrap();

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

    #[test]
    fn test_no_cycle_directed_by_types() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(true);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("bridge".to_string()))
            .unwrap();

        assert!(!graph.has_cycle_by_types(&["road", "bridge"]));
    }

    #[test]
    fn test_no_cycle_undirected() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(false);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("bridge".to_string()))
            .unwrap();

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

    #[test]
    fn test_no_cycle_undirected_by_types() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(false);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));
        let n2 = graph.add_node(TestNode("C".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 1.0, TestEdge("bridge".to_string()))
            .unwrap();

        assert!(!graph.has_cycle_by_types(&["road", "bridge"]));
    }

    #[test]
    fn test_multiple_edges() {
        let mut graph = HeterogeneousGraph::<f64, TestNode, TestEdge>::new(true);
        let n0 = graph.add_node(TestNode("A".to_string()));
        let n1 = graph.add_node(TestNode("B".to_string()));

        graph
            .add_edge(n0, n1, 1.0, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n0, n1, 2.0, TestEdge("path".to_string()))
            .unwrap();

        assert!(graph.has_path(n0, n1));
        assert!(graph.has_path_by_types(n0, n1, &["road"]));
        assert_eq!(graph.bfs_path(n0, n1).unwrap(), Some(vec![n0, n1]));
        assert_eq!(
            graph.bfs_path_by_types(n0, n1, &["path"]).unwrap(),
            Some(vec![n0, n1])
        );
        assert!(!graph.has_cycle());
        assert!(!graph.has_cycle_by_types(&["road", "path"]));
    }
}