15666368678

Committed 15 Jun 2025 06:54PM UTC coverage: 94.26% (+5.0%) from 89.24%

Build # 15666368678

Build Type

Pull #8

github

Committed by

kaidokert

Commit Message

Insert returns an error now

Make insert() return an error

Pull Request Pull Request #8: No ref graphs

Run Details

4008 of 4087 new or added lines in 29 files covered. (98.07%)

43 existing lines in 8 files now uncovered.

5764 of 6115 relevant lines covered (94.26%)

40.31 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

99.09

/src/algorithms/topological_sort.rs

// SPDX-License-Identifier: Apache-2.0

//! Topological sorting algorithms for directed acyclic graphs (DAGs)

use super::AlgorithmError;
use crate::graph::{Graph, NodeIndex};
use crate::visited::TriStateVisitedTracker;

fn topological_sort_dfs_visit<G, NI, VT>(
    graph: &G,
    node: NI,
    visited: &mut VT,
    sorted_nodes: &mut [NI],
    sort_index: &mut usize,
) -> Result<(), AlgorithmError<NI>>
where
    G: Graph<NI>,
    NI: NodeIndex,
    VT: TriStateVisitedTracker<NI> + ?Sized,
    AlgorithmError<NI>: From<G::Error>,
{
    if visited.is_visiting(&node) {
        return Err(AlgorithmError::CycleDetected);
    }
    if visited.is_visited(&node) {
        return Ok(());
    }

    visited.mark_visiting(&node);

    for next_node in graph.outgoing_edges(node)? {
        topological_sort_dfs_visit(graph, next_node, visited, sorted_nodes, sort_index)?;
    }

    visited.mark_visited(&node);

    // Add to front of result (DFS post-order gives reverse topological order)
    if *sort_index >= sorted_nodes.len() {
        return Err(AlgorithmError::ResultCapacityExceeded);
    }
    sorted_nodes[*sort_index] = node;
    *sort_index += 1;

    Ok(())
}

