heapless_graphs/algorithms/
kahns.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Kahn's algorithm for topological sorting of directed acyclic graphs (DAGs)
3
4use super::ContainerResultExt;
5
6use super::AlgorithmError;
7use crate::containers::{maps::MapTrait, queues::Deque};
8use crate::graph::{Graph, NodeIndex};
9
10/// Kahn's algorithm for topological sorting
11///
12/// Performs a topological sort on a directed graph using Kahn's algorithm (BFS-based).
13/// This algorithm tracks in-degrees of nodes and processes nodes with zero in-degree.
14/// It detects cycles and returns an error if the graph is not a DAG.
15///
16/// # Arguments
17/// * `graph` - The graph to sort topologically (must implement Graph)
18/// * `queue` - Queue for BFS processing (nodes with zero in-degree)
19/// * `in_degree_map` - Map to track in-degree count for each node
20/// * `sorted_nodes` - Buffer to store the topologically sorted nodes
21///
22/// # Returns
23/// * `Ok(&[NI])` slice of sorted nodes if successful
24/// * `Err(AlgorithmError::CycleDetected)` if a cycle is found
25/// * `Err(AlgorithmError::QueueCapacityExceeded)` if queue capacity exceeded
26/// * `Err(AlgorithmError::ResultCapacityExceeded)` if result buffer is full
27///
28/// # Time Complexity
29/// O(V + E) where V is the number of vertices and E is the number of edges.
30/// For matrix-based graphs with optimized incoming_edges, the in-degree
31/// calculation is O(V) instead of O(V + E).
32pub fn kahns<'a, G, NI, D, M>(
33    graph: &G,
34    mut queue: D,
35    mut in_degree_map: M,
36    sorted_nodes: &'a mut [NI],
37) -> Result<&'a [NI], AlgorithmError<NI>>
38where
39    G: Graph<NI>,
40    NI: NodeIndex,
41    D: Deque<NI>,
42    M: MapTrait<NI, isize>,
43    AlgorithmError<NI>: From<G::Error>,
44{
45    queue.clear();
46
47    let mut sort_index = 0;
48    let mut append_to_list = |node: NI| -> Result<(), AlgorithmError<NI>> {
49        if sort_index >= sorted_nodes.len() {
50            return Err(AlgorithmError::ResultCapacityExceeded);
51        }
52        sorted_nodes[sort_index] = node;
53        sort_index += 1;
54        Ok(())
55    };
56
57    // Calculate in-degrees by directly counting incoming edges for each node
58    for node in graph.iter_nodes()? {
59        let in_degree = graph.incoming_edges(node)?.count() as isize;
60        in_degree_map.insert(node, in_degree).capacity_error()?;
61    }
62
63    // Find all nodes with zero in-degree and add to queue
64    for (node, &degree) in in_degree_map.iter() {
65        if degree == 0 {
66            queue
67                .push_back(*node)
68                .map_err(|_| AlgorithmError::QueueCapacityExceeded)?;
69        }
70    }
71
72    // Process nodes in topological order
73    while let Some(node) = queue.pop_front() {
74        append_to_list(node)?;
75
76        // Reduce in-degree of all neighbors
77        for target in graph.outgoing_edges(node)? {
78            if let Some(degree) = in_degree_map.get_mut(&target) {
79                *degree -= 1;
80                if *degree == 0 {
81                    queue
82                        .push_back(target)
83                        .map_err(|_| AlgorithmError::QueueCapacityExceeded)?;
84                }
85            }
86        }
87    }
88
89    // Check for cycles - if any node still has positive in-degree, there's a cycle
90    for (_, &degree) in in_degree_map.iter() {
91        if degree > 0 {
92            return Err(AlgorithmError::CycleDetected);
93        }
94    }
95
96    Ok(&sorted_nodes[..sort_index])
97}
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102    use crate::containers::{maps::staticdict::Dictionary, queues::CircularQueue};
103    use crate::edgelist::edge_list::EdgeList;
104
105    #[test]
106    fn test_kahns_simple() {
107        // Create a simple DAG: 0 -> 1 -> 2
108        let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (1, 2)]);
109        let queue = CircularQueue::<usize, 8>::new();
110        let in_degree_map = Dictionary::<usize, isize, 8>::new();
111        let mut sorted_nodes = [0usize; 8];
112
113        let result = kahns(&graph, queue, in_degree_map, &mut sorted_nodes).unwrap();
114
115        assert_eq!(result, &[0, 1, 2]);
116    }
117
118    #[test]
119    fn test_kahns_complex() {
120        // Create a more complex DAG: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3
121        let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (0, 2), (1, 3), (2, 3)]);
122        let queue = CircularQueue::<usize, 8>::new();
123        let in_degree_map = Dictionary::<usize, isize, 8>::new();
124        let mut sorted_nodes = [0usize; 8];
125
126        let result = kahns(&graph, queue, in_degree_map, &mut sorted_nodes).unwrap();
127
128        assert_eq!(result.len(), 4);
129
130        // Kahn's algorithm should produce: [0, 1, 2, 3] or [0, 2, 1, 3]
131        // 0 should be first (no incoming edges)
132        // 3 should be last (no outgoing edges)
133        assert_eq!(result[0], 0);
134        assert_eq!(result[result.len() - 1], 3);
135
136        // Check that all nodes are present
137        assert!(result.contains(&1));
138        assert!(result.contains(&2));
139    }
140
141    #[test]
142    fn test_kahns_cycle_detection() {
143        // Create a graph with a cycle: 0 -> 1 -> 2 -> 0
144        let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (1, 2), (2, 0)]);
145        let queue = CircularQueue::<usize, 8>::new();
146        let in_degree_map = Dictionary::<usize, isize, 8>::new();
147        let mut sorted_nodes = [0usize; 8];
148
149        let error = kahns(&graph, queue, in_degree_map, &mut sorted_nodes);
150
151        assert_eq!(error, Err(AlgorithmError::CycleDetected));
152    }
153
154    #[test]
155    fn test_kahns_disconnected() {
156        // Create a disconnected graph: 0 -> 1, 2 -> 3 (no connection between pairs)
157        let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (2, 3)]);
158        let queue = CircularQueue::<usize, 8>::new();
159        let in_degree_map = Dictionary::<usize, isize, 8>::new();
160        let mut sorted_nodes = [0usize; 8];
161
162        let result = kahns(&graph, queue, in_degree_map, &mut sorted_nodes).unwrap();
163
164        assert_eq!(result.len(), 4);
165
166        // Check relative ordering within connected components
167        let pos_0 = result.iter().position(|&x| x == 0).unwrap();
168        let pos_1 = result.iter().position(|&x| x == 1).unwrap();
169        let pos_2 = result.iter().position(|&x| x == 2).unwrap();
170        let pos_3 = result.iter().position(|&x| x == 3).unwrap();
171
172        assert!(pos_0 < pos_1); // 0 should come before 1
173        assert!(pos_2 < pos_3); // 2 should come before 3
174    }
175
176    #[test]
177    fn test_kahns_self_loop() {
178        // Create a graph with a self-loop: 0 -> 0
179        let graph = EdgeList::<8, _, _>::new([(0usize, 0usize)]);
180        let queue = CircularQueue::<usize, 8>::new();
181        let in_degree_map = Dictionary::<usize, isize, 8>::new();
182        let mut sorted_nodes = [0usize; 8];
183
184        let error = kahns(&graph, queue, in_degree_map, &mut sorted_nodes);
185
186        assert_eq!(error, Err(AlgorithmError::CycleDetected));
187    }
188}
heapless_graphs/algorithms/kahns.rs

heapless_graphs/algorithms/
kahns.rs
