oxihuman_core/
simple_graph.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3#![allow(dead_code)]
4
5//! A simple directed graph with integer node ids and string edge labels.
6
7use std::collections::{HashMap, HashSet, VecDeque};
8
9/// An edge in the graph.
10#[allow(dead_code)]
11#[derive(Debug, Clone)]
12pub struct GraphEdge {
13    pub from: u32,
14    pub to: u32,
15    pub label: String,
16    pub weight: f32,
17}
18
19/// Simple directed graph.
20#[allow(dead_code)]
21pub struct SimpleGraph {
22    nodes: HashSet<u32>,
23    edges: Vec<GraphEdge>,
24    node_labels: HashMap<u32, String>,
25}
26
27#[allow(dead_code)]
28impl SimpleGraph {
29    pub fn new() -> Self {
30        Self {
31            nodes: HashSet::new(),
32            edges: Vec::new(),
33            node_labels: HashMap::new(),
34        }
35    }
36
37    pub fn add_node(&mut self, id: u32, label: &str) {
38        self.nodes.insert(id);
39        self.node_labels.insert(id, label.to_string());
40    }
41
42    pub fn remove_node(&mut self, id: u32) -> bool {
43        if !self.nodes.remove(&id) {
44            return false;
45        }
46        self.node_labels.remove(&id);
47        self.edges.retain(|e| e.from != id && e.to != id);
48        true
49    }
50
51    pub fn add_edge(&mut self, from: u32, to: u32, label: &str, weight: f32) {
52        self.nodes.insert(from);
53        self.nodes.insert(to);
54        self.edges.push(GraphEdge {
55            from,
56            to,
57            label: label.to_string(),
58            weight,
59        });
60    }
61
62    pub fn node_count(&self) -> usize {
63        self.nodes.len()
64    }
65
66    pub fn edge_count(&self) -> usize {
67        self.edges.len()
68    }
69
70    pub fn has_node(&self, id: u32) -> bool {
71        self.nodes.contains(&id)
72    }
73
74    pub fn neighbors(&self, id: u32) -> Vec<u32> {
75        self.edges
76            .iter()
77            .filter(|e| e.from == id)
78            .map(|e| e.to)
79            .collect()
80    }
81
82    pub fn in_neighbors(&self, id: u32) -> Vec<u32> {
83        self.edges
84            .iter()
85            .filter(|e| e.to == id)
86            .map(|e| e.from)
87            .collect()
88    }
89
90    /// BFS reachability from `start`.
91    pub fn bfs(&self, start: u32) -> Vec<u32> {
92        let mut visited = HashSet::new();
93        let mut queue = VecDeque::new();
94        let mut order = Vec::new();
95        if !self.nodes.contains(&start) {
96            return order;
97        }
98        queue.push_back(start);
99        visited.insert(start);
100        while let Some(node) = queue.pop_front() {
101            order.push(node);
102            for nb in self.neighbors(node) {
103                if visited.insert(nb) {
104                    queue.push_back(nb);
105                }
106            }
107        }
108        order
109    }
110
111    /// Check whether there is a path from `from` to `to`.
112    pub fn has_path(&self, from: u32, to: u32) -> bool {
113        self.bfs(from).contains(&to)
114    }
115
116    pub fn node_label(&self, id: u32) -> Option<&str> {
117        self.node_labels.get(&id).map(|s| s.as_str())
118    }
119
120    pub fn is_empty(&self) -> bool {
121        self.nodes.is_empty()
122    }
123
124    pub fn clear(&mut self) {
125        self.nodes.clear();
126        self.edges.clear();
127        self.node_labels.clear();
128    }
129}
130
131impl Default for SimpleGraph {
132    fn default() -> Self {
133        Self::new()
134    }
135}
136
137pub fn new_simple_graph() -> SimpleGraph {
138    SimpleGraph::new()
139}
140
141#[cfg(test)]
142mod tests {
143    use super::*;
144
145    #[test]
146    fn add_nodes_and_edges() {
147        let mut g = new_simple_graph();
148        g.add_node(1, "a");
149        g.add_node(2, "b");
150        g.add_edge(1, 2, "link", 1.0);
151        assert_eq!(g.node_count(), 2);
152        assert_eq!(g.edge_count(), 1);
153    }
154
155    #[test]
156    fn has_node() {
157        let mut g = new_simple_graph();
158        g.add_node(5, "x");
159        assert!(g.has_node(5));
160        assert!(!g.has_node(99));
161    }
162
163    #[test]
164    fn neighbors() {
165        let mut g = new_simple_graph();
166        g.add_edge(1, 2, "", 1.0);
167        g.add_edge(1, 3, "", 1.0);
168        let mut nb = g.neighbors(1);
169        nb.sort_unstable();
170        assert_eq!(nb, vec![2, 3]);
171    }
172
173    #[test]
174    fn bfs_order() {
175        let mut g = new_simple_graph();
176        g.add_edge(0, 1, "", 1.0);
177        g.add_edge(0, 2, "", 1.0);
178        g.add_edge(1, 3, "", 1.0);
179        let visited = g.bfs(0);
180        assert!(visited.contains(&0));
181        assert!(visited.contains(&3));
182    }
183
184    #[test]
185    fn has_path_true() {
186        let mut g = new_simple_graph();
187        g.add_edge(0, 1, "", 1.0);
188        g.add_edge(1, 2, "", 1.0);
189        assert!(g.has_path(0, 2));
190    }
191
192    #[test]
193    fn has_path_false() {
194        let mut g = new_simple_graph();
195        g.add_edge(0, 1, "", 1.0);
196        assert!(!g.has_path(1, 0));
197    }
198
199    #[test]
200    fn remove_node_removes_edges() {
201        let mut g = new_simple_graph();
202        g.add_edge(1, 2, "", 1.0);
203        g.remove_node(1);
204        assert_eq!(g.edge_count(), 0);
205    }
206
207    #[test]
208    fn node_label() {
209        let mut g = new_simple_graph();
210        g.add_node(7, "seven");
211        assert_eq!(g.node_label(7), Some("seven"));
212    }
213
214    #[test]
215    fn clear() {
216        let mut g = new_simple_graph();
217        g.add_edge(1, 2, "", 1.0);
218        g.clear();
219        assert!(g.is_empty());
220    }
221
222    #[test]
223    fn bfs_unreachable_node() {
224        let mut g = new_simple_graph();
225        g.add_node(10, "isolated");
226        let visited = g.bfs(99);
227        assert!(visited.is_empty());
228    }
229}
oxihuman_core/simple_graph.rs

oxihuman_core/
simple_graph.rs