/// DFS-based topological sort algorithm
///
/// Performs a topological sort on a directed graph using depth-first search.
/// The algorithm detects cycles and returns an error if the graph is not a DAG.
///
/// # Arguments
/// * `graph` - The graph to sort topologically (must implement Graph)
/// * `visited` - Tri-state visited tracker (unvisited/visiting/visited)
/// * `sorted_nodes` - Buffer to store the topologically sorted nodes
///
/// # Returns
/// * `Ok(&[NI])` slice of sorted nodes if successful
/// * `Err(AlgorithmError::CycleDetected)` if a cycle is found
/// * `Err(AlgorithmError::ResultCapacityExceeded)` if result buffer is full
///
/// # Time Complexity
/// O(V + E) where V is the number of vertices and E is the number of edges
pub fn topological_sort_dfs<'a, G, NI, VT>(
    graph: &G,
    visited: &mut VT,
    sorted_nodes: &'a mut [NI],
) -> Result<&'a [NI], AlgorithmError<NI>>
where
    G: Graph<NI>,
    NI: NodeIndex,
    VT: TriStateVisitedTracker<NI> + ?Sized,
    AlgorithmError<NI>: From<G::Error>,
{
    visited.reset();
    let mut sort_index = 0;

    // Visit all nodes in the graph
    for node in graph.iter_nodes()? {
        if visited.is_unvisited(&node) {
            topological_sort_dfs_visit(graph, node, visited, sorted_nodes, &mut sort_index)?;
        }
    }

    // Reverse the result since DFS post-order gives reverse topological order
    let result_slice = &mut sorted_nodes[..sort_index];
    result_slice.reverse();

    Ok(result_slice)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::edgelist::edge_list::EdgeList;
    use crate::visited::NodeState;

    #[test]
    fn test_topological_sort_simple() {
        // Create a simple DAG: 0 -> 1 -> 2
        let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (1, 2)]);
        let mut visited = [NodeState::Unvisited; 8];
        let mut sorted_nodes = [0usize; 8];

        let result =
            topological_sort_dfs(&graph, visited.as_mut_slice(), &mut sorted_nodes).unwrap();

        assert_eq!(result, &[0, 1, 2]);
    }

    #[test]
    fn test_topological_sort_complex() {
        // Create a more complex DAG: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3
        let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (0, 2), (1, 3), (2, 3)]);
        let mut visited = [NodeState::Unvisited; 8];
        let mut sorted_nodes = [0usize; 8];

        let result =
            topological_sort_dfs(&graph, visited.as_mut_slice(), &mut sorted_nodes).unwrap();

        assert_eq!(result.len(), 4);

        // Valid topological orderings: [0, 1, 2, 3] or [0, 2, 1, 3]
        // Both should have 0 first and 3 last
        assert_eq!(result[0], 0);
        assert_eq!(result[result.len() - 1], 3);

        // Check that all nodes are present
        assert!(result.contains(&1));
        assert!(result.contains(&2));
    }

    #[test]
    fn test_topological_sort_cycle_detection() {
        // Create a graph with a cycle: 0 -> 1 -> 2 -> 0
        let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (1, 2), (2, 0)]);
        let mut visited = [NodeState::Unvisited; 8];
        let mut sorted_nodes = [0usize; 8];

        let error = topological_sort_dfs(&graph, visited.as_mut_slice(), &mut sorted_nodes);

        assert!(matches!(error, Err(AlgorithmError::CycleDetected)));
    }

    #[test]
    fn test_topological_sort_disconnected() {
        // Create a disconnected graph: 0 -> 1, 2 -> 3 (no connection between pairs)
        let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (2, 3)]);
        let mut visited = [NodeState::Unvisited; 8];
        let mut sorted_nodes = [0usize; 8];

        let result =
            topological_sort_dfs(&graph, visited.as_mut_slice(), &mut sorted_nodes).unwrap();

        assert_eq!(result.len(), 4);

        // Check relative ordering within connected components
        let pos_0 = result.iter().position(|&x| x == 0).unwrap();
        let pos_1 = result.iter().position(|&x| x == 1).unwrap();
        let pos_2 = result.iter().position(|&x| x == 2).unwrap();
        let pos_3 = result.iter().position(|&x| x == 3).unwrap();

        assert!(pos_0 < pos_1); // 0 should come before 1
        assert!(pos_2 < pos_3); // 2 should come before 3
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2
3	//! Topological sorting algorithms for directed acyclic graphs (DAGs)
4
5	use super::AlgorithmError;
6	use crate::graph::{Graph, NodeIndex};
7	use crate::visited::TriStateVisitedTracker;
8
9	fn topological_sort_dfs_visit<G, NI, VT>(	16✔
10	graph: &G,	16✔
11	node: NI,	16✔
12	visited: &mut VT,	16✔
13	sorted_nodes: &mut [NI],	16✔
14	sort_index: &mut usize,	16✔
15	) -> Result<(), AlgorithmError<NI>>	16✔
16	where	16✔
17	G: Graph<NI>,	16✔
18	NI: NodeIndex,	16✔
19	VT: TriStateVisitedTracker<NI> + ?Sized,	16✔
20	AlgorithmError<NI>: From<G::Error>,	16✔
21	{	16✔
22	if visited.is_visiting(&node) {	16✔
23	return Err(AlgorithmError::CycleDetected);	1✔
24	}	15✔
25	if visited.is_visited(&node) {	15✔
26	return Ok(());	1✔
27	}	14✔
28		14✔
29	visited.mark_visiting(&node);	14✔
30
31	for next_node in graph.outgoing_edges(node)? {	14✔
32	topological_sort_dfs_visit(graph, next_node, visited, sorted_nodes, sort_index)?;	11✔
33	}
34
35	visited.mark_visited(&node);	11✔
36		11✔
37	// Add to front of result (DFS post-order gives reverse topological order)	11✔
38	if *sort_index >= sorted_nodes.len() {	11✔
NEW 39	return Err(AlgorithmError::ResultCapacityExceeded);	×
40	}	11✔
41	sorted_nodes[*sort_index] = node;	11✔
42	*sort_index += 1;	11✔
43		11✔
44	Ok(())	11✔
45	}	16✔
46
47	/// DFS-based topological sort algorithm
48	///
49	/// Performs a topological sort on a directed graph using depth-first search.
50	/// The algorithm detects cycles and returns an error if the graph is not a DAG.
51	///
52	/// # Arguments
53	/// * `graph` - The graph to sort topologically (must implement Graph)
54	/// * `visited` - Tri-state visited tracker (unvisited/visiting/visited)
55	/// * `sorted_nodes` - Buffer to store the topologically sorted nodes
56	///
57	/// # Returns
58	/// * `Ok(&[NI])` slice of sorted nodes if successful
59	/// * `Err(AlgorithmError::CycleDetected)` if a cycle is found
60	/// * `Err(AlgorithmError::ResultCapacityExceeded)` if result buffer is full
61	///
62	/// # Time Complexity
63	/// O(V + E) where V is the number of vertices and E is the number of edges
64	pub fn topological_sort_dfs<'a, G, NI, VT>(	4✔
65	graph: &G,	4✔
66	visited: &mut VT,	4✔
67	sorted_nodes: &'a mut [NI],	4✔
68	) -> Result<&'a [NI], AlgorithmError<NI>>	4✔
69	where	4✔
70	G: Graph<NI>,	4✔
71	NI: NodeIndex,	4✔
72	VT: TriStateVisitedTracker<NI> + ?Sized,	4✔
73	AlgorithmError<NI>: From<G::Error>,	4✔
74	{	4✔
75	visited.reset();	4✔
76	let mut sort_index = 0;	4✔
77
78	// Visit all nodes in the graph
79	for node in graph.iter_nodes()? {	12✔
80	if visited.is_unvisited(&node) {	12✔
81	topological_sort_dfs_visit(graph, node, visited, sorted_nodes, &mut sort_index)?;	5✔
82	}	7✔
83	}
84
85	// Reverse the result since DFS post-order gives reverse topological order
86	let result_slice = &mut sorted_nodes[..sort_index];	3✔
87	result_slice.reverse();	3✔
88		3✔
89	Ok(result_slice)	3✔
90	}	4✔
91
92	#[cfg(test)]
93	mod tests {
94	use super::*;
95	use crate::edgelist::edge_list::EdgeList;
96	use crate::visited::NodeState;
97
98	#[test]
99	fn test_topological_sort_simple() {	1✔
100	// Create a simple DAG: 0 -> 1 -> 2	1✔
101	let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (1, 2)]);	1✔
102	let mut visited = [NodeState::Unvisited; 8];	1✔
103	let mut sorted_nodes = [0usize; 8];	1✔
104		1✔
105	let result =	1✔
106	topological_sort_dfs(&graph, visited.as_mut_slice(), &mut sorted_nodes).unwrap();	1✔
107		1✔
108	assert_eq!(result, &[0, 1, 2]);	1✔
109	}	1✔
110
111	#[test]
112	fn test_topological_sort_complex() {	1✔
113	// Create a more complex DAG: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3	1✔
114	let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (0, 2), (1, 3), (2, 3)]);	1✔
115	let mut visited = [NodeState::Unvisited; 8];	1✔
116	let mut sorted_nodes = [0usize; 8];	1✔
117		1✔
118	let result =	1✔
119	topological_sort_dfs(&graph, visited.as_mut_slice(), &mut sorted_nodes).unwrap();	1✔
120		1✔
121	assert_eq!(result.len(), 4);	1✔
122
123	// Valid topological orderings: [0, 1, 2, 3] or [0, 2, 1, 3]
124	// Both should have 0 first and 3 last
125	assert_eq!(result[0], 0);	1✔
126	assert_eq!(result[result.len() - 1], 3);	1✔
127
128	// Check that all nodes are present
129	assert!(result.contains(&1));	1✔
130	assert!(result.contains(&2));	1✔
131	}	1✔
132
133	#[test]
134	fn test_topological_sort_cycle_detection() {	1✔
135	// Create a graph with a cycle: 0 -> 1 -> 2 -> 0	1✔
136	let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (1, 2), (2, 0)]);	1✔
137	let mut visited = [NodeState::Unvisited; 8];	1✔
138	let mut sorted_nodes = [0usize; 8];	1✔
139		1✔
140	let error = topological_sort_dfs(&graph, visited.as_mut_slice(), &mut sorted_nodes);	1✔
141		1✔
142	assert!(matches!(error, Err(AlgorithmError::CycleDetected)));	1✔
143	}	1✔
144
145	#[test]
146	fn test_topological_sort_disconnected() {	1✔
147	// Create a disconnected graph: 0 -> 1, 2 -> 3 (no connection between pairs)	1✔
148	let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (2, 3)]);	1✔
149	let mut visited = [NodeState::Unvisited; 8];	1✔
150	let mut sorted_nodes = [0usize; 8];	1✔
151		1✔
152	let result =	1✔
153	topological_sort_dfs(&graph, visited.as_mut_slice(), &mut sorted_nodes).unwrap();	1✔
154		1✔
155	assert_eq!(result.len(), 4);	1✔
156
157	// Check relative ordering within connected components
158	let pos_0 = result.iter().position(\|&x\| x == 0).unwrap();	3✔
159	let pos_1 = result.iter().position(\|&x\| x == 1).unwrap();	4✔
160	let pos_2 = result.iter().position(\|&x\| x == 2).unwrap();	1✔
161	let pos_3 = result.iter().position(\|&x\| x == 3).unwrap();	2✔
162		1✔
163	assert!(pos_0 < pos_1); // 0 should come before 1	1✔
164	assert!(pos_2 < pos_3); // 2 should come before 3	1✔
165	}	1✔
166	}

kaidokert / heapless-graphs-rs / 15666368678

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous