xgraph 3.0.0

//! Shortest path algorithms for heterogeneous multigraphs.
//!
//! This module provides implementations of Dijkstra's algorithm for computing shortest paths
//! in heterogeneous multigraphs, supporting both directed and undirected graphs with multiple
//! edge types. Key functionalities include:
//! - Computing shortest path distances and predecessors from a single source.
//! - Finding the shortest path between two nodes.
//! - Edge type filtering for type-specific shortest path analysis.
//!
//! 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")]
#[cfg(feature = "hgraph")]
use std::collections::HashMap;
#[cfg(feature = "hgraph")]
use std::fmt::Debug;
#[cfg(feature = "hgraph")]
use std::hash::Hash;
#[cfg(feature = "hgraph")]
use std::ops::Add;

// Error handling additions

/// Error type for shortest path computation failures.
///
/// Represents errors that may occur during shortest path calculations, such as invalid node references.
#[cfg(feature = "hgraph")]
#[derive(Debug, thiserror::Error)]
pub enum ShortestPathError {
    /// Indicates a node referenced in the graph does not exist.
    #[error("Invalid node reference: node ID {0} not found")]
    InvalidNodeReference(NodeId),
    /// Indicates an edge whose weight violates the algorithm's preconditions.
    ///
    /// Dijkstra requires non-negative weights that compare with themselves; a negative
    /// weight or a NaN is reported rather than producing a wrong distance map.
    #[error("{0}")]
    UnusableWeight(crate::core::ShortestPathError),
}

#[cfg(feature = "hgraph")]
impl From<crate::core::ShortestPathError> for ShortestPathError {
    fn from(error: crate::core::ShortestPathError) -> Self {
        use crate::core::ShortestPathError as Core;
        match error {
            Core::InvalidStartNode(id)
            | Core::InvalidTargetNode(id)
            | Core::InvalidNeighborNode(id) => ShortestPathError::InvalidNodeReference(id),
            other => ShortestPathError::UnusableWeight(other),
        }
    }
}

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

#[cfg(feature = "hgraph")]
/// Trait for shortest path operations in heterogeneous multigraphs.
///
/// Provides methods for computing shortest path distances and reconstructing paths using
/// Dijkstra's algorithm, with support for edge type filtering. Methods that may fail due to
/// invalid inputs return a `Result` to handle errors gracefully.
#[deprecated(
    since = "3.0.0",
    note = "superseded by `xgraph::core::ShortestPath`; the `*_by_types` variants become \
            `graph.of_edge_kinds(&[..])` followed by the ordinary method"
)]
pub trait HeteroShortestPath<W, N, E>
where
    W: Add<Output = W> + PartialOrd + Copy + Default + From<u8> + Debug + PartialEq,
    N: Clone + Eq + Hash + Debug + crate::hgraph::h_node::NodeType,
    E: Clone + Default + Debug + crate::hgraph::h_edge::EdgeType,
{
    /// Computes shortest path distances and predecessors from a start node using Dijkstra's algorithm.
    ///
    /// Uses all edges regardless of type to find the shortest paths from the start node to all reachable nodes.
    ///
    /// # Arguments
    /// * `start` - The starting node ID.
    ///
    /// # Returns
    /// A `Result` containing a tuple of:
    /// - `HashMap<NodeId, W>`: Shortest distances from `start` to each reachable node.
    /// - `HashMap<NodeId, NodeId>`: Predecessor nodes for path reconstruction.
    ///
    /// # Errors
    /// Returns `ShortestPathError::InvalidNodeReference` if `start` does not exist in the graph.
    fn dijkstra(&self, start: NodeId) -> Result<(HashMap<NodeId, W>, HashMap<NodeId, NodeId>)>;

    /// Computes shortest path distances and predecessors from a start node, considering only specific edge types.
    ///
    /// Filters edges by type to compute shortest paths in a subgraph defined by `edge_types`.
    ///
    /// # Arguments
    /// * `start` - The starting node ID.
    /// * `edge_types` - A slice of edge type strings to filter the computation.
    ///
    /// # Returns
    /// A `Result` containing a tuple of:
    /// - `HashMap<NodeId, W>`: Shortest distances from `start` to each reachable node.
    /// - `HashMap<NodeId, NodeId>`: Predecessor nodes for path reconstruction.
    ///
    /// # Errors
    /// Returns `ShortestPathError::InvalidNodeReference` if `start` does not exist in the graph.
    fn dijkstra_by_types(
        &self,
        start: NodeId,
        edge_types: &[&str],
    ) -> Result<(HashMap<NodeId, W>, HashMap<NodeId, NodeId>)>;

    /// Finds the shortest path between two nodes using Dijkstra's algorithm.
    ///
    /// Returns the path as a vector of node IDs from `start` to `end`, using all edges.
    ///
    /// # Arguments
    /// * `start` - The starting node ID.
    /// * `end` - The target node ID.
    ///
    /// # Returns
    /// A `Result` containing `Some(Vec<NodeId>)` with the shortest path if found, `None` if no path exists,
    /// or an error if either node is invalid.
    fn dijkstra_path(&self, start: NodeId, end: NodeId) -> Result<Option<Vec<NodeId>>>;

    /// Finds the shortest path between two nodes using Dijkstra's algorithm, considering only specific edge types.
    ///
    /// Returns the path as a vector of node IDs from `start` to `end`, filtered by `edge_types`.
    ///
    /// # Arguments
    /// * `start` - The starting node ID.
    /// * `end` - The target node ID.
    /// * `edge_types` - A slice of edge type strings to filter the computation.
    ///
    /// # Returns
    /// A `Result` containing `Some(Vec<NodeId>)` with the shortest path if found, `None` if no path exists,
    /// or an error if either node is invalid.
    fn dijkstra_path_by_types(
        &self,
        start: NodeId,
        end: NodeId,
        edge_types: &[&str],
    ) -> Result<Option<Vec<NodeId>>>;
}

