15667227901

Committed 15 Jun 2025 08:46PM UTC coverage: 94.257% (+5.0%) from 89.24%

Build # 15667227901

Build Type

push

github

Committed by

web-flow

Commit Message

Refactor the library

Huge update with API cleanup and dozens of bugs fixed

Run Details

4115 of 4202 new or added lines in 29 files covered. (97.93%)

44 existing lines in 9 files now uncovered.

5859 of 6216 relevant lines covered (94.26%)

39.93 hits per line

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

98.03

/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
/// ```rust
/// # use heapless_graphs::edgelist::edge_node_list::EdgeNodeList;
/// # use heapless_graphs::algorithms::connected_components;
/// let edges = [(0, 1)];
/// let nodes = [0, 1, 2]; // Explicitly include the isolated node
/// let graph = EdgeNodeList::new(edges, nodes).unwrap();
///
/// let mut visited = [false; 3];
/// let mut components = [(&[0usize][..], 0usize); 3];
/// let mut node_buffer = [0usize; 3];
///
/// let component_count = connected_components(
///     &graph,
///     visited.as_mut_slice(),
///     &mut components,
///     &mut node_buffer
/// ).unwrap();
/// assert_eq!(component_count, 2);
/// ```
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)
        .map_err(|_| AlgorithmError::VisitedTrackerCapacityExceeded)?;

    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)
        .map_err(|_| AlgorithmError::VisitedTrackerCapacityExceeded)?;

    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() {
        let mut dict = Dictionary::<usize, [usize; 2], 5>::new();
        dict.insert(0, [1, 2]).unwrap(); // 0 connects to 1, 2
        dict.insert(1, [0, 2]).unwrap(); // 1 connects to 0, 2
        dict.insert(2, [0, 1]).unwrap(); // 2 connects to 0, 1
        dict.insert(3, [3, 3]).unwrap(); // 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() {
        let mut dict = Dictionary::<usize, [usize; 0], 5>::new();
        dict.insert(0, []).unwrap();
        dict.insert(1, []).unwrap();
        dict.insert(2, []).unwrap();

        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
    }

    #[test]
    fn test_connected_components_edge_node_list_with_isolated_explicit() {
        // 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::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]);
    }
}

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

kaidokert / heapless-graphs-rs / 15667227901

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