15665410164

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

Build # 15665410164

Build Type

Pull #8

github

Committed by

web-flow

Commit Message

Merge branch 'main' into no_ref_graphs

Pull Request Pull Request #8: No ref graphs

Run Details

3387 of 3459 new or added lines in 26 files covered. (97.92%)

41 existing lines in 7 files now uncovered.

5130 of 5474 relevant lines covered (93.72%)

44.54 hits per line

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

92.79

/src/algorithms/dijkstra.rs

// SPDX-License-Identifier: Apache-2.0

//! Dijkstra algorithm for finding shortest paths

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

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

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

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

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

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

kaidokert / heapless-graphs-rs / 15665410164

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