#[cfg(feature = "hgraph")]
#[allow(deprecated)]
impl<W, N, E> HeteroShortestPath<W, N, E> for HeterogeneousGraph<W, N, E>
where
    W: Add<Output = W> + PartialOrd + Copy + Default + From<u8> + Debug + PartialEq,
    N: Clone + Eq + Hash + Debug + crate::hgraph::h_node::NodeType,
    E: Clone + Default + Debug + crate::hgraph::h_edge::EdgeType,
{
    fn dijkstra(&self, start: NodeId) -> Result<(HashMap<NodeId, W>, HashMap<NodeId, NodeId>)> {
        crate::core::ShortestPath::dijkstra_with_predecessors(self, start)
            .map_err(ShortestPathError::from)
    }

    fn dijkstra_by_types(
        &self,
        start: NodeId,
        edge_types: &[&str],
    ) -> Result<(HashMap<NodeId, W>, HashMap<NodeId, NodeId>)> {
        crate::core::ShortestPath::dijkstra_with_predecessors(
            &self.of_edge_kinds(edge_types),
            start,
        )
        .map_err(ShortestPathError::from)
    }

    fn dijkstra_path(&self, start: NodeId, end: NodeId) -> Result<Option<Vec<NodeId>>> {
        crate::core::ShortestPath::shortest_path_to(self, start, end)
            .map(|found| found.map(|(route, _)| route))
            .map_err(ShortestPathError::from)
    }

    fn dijkstra_path_by_types(
        &self,
        start: NodeId,
        end: NodeId,
        edge_types: &[&str],
    ) -> Result<Option<Vec<NodeId>>> {
        crate::core::ShortestPath::shortest_path_to(&self.of_edge_kinds(edge_types), start, end)
            .map(|found| found.map(|(route, _)| route))
            .map_err(ShortestPathError::from)
    }
}

