xgraph 3.0.0

//! Shortest path algorithms for weighted graphs
//!
//! This module provides Dijkstra's algorithm for graphs with non-negative edge weights,
//! reporting either the distances alone, the distances together with the predecessor tree,
//! or a single reconstructed route.
//!
//! # Features
//! - Dijkstra's algorithm from a single source, for directed and undirected graphs
//! - Path reconstruction, not just distances
//! - Weights only need to be partially ordered, so floating-point weights are supported
//! - Violated preconditions (negative or incomparable weights) are reported as errors
//!   rather than silently producing a wrong answer
//!
//! # Examples
//!
//! Integer weights:
//! ```rust
//! use xgraph::graph::graph::Graph;
//! use xgraph::graph::algorithms::shortest_path::ShortestPath;
//!
//! 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, 10, "road").unwrap();
//!
//! let distances = graph.dijkstra(a).unwrap();
//! assert_eq!(distances[&b], 10);
//! ```
//!
//! Floating-point weights and a reconstructed route:
//! ```rust
//! use xgraph::graph::graph::Graph;
//! use xgraph::graph::algorithms::shortest_path::ShortestPath;
//!
//! let mut graph = Graph::<f64, &str, &str>::new(false);
//! let a = graph.add_node("A");
//! let b = graph.add_node("B");
//! let c = graph.add_node("C");
//! graph.add_edge(a, b, 1.5, "road").unwrap();
//! graph.add_edge(b, c, 2.25, "road").unwrap();
//!
//! let (route, cost) = graph.shortest_path_to(a, c).unwrap().unwrap();
//! assert_eq!(route, vec![a, b, c]);
//! assert_eq!(cost, 3.75);
//! ```

use crate::graph::graph::{Graph, NodeId};
use std::collections::HashMap;
use std::fmt::Debug;
use std::hash::Hash;
use std::ops::Add;

pub use crate::core::algo::shortest_path::ShortestPathError;

/// Trait for shortest path calculations in weighted graphs.
///
/// # Type Parameters
/// - `W`: Edge weight type. Must be addable, copyable, partially ordered, and have a
///   `Default` that represents zero.
/// - `N`: Node data type, must be clonable, equatable, hashable, and debuggable.
/// - `E`: Edge data type, must be clonable and debuggable.
#[deprecated(
    since = "3.0.0",
    note = "superseded by `xgraph::core::ShortestPath`, which is implemented for every \
            graph view — including filtered ones — and carries no unused type parameters"
)]
pub trait ShortestPath<W, N, E>
where
    W: Add<Output = W> + PartialOrd + Copy + Default,
    N: Clone + Eq + Hash + Debug,
    E: Clone + Default + Debug,
{
    /// Calculates shortest path distances from a start node using Dijkstra's algorithm.
    ///
    /// # Examples
    /// ```rust
    /// use xgraph::core::ShortestPath;
    /// use xgraph::graph::graph::Graph;
    ///
    /// let mut graph = Graph::<u32, i32, &str>::new(true);
    /// let a = graph.add_node(0);
    /// let b = graph.add_node(1);
    /// graph.add_edge(a, b, 5, "edge").unwrap();
    ///
    /// assert_eq!(graph.dijkstra(a).unwrap().get(&b), Some(&5));
    /// ```
    fn dijkstra(&self, start: NodeId) -> Result<HashMap<NodeId, W>, ShortestPathError>;

    /// Calculates shortest path distances together with the predecessor tree.
    #[allow(clippy::type_complexity)]
    fn dijkstra_with_predecessors(
        &self,
        start: NodeId,
    ) -> Result<(HashMap<NodeId, W>, HashMap<NodeId, NodeId>), ShortestPathError>;

    /// Reconstructs one shortest route between two nodes.
    fn shortest_path_to(
        &self,
        start: NodeId,
        target: NodeId,
    ) -> Result<Option<(Vec<NodeId>, W)>, ShortestPathError>;
}

