15665053732

Committed 15 Jun 2025 04:12PM UTC coverage: 93.713% (+4.5%) from 89.24%

Build # 15665053732

Build Type

Pull #8

github

Committed by

kaidokert

Commit Message

EdgeValue arrays

Pull Request Pull Request #8: No ref graphs

Run Details

3389 of 3461 new or added lines in 26 files covered. (97.92%)

41 existing lines in 7 files now uncovered.

5128 of 5472 relevant lines covered (93.71%)

44.53 hits per line

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

98.44

/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;
    use test_log::test;

    #[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	use test_log::test;
98
99	#[test]	1✔
100	fn test_topological_sort_simple() {
101	// Create a simple DAG: 0 -> 1 -> 2
102	let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (1, 2)]);
103	let mut visited = [NodeState::Unvisited; 8];
104	let mut sorted_nodes = [0usize; 8];
105
106	let result =
107	topological_sort_dfs(&graph, visited.as_mut_slice(), &mut sorted_nodes).unwrap();
108
109	assert_eq!(result, &[0, 1, 2]);
110	}
111
112	#[test]	1✔
113	fn test_topological_sort_complex() {
114	// Create a more complex DAG: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3
115	let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (0, 2), (1, 3), (2, 3)]);
116	let mut visited = [NodeState::Unvisited; 8];
117	let mut sorted_nodes = [0usize; 8];
118
119	let result =
120	topological_sort_dfs(&graph, visited.as_mut_slice(), &mut sorted_nodes).unwrap();
121
122	assert_eq!(result.len(), 4);
123
124	// Valid topological orderings: [0, 1, 2, 3] or [0, 2, 1, 3]
125	// Both should have 0 first and 3 last
126	assert_eq!(result[0], 0);
127	assert_eq!(result[result.len() - 1], 3);
128
129	// Check that all nodes are present
130	assert!(result.contains(&1));
131	assert!(result.contains(&2));
132	}
133
134	#[test]	1✔
135	fn test_topological_sort_cycle_detection() {
136	// Create a graph with a cycle: 0 -> 1 -> 2 -> 0
137	let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (1, 2), (2, 0)]);
138	let mut visited = [NodeState::Unvisited; 8];
139	let mut sorted_nodes = [0usize; 8];
140
141	let error = topological_sort_dfs(&graph, visited.as_mut_slice(), &mut sorted_nodes);
142
143	assert!(matches!(error, Err(AlgorithmError::CycleDetected)));
144	}
145
146	#[test]	1✔
147	fn test_topological_sort_disconnected() {
148	// Create a disconnected graph: 0 -> 1, 2 -> 3 (no connection between pairs)
149	let graph = EdgeList::<8, _, _>::new([(0usize, 1usize), (2, 3)]);
150	let mut visited = [NodeState::Unvisited; 8];
151	let mut sorted_nodes = [0usize; 8];
152
153	let result =
154	topological_sort_dfs(&graph, visited.as_mut_slice(), &mut sorted_nodes).unwrap();
155
156	assert_eq!(result.len(), 4);
157
158	// Check relative ordering within connected components
159	let pos_0 = result.iter().position(\|&x\| x == 0).unwrap();	3✔
160	let pos_1 = result.iter().position(\|&x\| x == 1).unwrap();	4✔
161	let pos_2 = result.iter().position(\|&x\| x == 2).unwrap();	1✔
162	let pos_3 = result.iter().position(\|&x\| x == 3).unwrap();	2✔
163
164	assert!(pos_0 < pos_1); // 0 should come before 1
165	assert!(pos_2 < pos_3); // 2 should come before 3
166	}
167	}

kaidokert / heapless-graphs-rs / 15665053732

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