evolving_sheaf/
graph.rs

1
2
3/// A directed edge in the graph.
4#[derive(Debug, Clone, Copy, PartialEq)]
5pub struct Edge {
6    pub src: usize,
7    pub dst: usize,
8    pub weight: f64,
9}
10
11impl Edge {
12    pub fn new(src: usize, dst: usize, weight: f64) -> Self {
13        Edge { src, dst, weight }
14    }
15}
16
17/// A directed graph with vertex-weighted edges.
18#[derive(Debug, Clone)]
19pub struct Graph {
20    pub n_vertices: usize,
21    pub n_edges: usize,
22    pub edges: Vec<Edge>,
23}
24
25impl Graph {
26    pub fn new(n_vertices: usize, edges: Vec<Edge>) -> Self {
27        let n_edges = edges.len();
28        Graph {
29            n_vertices,
30            n_edges,
31            edges,
32        }
33    }
34
35    /// Build a cycle graph C_n.
36    pub fn cycle(n: usize) -> Self {
37        let edges: Vec<Edge> = (0..n)
38            .map(|i| Edge::new(i, (i + 1) % n, 1.0))
39            .collect();
40        Graph::new(n, edges)
41    }
42
43    /// Build a path graph P_n.
44    pub fn path(n: usize) -> Self {
45        assert!(n >= 2, "path graph needs at least 2 vertices");
46        let edges: Vec<Edge> = (0..n - 1)
47            .map(|i| Edge::new(i, i + 1, 1.0))
48            .collect();
49        Graph::new(n, edges)
50    }
51
52    /// Build a complete graph K_n.
53    pub fn complete(n: usize) -> Self {
54        let mut edges = Vec::with_capacity(n * (n - 1) / 2);
55        for i in 0..n {
56            for j in (i + 1)..n {
57                edges.push(Edge::new(i, j, 1.0));
58            }
59        }
60        Graph::new(n, edges)
61    }
62
63    /// Build a 3-regular expander-like graph (Paley-ish construction).
64    pub fn expander(n: usize) -> Self {
65        let max_edges = n * 3;
66        let mut edges = Vec::with_capacity(max_edges);
67        for i in 0..n {
68            let targets = [(i + 1) % n, (i + 2) % n, (i + n / 3) % n];
69            for &t in &targets {
70                let (a, b) = if i < t { (i, t) } else { (t, i) };
71                if !edges.iter().any(|e: &Edge| e.src == a && e.dst == b) {
72                    edges.push(Edge::new(a, b, 1.0));
73                }
74            }
75        }
76        Graph::new(n, edges)
77    }
78
79}
80
81#[cfg(test)]
82mod tests {
83    use super::*;
84
85    #[test]
86    fn test_cycle_4_vertices() {
87        let g = Graph::cycle(4);
88        assert_eq!(g.n_vertices, 4);
89        assert_eq!(g.n_edges, 4);
90        for i in 0..4 {
91            assert_eq!(g.edges[i].src, i);
92            assert_eq!(g.edges[i].dst, (i + 1) % 4);
93        }
94    }
95
96    #[test]
97    fn test_path_5() {
98        let g = Graph::path(5);
99        assert_eq!(g.n_vertices, 5);
100        assert_eq!(g.n_edges, 4);
101    }
102
103    #[test]
104    fn test_complete_k4() {
105        let g = Graph::complete(4);
106        assert_eq!(g.n_vertices, 4);
107        assert_eq!(g.n_edges, 6);
108    }
109
110    #[test]
111    fn test_expander_10() {
112        let g = Graph::expander(10);
113        assert_eq!(g.n_vertices, 10);
114        assert!(g.n_edges >= 10);
115    }
116
117    #[test]
118    fn test_cycle_3() {
119        let g = Graph::cycle(3);
120        assert_eq!(g.n_vertices, 3);
121        assert_eq!(g.n_edges, 3);
122    }
123
124    #[test]
125    fn test_new_graph() {
126        let edges = vec![Edge::new(0, 1, 2.0)];
127        let g = Graph::new(2, edges);
128        assert_eq!(g.n_vertices, 2);
129        assert_eq!(g.n_edges, 1);
130        assert!((g.edges[0].weight - 2.0).abs() < 1e-12);
131    }
132}
evolving_sheaf/graph.rs

evolving_sheaf/
graph.rs