#[cfg(test)]
#[allow(deprecated)]
#[cfg(feature = "hgraph")]
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_dijkstra() {
        let mut graph = HeterogeneousGraph::<u32, 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, 4, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 3, TestEdge("bridge".to_string()))
            .unwrap();
        graph
            .add_edge(n0, n2, 8, TestEdge("path".to_string()))
            .unwrap();

        let (distances, _) = graph.dijkstra(n0).unwrap();
        assert_eq!(distances[&n0], 0);
        assert_eq!(distances[&n1], 4);
        assert_eq!(distances[&n2], 7); // 0 -> 1 -> 2
    }

    #[test]
    fn test_dijkstra_by_types() {
        let mut graph = HeterogeneousGraph::<u32, 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, 4, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 3, TestEdge("bridge".to_string()))
            .unwrap();
        graph
            .add_edge(n0, n2, 8, TestEdge("path".to_string()))
            .unwrap();

        let (distances, _) = graph.dijkstra_by_types(n0, &["road", "bridge"]).unwrap();
        assert_eq!(distances[&n0], 0);
        assert_eq!(distances[&n1], 4);
        assert_eq!(distances[&n2], 7); // 0 -> 1 -> 2

        let (distances, _) = graph.dijkstra_by_types(n0, &["road"]).unwrap();
        assert_eq!(distances[&n0], 0);
        assert_eq!(distances[&n1], 4);
        assert_eq!(distances.get(&n2), None); // n2 unreachable with only "road"
    }

    #[test]
    fn test_dijkstra_path() {
        let mut graph = HeterogeneousGraph::<u32, 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, 4, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 3, TestEdge("bridge".to_string()))
            .unwrap();
        graph
            .add_edge(n0, n2, 8, TestEdge("path".to_string()))
            .unwrap();

        let path = graph.dijkstra_path(n0, n2).unwrap();
        assert_eq!(path, Some(vec![n0, n1, n2]));
    }

    #[test]
    fn test_dijkstra_path_by_types() {
        let mut graph = HeterogeneousGraph::<u32, 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, 4, TestEdge("road".to_string()))
            .unwrap();
        graph
            .add_edge(n1, n2, 3, TestEdge("bridge".to_string()))
            .unwrap();
        graph
            .add_edge(n0, n2, 8, TestEdge("path".to_string()))
            .unwrap();

        let path = graph
            .dijkstra_path_by_types(n0, n2, &["road", "bridge"])
            .unwrap();
        assert_eq!(path, Some(vec![n0, n1, n2]));

        let path = graph.dijkstra_path_by_types(n0, n2, &["path"]).unwrap();
        assert_eq!(path, Some(vec![n0, n2]));

        let path = graph.dijkstra_path_by_types(n0, n2, &["road"]).unwrap();
        assert_eq!(path, None); // n2 unreachable with only "road"
    }

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

        let (distances, _) = graph.dijkstra(n0).unwrap();
        assert_eq!(distances[&n0], 0);
        assert_eq!(distances.get(&n1), None);

        let path = graph.dijkstra_path(n0, n1).unwrap();
        assert_eq!(path, None);

        let path = graph.dijkstra_path_by_types(n0, n1, &["road"]).unwrap();
        assert_eq!(path, None);
    }

    #[test]
    fn test_same_start_end() {
        let mut graph = HeterogeneousGraph::<u32, 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, 4, TestEdge("road".to_string()))
            .unwrap();

        let path = graph.dijkstra_path(n0, n0).unwrap();
        assert_eq!(path, Some(vec![n0]));

        let path = graph.dijkstra_path_by_types(n0, n0, &["road"]).unwrap();
        assert_eq!(path, Some(vec![n0]));
    }

    #[test]
    fn test_invalid_node() {
        let graph = HeterogeneousGraph::<u32, TestNode, TestEdge>::new(true);
        assert!(matches!(
            graph.dijkstra(NodeId::from_index(0)),
            Err(ShortestPathError::InvalidNodeReference(_))
        ));
        assert!(matches!(
            graph.dijkstra_path(NodeId::from_index(0), NodeId::from_index(1)),
            Err(ShortestPathError::InvalidNodeReference(_))
        ));
        assert!(matches!(
            graph.dijkstra_path_by_types(NodeId::from_index(0), NodeId::from_index(1), &["road"]),
            Err(ShortestPathError::InvalidNodeReference(_))
        ));
    }
}