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

92.11

/src/algorithms/dijkstra.rs

// SPDX-License-Identifier: Apache-2.0
//! Dijkstra algorithm for finding shortest paths

use super::ContainerResultExt;

use crate::containers::maps::MapTrait;
use crate::graph::{GraphWithEdgeValues, NodeIndex};

use super::AlgorithmError;

/// Dijkstra algorithm to find shortest path between nodes
///
/// Calculates the shortest path from a start node to all other nodes in the graph,
/// does not handle negative edge weights.
///
/// # Arguments
/// * `graph` - Graph implementing GraphWithEdgeValues
/// * `source` - Source node to find shortest paths from
/// * `visited` - Map to track which nodes have been processed
/// * `distance_map` - Map to store distances (None = infinite/unreachable, Some(v) = distance v)
///
/// # Returns
/// * `Ok(M)` populated distance map if shortest paths computed successfully
/// * `Err(AlgorithmError::GraphError(_))` for graph access errors
pub fn dijkstra<G, NI, V, VIS, M>(
    graph: &G,
    source: NI,
    mut visited: VIS,
    mut distance_map: M,
) -> Result<M, AlgorithmError<NI>>
where
    G: GraphWithEdgeValues<NI, V>,
    NI: NodeIndex,
    VIS: MapTrait<NI, bool>,
    M: MapTrait<NI, Option<V>>,
    V: PartialOrd + Copy + core::ops::Add<Output = V> + Default,
    AlgorithmError<NI>: From<G::Error>,
{
    // Initialize distances: source is 0, others are None (infinite/unreachable)
    distance_map
        .insert(source, Some(V::default()))
        .capacity_error()?;

    // Initialize all other nodes as unreachable
    for node in graph.iter_nodes()? {
        if node != source {
            distance_map.insert(node, None).capacity_error()?;
        }
    }

    // Initialize visited tracking
    for node in graph.iter_nodes()? {
        visited.insert(node, false).capacity_error()?;
    }

    let node_count = graph.iter_nodes()?.count();

    // Main Dijkstra loop
    for _ in 0..node_count {
        // Find unvisited node with minimum distance
        let mut min_distance = None;
        let mut min_node = None;

        for node in graph.iter_nodes()? {
            if let (Some(is_visited), Some(dist_opt)) =
                (visited.get(&node), distance_map.get(&node))
            {
                if !*is_visited {
                    if let Some(dist) = dist_opt {
                        if let Some(current_min) = min_distance {
                            if *dist < current_min {
                                min_distance = Some(*dist);
                                min_node = Some(node);
                            }
                        } else {
                            min_distance = Some(*dist);
                            min_node = Some(node);
                        }
                    }
                }
            }
        }

        // If no unvisited node found, we're done
        let u = match min_node {
            Some(node) => node,
            None => break,
        };

        // Mark current node as visited
        visited.insert(u, true).capacity_error()?;

        // Update distances to neighbors
        // iterate only outgoing edges from `u`
        for (dst, weight_opt) in graph.outgoing_edge_values(u)? {
            if let Some(weight) = weight_opt {
                if !*visited.get(&dst).unwrap_or(&false) {
                    if let Some(Some(u_dist)) = distance_map.get(&u) {
                        let new_distance = *u_dist + *weight;
                        if let Some(dst_dist_opt) = distance_map.get(&dst) {
                            if dst_dist_opt.is_none_or(|old| new_distance < old) {
                                distance_map
                                    .insert(dst, Some(new_distance))
                                    .capacity_error()?;
                            }
                        }
                    }
                }
            }
        }
    }

    Ok(distance_map)
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::containers::maps::staticdict::Dictionary;
    use crate::edgelist::edge_list::EdgeList;
    use crate::edges::EdgeValueStruct;

    #[test]
    fn test_dijkstra_simple() {
        //    (1)        (2)
        //A ------ B -------- C
        // \       |          |
        //  \      |(5)       |(1)
        //   \     |          |
        //    \    D ---------
        //     \              |
        //      \_____________|
        //          (4)

        // Create the graph with positive edge weights
        let edge_data = EdgeValueStruct([
            ('A', 'B', 1),
            ('A', 'C', 4),
            ('B', 'C', 2),
            ('B', 'D', 5),
            ('C', 'D', 1),
        ]);
        let graph = EdgeList::<8, _, _>::new(edge_data);

        let distance_map = Dictionary::<char, Option<i32>, 16>::new();
        let visited = Dictionary::<char, bool, 16>::new();

        let result = dijkstra(&graph, 'A', visited, distance_map).unwrap();

        // Check the expected distances
        assert_eq!(result.get(&'A'), Some(&Some(0)));
        assert_eq!(result.get(&'B'), Some(&Some(1)));
        assert_eq!(result.get(&'C'), Some(&Some(3))); // 1 (A->B) + 2 (B->C)
        assert_eq!(result.get(&'D'), Some(&Some(4))); // 3 (A->B->C) + 1 (C->D)
    }

    #[test]
    fn test_dijkstra_disconnected() {
        // Create disconnected graph: 0 -> 1 (weight 2), 2 isolated
        let edge_data = EdgeValueStruct([(0usize, 1usize, 2i32)]);
        let graph = EdgeList::<8, _, _>::new(edge_data);

        let distance_map = Dictionary::<usize, Option<i32>, 16>::new();
        let visited = Dictionary::<usize, bool, 16>::new();

        let result = dijkstra(&graph, 0, visited, distance_map).unwrap();

        // Check distances - node 1 should be reachable
        assert_eq!(result.get(&0), Some(&Some(0)));
        assert_eq!(result.get(&1), Some(&Some(2)));
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2	//! Dijkstra algorithm for finding shortest paths
3
4	use super::ContainerResultExt;
5
6	use crate::containers::maps::MapTrait;
7	use crate::graph::{GraphWithEdgeValues, NodeIndex};
8
9	use super::AlgorithmError;
10
11	/// Dijkstra algorithm to find shortest path between nodes
12	///
13	/// Calculates the shortest path from a start node to all other nodes in the graph,
14	/// does not handle negative edge weights.
15	///
16	/// # Arguments
17	/// * `graph` - Graph implementing GraphWithEdgeValues
18	/// * `source` - Source node to find shortest paths from
19	/// * `visited` - Map to track which nodes have been processed
20	/// * `distance_map` - Map to store distances (None = infinite/unreachable, Some(v) = distance v)
21	///
22	/// # Returns
23	/// * `Ok(M)` populated distance map if shortest paths computed successfully
24	/// * `Err(AlgorithmError::GraphError(_))` for graph access errors
25	pub fn dijkstra<G, NI, V, VIS, M>(	2✔
26	graph: &G,	2✔
27	source: NI,	2✔
28	mut visited: VIS,	2✔
29	mut distance_map: M,	2✔
30	) -> Result<M, AlgorithmError<NI>>	2✔
31	where	2✔
32	G: GraphWithEdgeValues<NI, V>,	2✔
33	NI: NodeIndex,	2✔
34	VIS: MapTrait<NI, bool>,	2✔
35	M: MapTrait<NI, Option<V>>,	2✔
36	V: PartialOrd + Copy + core::ops::Add<Output = V> + Default,	2✔
37	AlgorithmError<NI>: From<G::Error>,	2✔
38	{	2✔
39	// Initialize distances: source is 0, others are None (infinite/unreachable)	2✔
40	distance_map	2✔
41	.insert(source, Some(V::default()))	2✔
42	.capacity_error()?;	2✔
43
44	// Initialize all other nodes as unreachable
45	for node in graph.iter_nodes()? {	6✔
46	if node != source {	6✔
47	distance_map.insert(node, None).capacity_error()?;	4✔
48	}	2✔
49	}
50
51	// Initialize visited tracking
52	for node in graph.iter_nodes()? {	6✔
53	visited.insert(node, false).capacity_error()?;	6✔
54	}
55
56	let node_count = graph.iter_nodes()?.count();	2✔
57		2✔
58	// Main Dijkstra loop	2✔
59	for _ in 0..node_count {	2✔
60	// Find unvisited node with minimum distance
61	let mut min_distance = None;	6✔
62	let mut min_node = None;	6✔
63
64	for node in graph.iter_nodes()? {	20✔
65	if let (Some(is_visited), Some(dist_opt)) =	20✔
66	(visited.get(&node), distance_map.get(&node))	20✔
67	{
68	if !*is_visited {	20✔
69	if let Some(dist) = dist_opt {	13✔
70	if let Some(current_min) = min_distance {	8✔
71	if *dist < current_min {	2✔
NEW 72	min_distance = Some(*dist);	×
NEW 73	min_node = Some(node);	×
74	}	2✔
75	} else {	6✔
76	min_distance = Some(*dist);	6✔
77	min_node = Some(node);	6✔
78	}	6✔
79	}	5✔
80	}	7✔
UNCOV 81	}	×
82	}
83
84	// If no unvisited node found, we're done
85	let u = match min_node {	6✔
86	Some(node) => node,	6✔
NEW 87	None => break,	×
88	};
89
90	// Mark current node as visited
91	visited.insert(u, true).capacity_error()?;	6✔
92
93	// Update distances to neighbors
94	// iterate only outgoing edges from `u`
95	for (dst, weight_opt) in graph.outgoing_edge_values(u)? {	6✔
96	if let Some(weight) = weight_opt {	6✔
97	if !*visited.get(&dst).unwrap_or(&false) {	6✔
98	if let Some(Some(u_dist)) = distance_map.get(&u) {	6✔
99	let new_distance = u_dist + weight;	6✔
100	if let Some(dst_dist_opt) = distance_map.get(&dst) {	6✔
101	if dst_dist_opt.is_none_or(\|old\| new_distance < old) {	6✔
102	distance_map	6✔
103	.insert(dst, Some(new_distance))	6✔
104	.capacity_error()?;	6✔
NEW 105	}	×
NEW 106	}	×
UNCOV 107	}	×
UNCOV 108	}	×
109	}	×
110	}
111	}
112
113	Ok(distance_map)	2✔
114	}	2✔
115
116	#[cfg(test)]
117	mod tests {
118	use super::*;
119	use crate::containers::maps::staticdict::Dictionary;
120	use crate::edgelist::edge_list::EdgeList;
121	use crate::edges::EdgeValueStruct;
122
123	#[test]
124	fn test_dijkstra_simple() {	1✔
125	// (1) (2)	1✔
126	//A ------ B -------- C	1✔
127	// \ \| \|	1✔
128	// \ \|(5) \|(1)	1✔
129	// \ \| \|	1✔
130	// \ D ---------	1✔
131	// \ \|	1✔
132	// \_____________\|	1✔
133	// (4)	1✔
134		1✔
135	// Create the graph with positive edge weights	1✔
136	let edge_data = EdgeValueStruct([	1✔
137	('A', 'B', 1),	1✔
138	('A', 'C', 4),	1✔
139	('B', 'C', 2),	1✔
140	('B', 'D', 5),	1✔
141	('C', 'D', 1),	1✔
142	]);	1✔
143	let graph = EdgeList::<8, _, _>::new(edge_data);	1✔
144		1✔
145	let distance_map = Dictionary::<char, Option<i32>, 16>::new();	1✔
146	let visited = Dictionary::<char, bool, 16>::new();	1✔
147		1✔
148	let result = dijkstra(&graph, 'A', visited, distance_map).unwrap();	1✔
149		1✔
150	// Check the expected distances	1✔
151	assert_eq!(result.get(&'A'), Some(&Some(0)));	1✔
152	assert_eq!(result.get(&'B'), Some(&Some(1)));	1✔
153	assert_eq!(result.get(&'C'), Some(&Some(3))); // 1 (A->B) + 2 (B->C)	1✔
154	assert_eq!(result.get(&'D'), Some(&Some(4))); // 3 (A->B->C) + 1 (C->D)	1✔
155	}	1✔
156
157	#[test]
158	fn test_dijkstra_disconnected() {	1✔
159	// Create disconnected graph: 0 -> 1 (weight 2), 2 isolated	1✔
160	let edge_data = EdgeValueStruct([(0usize, 1usize, 2i32)]);	1✔
161	let graph = EdgeList::<8, _, _>::new(edge_data);	1✔
162		1✔
163	let distance_map = Dictionary::<usize, Option<i32>, 16>::new();	1✔
164	let visited = Dictionary::<usize, bool, 16>::new();	1✔
165		1✔
166	let result = dijkstra(&graph, 0, visited, distance_map).unwrap();	1✔
167		1✔
168	// Check distances - node 1 should be reachable	1✔
169	assert_eq!(result.get(&0), Some(&Some(0)));	1✔
170	assert_eq!(result.get(&1), Some(&Some(2)));	1✔
171	}	1✔
172	}

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