oxihuman_core/
dep_graph_simple.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3#![allow(dead_code)]
4
5/// Simple directed graph for dependency resolution via Kahn's topological sort.
6pub struct DepGraph {
7    pub nodes: Vec<String>,
8    pub edges: Vec<(usize, usize)>,
9}
10
11impl DepGraph {
12    pub fn new() -> Self {
13        DepGraph {
14            nodes: Vec::new(),
15            edges: Vec::new(),
16        }
17    }
18}
19
20impl Default for DepGraph {
21    fn default() -> Self {
22        Self::new()
23    }
24}
25
26pub fn new_dep_graph() -> DepGraph {
27    DepGraph::new()
28}
29
30pub fn dep_add_node(g: &mut DepGraph, name: &str) -> usize {
31    let idx = g.nodes.len();
32    g.nodes.push(name.to_string());
33    idx
34}
35
36pub fn dep_add_edge(g: &mut DepGraph, from: usize, to: usize) {
37    g.edges.push((from, to));
38}
39
40pub fn dep_node_count(g: &DepGraph) -> usize {
41    g.nodes.len()
42}
43
44/// Kahn's algorithm. Returns `None` if a cycle is detected.
45pub fn dep_topo_sort(g: &DepGraph) -> Option<Vec<usize>> {
46    let n = g.nodes.len();
47    let mut in_degree = vec![0usize; n];
48    for &(_, to) in &g.edges {
49        in_degree[to] += 1;
50    }
51
52    let mut queue: std::collections::VecDeque<usize> =
53        (0..n).filter(|&i| in_degree[i] == 0).collect();
54
55    let mut order = Vec::with_capacity(n);
56    while let Some(node) = queue.pop_front() {
57        order.push(node);
58        for &(from, to) in &g.edges {
59            if from == node {
60                in_degree[to] -= 1;
61                if in_degree[to] == 0 {
62                    queue.push_back(to);
63                }
64            }
65        }
66    }
67
68    if order.len() == n {
69        Some(order)
70    } else {
71        None
72    }
73}
74
75pub fn dep_has_cycle(g: &DepGraph) -> bool {
76    dep_topo_sort(g).is_none()
77}
78
79#[cfg(test)]
80mod tests {
81    use super::*;
82
83    #[test]
84    fn test_new_empty() {
85        /* new graph is empty */
86        let g = new_dep_graph();
87        assert_eq!(dep_node_count(&g), 0);
88    }
89
90    #[test]
91    fn test_add_nodes() {
92        /* adding nodes increments count */
93        let mut g = new_dep_graph();
94        let a = dep_add_node(&mut g, "a");
95        let b = dep_add_node(&mut g, "b");
96        assert_eq!(a, 0);
97        assert_eq!(b, 1);
98        assert_eq!(dep_node_count(&g), 2);
99    }
100
101    #[test]
102    fn test_topo_sort_linear() {
103        /* linear chain: a -> b -> c */
104        let mut g = new_dep_graph();
105        let a = dep_add_node(&mut g, "a");
106        let b = dep_add_node(&mut g, "b");
107        let c = dep_add_node(&mut g, "c");
108        dep_add_edge(&mut g, a, b);
109        dep_add_edge(&mut g, b, c);
110        let order = dep_topo_sort(&g).expect("should succeed");
111        assert_eq!(order, vec![a, b, c]);
112    }
113
114    #[test]
115    fn test_no_cycle() {
116        /* acyclic graph has no cycle */
117        let mut g = new_dep_graph();
118        let a = dep_add_node(&mut g, "a");
119        let b = dep_add_node(&mut g, "b");
120        dep_add_edge(&mut g, a, b);
121        assert!(!dep_has_cycle(&g));
122    }
123
124    #[test]
125    fn test_cycle_detected() {
126        /* cycle: a -> b -> a */
127        let mut g = new_dep_graph();
128        let a = dep_add_node(&mut g, "a");
129        let b = dep_add_node(&mut g, "b");
130        dep_add_edge(&mut g, a, b);
131        dep_add_edge(&mut g, b, a);
132        assert!(dep_has_cycle(&g));
133        assert!(dep_topo_sort(&g).is_none());
134    }
135
136    #[test]
137    fn test_no_edges() {
138        /* nodes with no edges sort in insertion order */
139        let mut g = new_dep_graph();
140        dep_add_node(&mut g, "x");
141        dep_add_node(&mut g, "y");
142        let order = dep_topo_sort(&g).expect("should succeed");
143        assert_eq!(order.len(), 2);
144    }
145
146    #[test]
147    fn test_default() {
148        /* Default impl works */
149        let g = DepGraph::default();
150        assert_eq!(g.nodes.len(), 0);
151    }
152
153    #[test]
154    fn test_diamond() {
155        /* diamond graph: a -> b, a -> c, b -> d, c -> d */
156        let mut g = new_dep_graph();
157        let a = dep_add_node(&mut g, "a");
158        let b = dep_add_node(&mut g, "b");
159        let c = dep_add_node(&mut g, "c");
160        let d = dep_add_node(&mut g, "d");
161        dep_add_edge(&mut g, a, b);
162        dep_add_edge(&mut g, a, c);
163        dep_add_edge(&mut g, b, d);
164        dep_add_edge(&mut g, c, d);
165        let order = dep_topo_sort(&g).expect("should succeed");
166        assert_eq!(order.len(), 4);
167        /* a must come before b, c, d */
168        let pos_a = order.iter().position(|&x| x == a).expect("should succeed");
169        let pos_d = order.iter().position(|&x| x == d).expect("should succeed");
170        assert!(pos_a < pos_d);
171    }
172}
oxihuman_core/dep_graph_simple.rs

oxihuman_core/
dep_graph_simple.rs
