graph_algorithms/
lib.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#![forbid(unsafe_code)]

use std::{error::Error, fmt};

pub mod bellman_ford;
pub mod dijkstra;

pub use bellman_ford::*;
pub use dijkstra::*;

/// Error type for graph algorithms.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum GraphError {
    /// Graph contains a negative weight cycle.
    NegativeWeightCycle,
}

impl Error for GraphError {}

impl fmt::Display for GraphError {
    /// Display the error message.
    ///
    /// # Arguments
    ///
    /// - `f`: Formatter.
    ///
    /// # Returns
    ///
    /// Result containing the formatted error message.
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{:?}", self)
    }
}

/// A trait for graph search algorithms.
pub trait GraphAlgorithm {
    /// Type of node.
    type Node;

    /// Type of weight.
    type Weight;

    /// Run the graph algorithm.
    ///
    /// # Arguments
    ///
    /// - `start`: The starting node.
    ///
    /// # Returns
    ///
    /// Result containing a vector of shortest paths, or an error if applicable.
    fn run(&self, start: Self::Node) -> Result<Vec<Self::Weight>, GraphError>;
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_graph_error() {
        assert_eq!(
            format!("{}", GraphError::NegativeWeightCycle),
            "NegativeWeightCycle"
        );
    }
}