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

98.01

/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);

    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() {
        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.mark_visited(node);	17✔
142		17✔
143	if *count >= buffer.len() {	17✔
NEW 144	return Err(AlgorithmError::ResultCapacityExceeded);	×
145	}	17✔
146		17✔
147	buffer[count] = node;	17✔
148	*count += 1;	17✔
149
150	// Recursively visit all unvisited neighbors
151	for neighbor in graph.outgoing_edges(*node)? {	17✔
152	if !visited.is_visited(&neighbor) {	9✔
153	dfs_collect_recursive(graph, &neighbor, visited, buffer, count)?	9✔
NEW 154	}	×
155	}
156
157	Ok(())	17✔
158	}	17✔
159
160	/// Count the number of connected components without collecting the actual components
161	///
162	/// This is a more memory-efficient version that only counts components
163	/// without storing them.
164	pub fn count_connected_components<G, NI, VT>(	5✔
165	graph: &G,	5✔
166	visited: &mut VT,	5✔
167	) -> Result<usize, AlgorithmError<NI>>	5✔
168	where	5✔
169	G: Graph<NI>,	5✔
170	NI: NodeIndex,	5✔
171	VT: VisitedTracker<NI> + ?Sized,	5✔
172	AlgorithmError<NI>: From<G::Error>,	5✔
173	{	5✔
174	let mut component_count = 0;	5✔
175
176	for node in graph.iter_nodes()? {	16✔
177	if !visited.is_visited(&node) {	16✔
178	// Start DFS from this unvisited node
179	dfs_mark_component(graph, &node, visited)?;	8✔
180	component_count += 1;	8✔
181	}	8✔
182	}
183
184	Ok(component_count)	4✔
185	}	5✔
186
187	/// Helper function to mark all nodes in a connected component as visited
188	fn dfs_mark_component<G, NI, VT>(	16✔
189	graph: &G,	16✔
190	start_node: &NI,	16✔
191	visited: &mut VT,	16✔
192	) -> Result<(), AlgorithmError<NI>>	16✔
193	where	16✔
194	G: Graph<NI>,	16✔
195	NI: NodeIndex,	16✔
196	VT: VisitedTracker<NI> + ?Sized,	16✔
197	AlgorithmError<NI>: From<G::Error>,	16✔
198	{	16✔
199	if visited.is_visited(start_node) {	16✔
NEW 200	return Ok(());	×
201	}	16✔
202		16✔
203	visited.mark_visited(start_node);	16✔
204
205	for neighbor in graph.outgoing_edges(*start_node)? {	16✔
206	if !visited.is_visited(&neighbor) {	14✔
207	dfs_mark_component(graph, &neighbor, visited)?;	8✔
208	}	6✔
209	}
210
211	Ok(())	16✔
212	}	16✔
213
214	#[cfg(test)]
215	mod tests {
216	use super::*;
217	use crate::adjacency_list::map_adjacency_list::MapAdjacencyList;
218	use crate::containers::maps::{staticdict::Dictionary, MapTrait};
219	use crate::edgelist::edge_list::EdgeList;
220	use crate::edgelist::edge_node_list::EdgeNodeList;
221
222	#[test]
223	fn test_connected_components_edge_list() {	1✔
224	// Create a graph with 3 connected components:	1✔
225	// Component 1: 0-1-2	1✔
226	// Component 2: 3-4	1✔
227	// Component 3: 5 (isolated)	1✔
228	let edges = [(0, 1), (1, 2), (3, 4)];	1✔
229	let graph = EdgeList::<10, usize, _>::new(edges);	1✔
230		1✔
231	let mut visited = [false; 10];	1✔
232	let mut components: [(&[usize], usize); 5] = [(&[], 0); 5];	1✔
233	let mut node_buffer = [0usize; 10];	1✔
234		1✔
235	let component_count = connected_components(	1✔
236	&graph,	1✔
237	visited.as_mut_slice(),	1✔
238	&mut components,	1✔
239	&mut node_buffer,	1✔
240	)	1✔
241	.unwrap();	1✔
242		1✔
243	// Should find 2 components	1✔
244	assert_eq!(component_count, 2);	1✔
245
246	// Check component sizes
247	assert_eq!(components[0].0.len(), 3); // 0-1-2	1✔
248	assert_eq!(components[1].0.len(), 2); // 3-4	1✔
249
250	// Verify all nodes are accounted for
251	let mut all_nodes = [0usize; 10];	1✔
252	let mut total_nodes = 0;	1✔
253	for i in 0..component_count {	2✔
254	for &node in components[i].0 {	5✔
255	all_nodes[total_nodes] = node;	5✔
256	total_nodes += 1;	5✔
257	}	5✔
258	}
259	all_nodes[..total_nodes].sort();	1✔
260	assert_eq!(&all_nodes[..total_nodes], &[0, 1, 2, 3, 4]);	1✔
261	}	1✔
262
263	#[test]
264	fn test_count_connected_components() {	1✔
265	let edges = [(0, 1), (1, 2), (3, 4)];	1✔
266	let graph = EdgeList::<10, usize, _>::new(edges);	1✔
267		1✔
268	let mut visited = [false; 10];	1✔
269	let count = count_connected_components(&graph, visited.as_mut_slice()).unwrap();	1✔
270		1✔
271	assert_eq!(count, 2); // Two components: {0,1,2}, {3,4}	1✔
272	}	1✔
273
274	#[test]
275	fn test_connected_components_single_component() {	1✔
276	// All nodes connected: 0-1-2-3	1✔
277	let edges = [(0, 1), (1, 2), (2, 3)];	1✔
278	let graph = EdgeList::<10, usize, _>::new(edges);	1✔
279		1✔
280	let mut visited = [false; 10];	1✔
281	let count = count_connected_components(&graph, visited.as_mut_slice()).unwrap();	1✔
282		1✔
283	assert_eq!(count, 1); // One component containing all nodes	1✔
284	}	1✔
285
286	#[test]
287	fn test_connected_components_map_adjacency_list() {	1✔
288	let mut dict = Dictionary::<usize, [usize; 2], 5>::new();	1✔
289	dict.insert(0, [1, 2]).unwrap(); // 0 connects to 1, 2	1✔
290	dict.insert(1, [0, 2]).unwrap(); // 1 connects to 0, 2	1✔
291	dict.insert(2, [0, 1]).unwrap(); // 2 connects to 0, 1	1✔
292	dict.insert(3, [3, 3]).unwrap(); // 3 is isolated (self-loop)	1✔
293		1✔
294	let graph = MapAdjacencyList::new_unchecked(dict);	1✔
295		1✔
296	let mut visited = [false; 10];	1✔
297	let count = count_connected_components(&graph, visited.as_mut_slice()).unwrap();	1✔
298		1✔
299	assert_eq!(count, 2); // Two components: {0,1,2} and {3}	1✔
300	}	1✔
301
302	#[test]
303	fn test_connected_components_empty_graph() {	1✔
304	let edges: [(usize, usize); 0] = [];	1✔
305	let graph = EdgeList::<5, usize, _>::new(edges);	1✔
306		1✔
307	let mut visited = [false; 5];	1✔
308		1✔
309	// Empty EdgeList will return an error when trying to iterate nodes	1✔
310	// because EdgesToNodesIterator requires at least one edge	1✔
311	let result = count_connected_components(&graph, visited.as_mut_slice());	1✔
312	assert!(result.is_err()); // Should error on empty graph	1✔
313	}	1✔
314
315	#[test]
316	fn test_connected_components_edge_node_list_with_isolated() {	1✔
317	// EdgeNodeList allows us to define isolated nodes explicitly	1✔
318	// Create a graph with 3 connected components:	1✔
319	// Component 1: 0-1-2	1✔
320	// Component 2: 3-4	1✔
321	// Component 3: 5 (isolated)	1✔
322	let edges = [(0, 1), (1, 2), (3, 4)];	1✔
323	let nodes = [0, 1, 2, 3, 4, 5]; // Node 5 is isolated	1✔
324	let graph = EdgeNodeList::<usize, _, _>::new(edges, nodes).unwrap();	1✔
325		1✔
326	let mut visited = [false; 10];	1✔
327	let mut components: [(&[usize], usize); 5] = [(&[], 0); 5];	1✔
328	let mut node_buffer = [0usize; 10];	1✔
329		1✔
330	let component_count = connected_components(	1✔
331	&graph,	1✔
332	visited.as_mut_slice(),	1✔
333	&mut components,	1✔
334	&mut node_buffer,	1✔
335	)	1✔
336	.unwrap();	1✔
337		1✔
338	// Should find 3 components including the isolated node	1✔
339	assert_eq!(component_count, 3);	1✔
340
341	// Check component sizes
342	let mut sizes = [0; 3];	1✔
343	for i in 0..component_count {	3✔
344	sizes[i] = components[i].0.len();	3✔
345	}	3✔
346	sizes.sort(); // Sort to make assertion order-independent	1✔
347	assert_eq!(sizes, [1, 2, 3]); // One isolated (1), one pair (2), one triple (3)	1✔
348
349	// Verify all nodes are accounted for
350	let mut all_nodes = [0usize; 10];	1✔
351	let mut total_nodes = 0;	1✔
352	for i in 0..component_count {	3✔
353	for &node in components[i].0 {	6✔
354	all_nodes[total_nodes] = node;	6✔
355	total_nodes += 1;	6✔
356	}	6✔
357	}
358	all_nodes[..total_nodes].sort();	1✔
359	assert_eq!(&all_nodes[..total_nodes], &[0, 1, 2, 3, 4, 5]);	1✔
360	}	1✔
361
362	#[test]
363	fn test_connected_components_all_isolated() {	1✔
364	let mut dict = Dictionary::<usize, [usize; 0], 5>::new();	1✔
365	dict.insert(0, []).unwrap();	1✔
366	dict.insert(1, []).unwrap();	1✔
367	dict.insert(2, []).unwrap();	1✔
368		1✔
369	let graph = MapAdjacencyList::new_unchecked(dict);	1✔
370		1✔
371	let mut visited = [false; 10];	1✔
372	let count = count_connected_components(&graph, visited.as_mut_slice()).unwrap();	1✔
373		1✔
374	assert_eq!(count, 3); // Three isolated nodes = three components	1✔
375	}	1✔
376
377	#[test]
378	fn test_connected_components_edge_node_list_with_isolated_explicit() {	1✔
379	// EdgeNodeList allows us to define isolated nodes explicitly	1✔
380	// Create a graph with 3 connected components:	1✔
381	// Component 1: 0-1-2	1✔
382	// Component 2: 3-4	1✔
383	// Component 3: 5 (isolated)	1✔
384	let edges = [(0, 1), (1, 2), (3, 4)];	1✔
385	let nodes = [0, 1, 2, 3, 4, 5]; // Node 5 is isolated	1✔
386	let graph = EdgeNodeList::new(edges, nodes).unwrap();	1✔
387		1✔
388	let mut visited = [false; 10];	1✔
389	let mut components: [(&[usize], usize); 5] = [(&[], 0); 5];	1✔
390	let mut node_buffer = [0usize; 10];	1✔
391		1✔
392	let component_count = connected_components(	1✔
393	&graph,	1✔
394	visited.as_mut_slice(),	1✔
395	&mut components,	1✔
396	&mut node_buffer,	1✔
397	)	1✔
398	.unwrap();	1✔
399		1✔
400	// Should find 3 components including the isolated node	1✔
401	assert_eq!(component_count, 3);	1✔
402
403	// Check component sizes
404	let mut sizes = [0; 3];	1✔
405	for i in 0..component_count {	3✔
406	sizes[i] = components[i].0.len();	3✔
407	}	3✔
408	sizes.sort(); // Sort to make assertion order-independent	1✔
409	assert_eq!(sizes, [1, 2, 3]); // One isolated (1), one pair (2), one triple (3)	1✔
410
411	// Verify all nodes are accounted for
412	let mut all_nodes = [0usize; 10];	1✔
413	let mut total_nodes = 0;	1✔
414	for i in 0..component_count {	3✔
415	for &node in components[i].0 {	6✔
416	all_nodes[total_nodes] = node;	6✔
417	total_nodes += 1;	6✔
418	}	6✔
419	}
420	all_nodes[..total_nodes].sort();	1✔
421	assert_eq!(&all_nodes[..total_nodes], &[0, 1, 2, 3, 4, 5]);	1✔
422	}	1✔
423	}

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