15665122570

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

Build # 15665122570

Build Type

Pull #8

github

Committed by

web-flow

Commit Message

Move heapless src/algorithms/traversal.rs

Co-authored-by: coderabbitai[bot] <136622811+coderabbitai[bot]@users.noreply.github.com>

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

97.73

/src/algorithms/connected_components.rs

// SPDX-License-Identifier: Apache-2.0

//! Connected Components Algorithm
//!
//! Finds all connected components in an undirected graph using depth-first search.
//! A connected component is a maximal set of vertices such that there is a path
//! between every pair of vertices.

use super::AlgorithmError;

use crate::graph::{Graph, NodeIndex};
use crate::visited::VisitedTracker;

/// Find all connected components in an undirected graph
///
/// This function identifies all connected components in the graph by performing
/// DFS from each unvisited node. Each connected component is collected into
/// the provided buffer.
///
/// # Arguments
/// * `graph` - The graph to analyze
/// * `visited` - Tracker for visited nodes
/// * `components` - Buffer to store the connected components as (slice, size) tuples
/// * `node_buffer` - Temporary buffer for collecting nodes in each component
///
/// # Returns
/// The number of connected components found, or an error if buffers are too small
///
/// # Example
/// ```ignore
/// let mut visited = [false; 10];
/// let mut components = [(&[0usize][..], 0usize); 5]; // Up to 5 components with sizes
/// let mut node_buffer = [0usize; 10];
///
/// let component_count = connected_components(
///     &graph,
///     visited.as_mut_slice(),
///     &mut components,
///     &mut node_buffer
/// )?;
/// ```
pub fn connected_components<'a, G, NI, VT>(
    graph: &G,
    visited: &mut VT,
    components: &mut [(&'a [NI], usize)],
    node_buffer: &'a mut [NI],
) -> Result<usize, AlgorithmError<NI>>
where
    G: Graph<NI>,
    NI: NodeIndex,
    VT: VisitedTracker<NI> + ?Sized,
    AlgorithmError<NI>: From<G::Error>,
{
    let mut component_count = 0;
    let mut buffer_offset = 0;

    // First pass: collect all components and store sizes
    for node in graph.iter_nodes()? {
        if !visited.is_visited(&node) {
            if component_count >= components.len() {
                return Err(AlgorithmError::ResultCapacityExceeded);
            }

            // Collect all nodes in this connected component
            let remaining_buffer = &mut node_buffer[buffer_offset..];
            let component_size = dfs_component_collection(graph, &node, visited, remaining_buffer)?;

            if buffer_offset + component_size > node_buffer.len() {
                return Err(AlgorithmError::ResultCapacityExceeded);
            }

            // Store size temporarily (slice will be filled in second pass)
            components[component_count] = (&[], component_size);
            buffer_offset += component_size;
            component_count += 1;
        }
    }

    // Second pass: populate component slices
    let mut current_offset = 0;
    for component in components.iter_mut().take(component_count) {
        let component_size = component.1;
        let component_slice = &node_buffer[current_offset..current_offset + component_size];
        *component = (component_slice, component_size);
        current_offset += component_size;
    }

    Ok(component_count)
}

/// Helper function to collect all nodes in a connected component using DFS
///
/// Performs depth-first search starting from the given node and collects
/// all reachable nodes into the provided buffer.
fn dfs_component_collection<G, NI, VT>(
    graph: &G,
    start_node: &NI,
    visited: &mut VT,
    buffer: &mut [NI],
) -> Result<usize, AlgorithmError<NI>>
where
    G: Graph<NI>,
    NI: NodeIndex,
    VT: VisitedTracker<NI> + ?Sized,
    AlgorithmError<NI>: From<G::Error>,
{
    let mut count = 0;

    // Use a simple recursive DFS to collect nodes
    dfs_collect_recursive(graph, start_node, visited, buffer, &mut count)?;

    Ok(count)
}

/// Recursive helper for DFS node collection
fn dfs_collect_recursive<G, NI, VT>(
    graph: &G,
    node: &NI,
    visited: &mut VT,
    buffer: &mut [NI],
    count: &mut usize,
) -> Result<(), AlgorithmError<NI>>
where
    G: Graph<NI>,
    NI: NodeIndex,
    VT: VisitedTracker<NI> + ?Sized,
    AlgorithmError<NI>: From<G::Error>,
{
    if visited.is_visited(node) {
        return Ok(());
    }

    // Mark as visited and add to buffer
    visited.mark_visited(node);

    if *count >= buffer.len() {
        return Err(AlgorithmError::ResultCapacityExceeded);
    }

    buffer[*count] = *node;
    *count += 1;

    // Recursively visit all unvisited neighbors
    for neighbor in graph.outgoing_edges(*node)? {
        if !visited.is_visited(&neighbor) {
            dfs_collect_recursive(graph, &neighbor, visited, buffer, count)?
        }
    }

    Ok(())
}

/// Count the number of connected components without collecting the actual components
///
/// This is a more memory-efficient version that only counts components
/// without storing them.
pub fn count_connected_components<G, NI, VT>(
    graph: &G,
    visited: &mut VT,
) -> Result<usize, AlgorithmError<NI>>
where
    G: Graph<NI>,
    NI: NodeIndex,
    VT: VisitedTracker<NI> + ?Sized,
    AlgorithmError<NI>: From<G::Error>,
{
    let mut component_count = 0;

    for node in graph.iter_nodes()? {
        if !visited.is_visited(&node) {
            // Start DFS from this unvisited node
            dfs_mark_component(graph, &node, visited)?;
            component_count += 1;
        }
    }

    Ok(component_count)
}

/// Helper function to mark all nodes in a connected component as visited
fn dfs_mark_component<G, NI, VT>(
    graph: &G,
    start_node: &NI,
    visited: &mut VT,
) -> Result<(), AlgorithmError<NI>>
where
    G: Graph<NI>,
    NI: NodeIndex,
    VT: VisitedTracker<NI> + ?Sized,
    AlgorithmError<NI>: From<G::Error>,
{
    if visited.is_visited(start_node) {
        return Ok(());
    }

    visited.mark_visited(start_node);

    for neighbor in graph.outgoing_edges(*start_node)? {
        if !visited.is_visited(&neighbor) {
            dfs_mark_component(graph, &neighbor, visited)?;
        }
    }

    Ok(())
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::adjacency_list::map_adjacency_list::MapAdjacencyList;
    use crate::containers::maps::{staticdict::Dictionary, MapTrait};
    use crate::edgelist::edge_list::EdgeList;
    use crate::edgelist::edge_node_list::EdgeNodeList;

    #[test]
    fn test_connected_components_edge_list() {
        // Create a graph with 3 connected components:
        // Component 1: 0-1-2
        // Component 2: 3-4
        // Component 3: 5 (isolated)
        let edges = [(0, 1), (1, 2), (3, 4)];
        let graph = EdgeList::<10, usize, _>::new(edges);

        let mut visited = [false; 10];
        let mut components: [(&[usize], usize); 5] = [(&[], 0); 5];
        let mut node_buffer = [0usize; 10];

        let component_count = connected_components(
            &graph,
            visited.as_mut_slice(),
            &mut components,
            &mut node_buffer,
        )
        .unwrap();

        // Should find 2 components
        assert_eq!(component_count, 2);

        // Check component sizes
        assert_eq!(components[0].0.len(), 3); // 0-1-2
        assert_eq!(components[1].0.len(), 2); // 3-4

        // Verify all nodes are accounted for
        let mut all_nodes = [0usize; 10];
        let mut total_nodes = 0;
        for i in 0..component_count {
            for &node in components[i].0 {
                all_nodes[total_nodes] = node;
                total_nodes += 1;
            }
        }
        all_nodes[..total_nodes].sort();
        assert_eq!(&all_nodes[..total_nodes], &[0, 1, 2, 3, 4]);
    }

    #[test]
    fn test_count_connected_components() {
        let edges = [(0, 1), (1, 2), (3, 4)];
        let graph = EdgeList::<10, usize, _>::new(edges);

        let mut visited = [false; 10];
        let count = count_connected_components(&graph, visited.as_mut_slice()).unwrap();

        assert_eq!(count, 2); // Two components: {0,1,2}, {3,4}
    }

    #[test]
    fn test_connected_components_single_component() {
        // All nodes connected: 0-1-2-3
        let edges = [(0, 1), (1, 2), (2, 3)];
        let graph = EdgeList::<10, usize, _>::new(edges);

        let mut visited = [false; 10];
        let count = count_connected_components(&graph, visited.as_mut_slice()).unwrap();

        assert_eq!(count, 1); // One component containing all nodes
    }

    #[test]
    fn test_connected_components_map_adjacency_list() {
        // Test with different graph type
        let mut dict = Dictionary::<usize, [usize; 2], 5>::new();
        dict.insert(0, [1, 2]); // 0 connects to 1, 2
        dict.insert(1, [0, 2]); // 1 connects to 0, 2
        dict.insert(2, [0, 1]); // 2 connects to 0, 1
        dict.insert(3, [3, 3]); // 3 is isolated (self-loop)

        let graph = MapAdjacencyList::new_unchecked(dict);

        let mut visited = [false; 10];
        let count = count_connected_components(&graph, visited.as_mut_slice()).unwrap();

        assert_eq!(count, 2); // Two components: {0,1,2} and {3}
    }

    #[test]
    fn test_connected_components_empty_graph() {
        let edges: [(usize, usize); 0] = [];
        let graph = EdgeList::<5, usize, _>::new(edges);

        let mut visited = [false; 5];

        // Empty EdgeList will return an error when trying to iterate nodes
        // because EdgesToNodesIterator requires at least one edge
        let result = count_connected_components(&graph, visited.as_mut_slice());
        assert!(result.is_err()); // Should error on empty graph
    }

    #[test]
    fn test_connected_components_edge_node_list_with_isolated() {
        // EdgeNodeList allows us to define isolated nodes explicitly
        // Create a graph with 3 connected components:
        // Component 1: 0-1-2
        // Component 2: 3-4
        // Component 3: 5 (isolated)
        let edges = [(0, 1), (1, 2), (3, 4)];
        let nodes = [0, 1, 2, 3, 4, 5]; // Node 5 is isolated
        let graph = EdgeNodeList::<usize, _, _>::new(edges, nodes).unwrap();

        let mut visited = [false; 10];
        let mut components: [(&[usize], usize); 5] = [(&[], 0); 5];
        let mut node_buffer = [0usize; 10];

        let component_count = connected_components(
            &graph,
            visited.as_mut_slice(),
            &mut components,
            &mut node_buffer,
        )
        .unwrap();

        // Should find 3 components including the isolated node
        assert_eq!(component_count, 3);

        // Check component sizes
        let mut sizes = [0; 3];
        for i in 0..component_count {
            sizes[i] = components[i].0.len();
        }
        sizes.sort(); // Sort to make assertion order-independent
        assert_eq!(sizes, [1, 2, 3]); // One isolated (1), one pair (2), one triple (3)

        // Verify all nodes are accounted for
        let mut all_nodes = [0usize; 10];
        let mut total_nodes = 0;
        for i in 0..component_count {
            for &node in components[i].0 {
                all_nodes[total_nodes] = node;
                total_nodes += 1;
            }
        }
        all_nodes[..total_nodes].sort();
        assert_eq!(&all_nodes[..total_nodes], &[0, 1, 2, 3, 4, 5]);
    }

    #[test]
    fn test_connected_components_all_isolated() {
        // Graph with nodes but no edges - each node is its own component
        let mut dict = Dictionary::<usize, [usize; 0], 5>::new();
        dict.insert(0, []);
        dict.insert(1, []);
        dict.insert(2, []);

        let graph = MapAdjacencyList::new_unchecked(dict);

        let mut visited = [false; 10];
        let count = count_connected_components(&graph, visited.as_mut_slice()).unwrap();

        assert_eq!(count, 3); // Three isolated nodes = three components
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2
3	//! Connected Components Algorithm
4	//!
5	//! Finds all connected components in an undirected graph using depth-first search.
6	//! A connected component is a maximal set of vertices such that there is a path
7	//! between every pair of vertices.
8
9	use super::AlgorithmError;
10
11	use crate::graph::{Graph, NodeIndex};
12	use crate::visited::VisitedTracker;
13
14	/// Find all connected components in an undirected graph
15	///
16	/// This function identifies all connected components in the graph by performing
17	/// DFS from each unvisited node. Each connected component is collected into
18	/// the provided buffer.
19	///
20	/// # Arguments
21	/// * `graph` - The graph to analyze
22	/// * `visited` - Tracker for visited nodes
23	/// * `components` - Buffer to store the connected components as (slice, size) tuples
24	/// * `node_buffer` - Temporary buffer for collecting nodes in each component
25	///
26	/// # Returns
27	/// The number of connected components found, or an error if buffers are too small
28	///
29	/// # Example
30	/// ```ignore
31	/// let mut visited = [false; 10];
32	/// let mut components = [(&[0usize][..], 0usize); 5]; // Up to 5 components with sizes
33	/// let mut node_buffer = [0usize; 10];
34	///
35	/// let component_count = connected_components(
36	/// &graph,
37	/// visited.as_mut_slice(),
38	/// &mut components,
39	/// &mut node_buffer
40	/// )?;
41	/// ```
42	pub fn connected_components<'a, G, NI, VT>(	2✔
43	graph: &G,	2✔
44	visited: &mut VT,	2✔
45	components: &mut [(&'a [NI], usize)],	2✔
46	node_buffer: &'a mut [NI],	2✔
47	) -> Result<usize, AlgorithmError<NI>>	2✔
48	where	2✔
49	G: Graph<NI>,	2✔
50	NI: NodeIndex,	2✔
51	VT: VisitedTracker<NI> + ?Sized,	2✔
52	AlgorithmError<NI>: From<G::Error>,	2✔
53	{	2✔
54	let mut component_count = 0;	2✔
55	let mut buffer_offset = 0;	2✔
56
57	// First pass: collect all components and store sizes
58	for node in graph.iter_nodes()? {	11✔
59	if !visited.is_visited(&node) {	11✔
60	if component_count >= components.len() {	5✔
NEW 61	return Err(AlgorithmError::ResultCapacityExceeded);	×
62	}	5✔
63		5✔
64	// Collect all nodes in this connected component	5✔
65	let remaining_buffer = &mut node_buffer[buffer_offset..];	5✔
66	let component_size = dfs_component_collection(graph, &node, visited, remaining_buffer)?;	5✔
67
68	if buffer_offset + component_size > node_buffer.len() {	5✔
NEW 69	return Err(AlgorithmError::ResultCapacityExceeded);	×
70	}	5✔
71		5✔
72	// Store size temporarily (slice will be filled in second pass)	5✔
73	components[component_count] = (&[], component_size);	5✔
74	buffer_offset += component_size;	5✔
75	component_count += 1;	5✔
76	}	6✔
77	}
78
79	// Second pass: populate component slices
80	let mut current_offset = 0;	2✔
81	for component in components.iter_mut().take(component_count) {	5✔
82	let component_size = component.1;	5✔
83	let component_slice = &node_buffer[current_offset..current_offset + component_size];	5✔
84	*component = (component_slice, component_size);	5✔
85	current_offset += component_size;	5✔
86	}	5✔
87
88	Ok(component_count)	2✔
89	}	2✔
90
91	/// Helper function to collect all nodes in a connected component using DFS
92	///
93	/// Performs depth-first search starting from the given node and collects
94	/// all reachable nodes into the provided buffer.
95	fn dfs_component_collection<G, NI, VT>(	5✔
96	graph: &G,	5✔
97	start_node: &NI,	5✔
98	visited: &mut VT,	5✔
99	buffer: &mut [NI],	5✔
100	) -> Result<usize, AlgorithmError<NI>>	5✔
101	where	5✔
102	G: Graph<NI>,	5✔
103	NI: NodeIndex,	5✔
104	VT: VisitedTracker<NI> + ?Sized,	5✔
105	AlgorithmError<NI>: From<G::Error>,	5✔
106	{	5✔
107	let mut count = 0;	5✔
108		5✔
109	// Use a simple recursive DFS to collect nodes	5✔
110	dfs_collect_recursive(graph, start_node, visited, buffer, &mut count)?;	5✔
111
112	Ok(count)	5✔
113	}	5✔
114
115	/// Recursive helper for DFS node collection
116	fn dfs_collect_recursive<G, NI, VT>(	11✔
117	graph: &G,	11✔
118	node: &NI,	11✔
119	visited: &mut VT,	11✔
120	buffer: &mut [NI],	11✔
121	count: &mut usize,	11✔
122	) -> Result<(), AlgorithmError<NI>>	11✔
123	where	11✔
124	G: Graph<NI>,	11✔
125	NI: NodeIndex,	11✔
126	VT: VisitedTracker<NI> + ?Sized,	11✔
127	AlgorithmError<NI>: From<G::Error>,	11✔
128	{	11✔
129	if visited.is_visited(node) {	11✔
NEW 130	return Ok(());	×
131	}	11✔
132		11✔
133	// Mark as visited and add to buffer	11✔
134	visited.mark_visited(node);	11✔
135		11✔
136	if *count >= buffer.len() {	11✔
NEW 137	return Err(AlgorithmError::ResultCapacityExceeded);	×
138	}	11✔
139		11✔
140	buffer[count] = node;	11✔
141	*count += 1;	11✔
142
143	// Recursively visit all unvisited neighbors
144	for neighbor in graph.outgoing_edges(*node)? {	11✔
145	if !visited.is_visited(&neighbor) {	6✔
146	dfs_collect_recursive(graph, &neighbor, visited, buffer, count)?	6✔
NEW 147	}	×
148	}
149
150	Ok(())	11✔
151	}	11✔
152
153	/// Count the number of connected components without collecting the actual components
154	///
155	/// This is a more memory-efficient version that only counts components
156	/// without storing them.
157	pub fn count_connected_components<G, NI, VT>(	5✔
158	graph: &G,	5✔
159	visited: &mut VT,	5✔
160	) -> Result<usize, AlgorithmError<NI>>	5✔
161	where	5✔
162	G: Graph<NI>,	5✔
163	NI: NodeIndex,	5✔
164	VT: VisitedTracker<NI> + ?Sized,	5✔
165	AlgorithmError<NI>: From<G::Error>,	5✔
166	{	5✔
167	let mut component_count = 0;	5✔
168
169	for node in graph.iter_nodes()? {	16✔
170	if !visited.is_visited(&node) {	16✔
171	// Start DFS from this unvisited node
172	dfs_mark_component(graph, &node, visited)?;	8✔
173	component_count += 1;	8✔
174	}	8✔
175	}
176
177	Ok(component_count)	4✔
178	}	5✔
179
180	/// Helper function to mark all nodes in a connected component as visited
181	fn dfs_mark_component<G, NI, VT>(	16✔
182	graph: &G,	16✔
183	start_node: &NI,	16✔
184	visited: &mut VT,	16✔
185	) -> Result<(), AlgorithmError<NI>>	16✔
186	where	16✔
187	G: Graph<NI>,	16✔
188	NI: NodeIndex,	16✔
189	VT: VisitedTracker<NI> + ?Sized,	16✔
190	AlgorithmError<NI>: From<G::Error>,	16✔
191	{	16✔
192	if visited.is_visited(start_node) {	16✔
NEW 193	return Ok(());	×
194	}	16✔
195		16✔
196	visited.mark_visited(start_node);	16✔
197
198	for neighbor in graph.outgoing_edges(*start_node)? {	16✔
199	if !visited.is_visited(&neighbor) {	14✔
200	dfs_mark_component(graph, &neighbor, visited)?;	8✔
201	}	6✔
202	}
203
204	Ok(())	16✔
205	}	16✔
206
207	#[cfg(test)]
208	mod tests {
209	use super::*;
210	use crate::adjacency_list::map_adjacency_list::MapAdjacencyList;
211	use crate::containers::maps::{staticdict::Dictionary, MapTrait};
212	use crate::edgelist::edge_list::EdgeList;
213	use crate::edgelist::edge_node_list::EdgeNodeList;
214
215	#[test]
216	fn test_connected_components_edge_list() {	1✔
217	// Create a graph with 3 connected components:	1✔
218	// Component 1: 0-1-2	1✔
219	// Component 2: 3-4	1✔
220	// Component 3: 5 (isolated)	1✔
221	let edges = [(0, 1), (1, 2), (3, 4)];	1✔
222	let graph = EdgeList::<10, usize, _>::new(edges);	1✔
223		1✔
224	let mut visited = [false; 10];	1✔
225	let mut components: [(&[usize], usize); 5] = [(&[], 0); 5];	1✔
226	let mut node_buffer = [0usize; 10];	1✔
227		1✔
228	let component_count = connected_components(	1✔
229	&graph,	1✔
230	visited.as_mut_slice(),	1✔
231	&mut components,	1✔
232	&mut node_buffer,	1✔
233	)	1✔
234	.unwrap();	1✔
235		1✔
236	// Should find 2 components	1✔
237	assert_eq!(component_count, 2);	1✔
238
239	// Check component sizes
240	assert_eq!(components[0].0.len(), 3); // 0-1-2	1✔
241	assert_eq!(components[1].0.len(), 2); // 3-4	1✔
242
243	// Verify all nodes are accounted for
244	let mut all_nodes = [0usize; 10];	1✔
245	let mut total_nodes = 0;	1✔
246	for i in 0..component_count {	2✔
247	for &node in components[i].0 {	5✔
248	all_nodes[total_nodes] = node;	5✔
249	total_nodes += 1;	5✔
250	}	5✔
251	}
252	all_nodes[..total_nodes].sort();	1✔
253	assert_eq!(&all_nodes[..total_nodes], &[0, 1, 2, 3, 4]);	1✔
254	}	1✔
255
256	#[test]
257	fn test_count_connected_components() {	1✔
258	let edges = [(0, 1), (1, 2), (3, 4)];	1✔
259	let graph = EdgeList::<10, usize, _>::new(edges);	1✔
260		1✔
261	let mut visited = [false; 10];	1✔
262	let count = count_connected_components(&graph, visited.as_mut_slice()).unwrap();	1✔
263		1✔
264	assert_eq!(count, 2); // Two components: {0,1,2}, {3,4}	1✔
265	}	1✔
266
267	#[test]
268	fn test_connected_components_single_component() {	1✔
269	// All nodes connected: 0-1-2-3	1✔
270	let edges = [(0, 1), (1, 2), (2, 3)];	1✔
271	let graph = EdgeList::<10, usize, _>::new(edges);	1✔
272		1✔
273	let mut visited = [false; 10];	1✔
274	let count = count_connected_components(&graph, visited.as_mut_slice()).unwrap();	1✔
275		1✔
276	assert_eq!(count, 1); // One component containing all nodes	1✔
277	}	1✔
278
279	#[test]
280	fn test_connected_components_map_adjacency_list() {	1✔
281	// Test with different graph type	1✔
282	let mut dict = Dictionary::<usize, [usize; 2], 5>::new();	1✔
283	dict.insert(0, [1, 2]); // 0 connects to 1, 2	1✔
284	dict.insert(1, [0, 2]); // 1 connects to 0, 2	1✔
285	dict.insert(2, [0, 1]); // 2 connects to 0, 1	1✔
286	dict.insert(3, [3, 3]); // 3 is isolated (self-loop)	1✔
287		1✔
288	let graph = MapAdjacencyList::new_unchecked(dict);	1✔
289		1✔
290	let mut visited = [false; 10];	1✔
291	let count = count_connected_components(&graph, visited.as_mut_slice()).unwrap();	1✔
292		1✔
293	assert_eq!(count, 2); // Two components: {0,1,2} and {3}	1✔
294	}	1✔
295
296	#[test]
297	fn test_connected_components_empty_graph() {	1✔
298	let edges: [(usize, usize); 0] = [];	1✔
299	let graph = EdgeList::<5, usize, _>::new(edges);	1✔
300		1✔
301	let mut visited = [false; 5];	1✔
302		1✔
303	// Empty EdgeList will return an error when trying to iterate nodes	1✔
304	// because EdgesToNodesIterator requires at least one edge	1✔
305	let result = count_connected_components(&graph, visited.as_mut_slice());	1✔
306	assert!(result.is_err()); // Should error on empty graph	1✔
307	}	1✔
308
309	#[test]
310	fn test_connected_components_edge_node_list_with_isolated() {	1✔
311	// EdgeNodeList allows us to define isolated nodes explicitly	1✔
312	// Create a graph with 3 connected components:	1✔
313	// Component 1: 0-1-2	1✔
314	// Component 2: 3-4	1✔
315	// Component 3: 5 (isolated)	1✔
316	let edges = [(0, 1), (1, 2), (3, 4)];	1✔
317	let nodes = [0, 1, 2, 3, 4, 5]; // Node 5 is isolated	1✔
318	let graph = EdgeNodeList::<usize, _, _>::new(edges, nodes).unwrap();	1✔
319		1✔
320	let mut visited = [false; 10];	1✔
321	let mut components: [(&[usize], usize); 5] = [(&[], 0); 5];	1✔
322	let mut node_buffer = [0usize; 10];	1✔
323		1✔
324	let component_count = connected_components(	1✔
325	&graph,	1✔
326	visited.as_mut_slice(),	1✔
327	&mut components,	1✔
328	&mut node_buffer,	1✔
329	)	1✔
330	.unwrap();	1✔
331		1✔
332	// Should find 3 components including the isolated node	1✔
333	assert_eq!(component_count, 3);	1✔
334
335	// Check component sizes
336	let mut sizes = [0; 3];	1✔
337	for i in 0..component_count {	3✔
338	sizes[i] = components[i].0.len();	3✔
339	}	3✔
340	sizes.sort(); // Sort to make assertion order-independent	1✔
341	assert_eq!(sizes, [1, 2, 3]); // One isolated (1), one pair (2), one triple (3)	1✔
342
343	// Verify all nodes are accounted for
344	let mut all_nodes = [0usize; 10];	1✔
345	let mut total_nodes = 0;	1✔
346	for i in 0..component_count {	3✔
347	for &node in components[i].0 {	6✔
348	all_nodes[total_nodes] = node;	6✔
349	total_nodes += 1;	6✔
350	}	6✔
351	}
352	all_nodes[..total_nodes].sort();	1✔
353	assert_eq!(&all_nodes[..total_nodes], &[0, 1, 2, 3, 4, 5]);	1✔
354	}	1✔
355
356	#[test]
357	fn test_connected_components_all_isolated() {	1✔
358	// Graph with nodes but no edges - each node is its own component	1✔
359	let mut dict = Dictionary::<usize, [usize; 0], 5>::new();	1✔
360	dict.insert(0, []);	1✔
361	dict.insert(1, []);	1✔
362	dict.insert(2, []);	1✔
363		1✔
364	let graph = MapAdjacencyList::new_unchecked(dict);	1✔
365		1✔
366	let mut visited = [false; 10];	1✔
367	let count = count_connected_components(&graph, visited.as_mut_slice()).unwrap();	1✔
368		1✔
369	assert_eq!(count, 3); // Three isolated nodes = three components	1✔
370	}	1✔
371	}

kaidokert / heapless-graphs-rs / 15665122570

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