oxicuda_graphalg/repr/
weighted_graph.rs

1//! Weighted graph representation (adjacency list of `(neighbor, weight)`).
2
3use crate::error::{GraphalgError, GraphalgResult};
4
5/// Weighted graph stored as adjacency list of `(neighbor, weight)` pairs.
6#[derive(Debug, Clone)]
7pub struct WeightedGraph {
8    pub n: usize,
9    pub edges: Vec<Vec<(usize, f64)>>,
10}
11
12impl WeightedGraph {
13    pub fn new(n: usize) -> Self {
14        Self {
15            n,
16            edges: vec![Vec::new(); n],
17        }
18    }
19
20    pub fn add_edge(&mut self, u: usize, v: usize, w: f64) -> GraphalgResult<()> {
21        if u >= self.n || v >= self.n {
22            return Err(GraphalgError::IndexOutOfBounds {
23                index: u.max(v),
24                len: self.n,
25            });
26        }
27        if w.is_nan() || w.is_infinite() {
28            return Err(GraphalgError::InvalidEdgeWeight(format!(
29                "edge ({u},{v}) weight not finite: {w}"
30            )));
31        }
32        self.edges[u].push((v, w));
33        Ok(())
34    }
35
36    pub fn add_undirected_edge(&mut self, u: usize, v: usize, w: f64) -> GraphalgResult<()> {
37        self.add_edge(u, v, w)?;
38        if u != v {
39            self.add_edge(v, u, w)?;
40        }
41        Ok(())
42    }
43
44    pub fn num_edges(&self) -> usize {
45        self.edges.iter().map(|adj| adj.len()).sum()
46    }
47
48    pub fn neighbors(&self, u: usize) -> GraphalgResult<&[(usize, f64)]> {
49        if u >= self.n {
50            return Err(GraphalgError::IndexOutOfBounds {
51                index: u,
52                len: self.n,
53            });
54        }
55        Ok(&self.edges[u])
56    }
57
58    /// Iterate over all directed edges as `(u, v, w)`.
59    pub fn all_edges(&self) -> Vec<(usize, usize, f64)> {
60        let mut out = Vec::with_capacity(self.num_edges());
61        for (u, adj) in self.edges.iter().enumerate() {
62            for &(v, w) in adj {
63                out.push((u, v, w));
64            }
65        }
66        out
67    }
68
69    /// Reverse the directed weighted graph.
70    pub fn reverse(&self) -> Self {
71        let mut rev = Self::new(self.n);
72        for (u, adj) in self.edges.iter().enumerate() {
73            for &(v, w) in adj {
74                rev.edges[v].push((u, w));
75            }
76        }
77        rev
78    }
79}
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84
85    #[test]
86    fn build_weighted() {
87        let mut g = WeightedGraph::new(3);
88        g.add_edge(0, 1, 2.5).expect("ok");
89        g.add_edge(1, 2, 4.0).expect("ok");
90        assert_eq!(g.num_edges(), 2);
91    }
92
93    #[test]
94    fn undirected_weighted() {
95        let mut g = WeightedGraph::new(3);
96        g.add_undirected_edge(0, 1, 1.5).expect("ok");
97        assert_eq!(g.num_edges(), 2);
98    }
99
100    #[test]
101    fn rejects_nan() {
102        let mut g = WeightedGraph::new(2);
103        assert!(g.add_edge(0, 1, f64::NAN).is_err());
104    }
105}
oxicuda_graphalg/repr/weighted_graph.rs

oxicuda_graphalg/repr/
weighted_graph.rs