#[allow(deprecated)]
impl<W, N, E> ShortestPath<W, N, E> for Graph<W, N, E>
where
    W: Add<Output = W> + PartialOrd + Copy + Default,
    N: Clone + Eq + Hash + Debug,
    E: Clone + Default + Debug,
{
    fn dijkstra(&self, start: NodeId) -> Result<HashMap<NodeId, W>, ShortestPathError> {
        crate::core::ShortestPath::dijkstra(self, start)
    }

    fn dijkstra_with_predecessors(
        &self,
        start: NodeId,
    ) -> Result<(HashMap<NodeId, W>, HashMap<NodeId, NodeId>), ShortestPathError> {
        crate::core::ShortestPath::dijkstra_with_predecessors(self, start)
    }

    fn shortest_path_to(
        &self,
        start: NodeId,
        target: NodeId,
    ) -> Result<Option<(Vec<NodeId>, W)>, ShortestPathError> {
        crate::core::ShortestPath::shortest_path_to(self, start, target)
    }
}

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

    /// Test to check basic functionality of Dijkstra's algorithm.
    #[test]
    fn test_dijkstra_basic() {
        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, 2, ()).unwrap();
        graph.add_edge(n1, n2, 3, ()).unwrap();

        let distances = graph.dijkstra(n0).unwrap();
        assert_eq!(distances[&n0], 0);
        assert_eq!(distances[&n1], 2);
        assert_eq!(distances[&n2], 5);
    }

    /// Test to check handling of an unreachable node in the graph.
    #[test]
    fn test_unreachable_node() {
        let mut graph = Graph::<u64, (), ()>::new(true);
        let n0 = graph.add_node(());
        let n1 = graph.add_node(());

        let distances = graph.dijkstra(n0).unwrap();
        assert_eq!(distances.get(&n1), None);
    }

    /// Test to check error handling for an invalid start node.
    #[test]
    fn test_invalid_start_node() {
        let graph = Graph::<u32, (), ()>::new(false);
        assert!(matches!(
            graph.dijkstra(NodeId::from_index(999)),
            Err(ShortestPathError::InvalidStartNode(id)) if id == NodeId::from_index(999)
        ));
    }

    /// Floating-point weights were rejected outright while the trait demanded `W: Ord`.
    #[test]
    fn test_dijkstra_with_float_weights() {
        let mut graph = Graph::<f64, (), ()>::new(false);
        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        let n2 = graph.add_node(());

        graph.add_edge(n0, n1, 1.5, ()).unwrap();
        graph.add_edge(n1, n2, 2.25, ()).unwrap();
        graph.add_edge(n0, n2, 10.0, ()).unwrap();

        let distances = graph.dijkstra(n0).unwrap();
        assert_eq!(distances[&n2], 3.75);
    }

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

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

        assert_eq!(
            graph.shortest_path_to(n0, n3).unwrap(),
            Some((vec![n0, n1, n3], 2))
        );
        // A node is trivially reachable from itself at zero cost.
        assert_eq!(graph.shortest_path_to(n0, n0).unwrap(), Some((vec![n0], 0)));
    }

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

        assert_eq!(graph.shortest_path_to(n0, n1).unwrap(), None);
        assert!(matches!(
            graph.shortest_path_to(n0, NodeId::from_index(999)),
            Err(ShortestPathError::InvalidTargetNode(id)) if id == NodeId::from_index(999)
        ));
    }

    /// Dijkstra is simply wrong on negative weights, so the precondition is reported
    /// instead of a plausible-looking distance map.
    #[test]
    fn test_negative_weight_is_rejected() {
        let mut graph = Graph::<i32, (), ()>::new(true);
        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        graph.add_edge(n0, n1, -3, ()).unwrap();

        assert!(matches!(
            graph.dijkstra(n0),
            Err(ShortestPathError::NegativeWeight { .. })
        ));
    }

    /// A NaN weight would make the priority queue's ordering incoherent.
    #[test]
    fn test_nan_weight_is_rejected() {
        let mut graph = Graph::<f64, (), ()>::new(true);
        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        graph.add_edge(n0, n1, f64::NAN, ()).unwrap();

        assert!(matches!(
            graph.dijkstra(n0),
            Err(ShortestPathError::IncomparableWeight { .. })
        ));
    }
}