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

94.29

/src/algorithms/bellman_ford.rs

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

use super::ContainerResultExt;

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

use super::AlgorithmError;

/// Bellman-Ford algorithm for finding shortest paths from a source node
///
/// This algorithm can handle graphs with negative edge weights and will detect
/// negative cycles. It requires edge weights through GraphWithEdgeValues.
/// Uses the standard |V|-1 iterations automatically.
///
/// # Arguments
/// * `graph` - Graph implementing GraphWithEdgeValues
/// * `source` - Source node to find shortest paths from
/// * `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::CycleDetected)` if negative cycle detected
/// * `Err(AlgorithmError::GraphError(_))` for graph access errors
pub fn bellman_ford<G, NI, V, M>(
    graph: &G,
    source: NI,
    distance_map: M,
) -> Result<M, AlgorithmError<NI>>
where
    G: GraphWithEdgeValues<NI, V>,
    NI: NodeIndex,
    M: MapTrait<NI, Option<V>>,
    V: PartialOrd + Copy + core::ops::Add<Output = V> + Default,
    AlgorithmError<NI>: From<G::Error>,
{
    // Auto-compute |V|-1 iterations
    let node_count = graph.iter_nodes()?.count();
    let max_iterations = if node_count > 0 { node_count - 1 } else { 0 };
    bellman_ford_bounded(graph, source, distance_map, max_iterations)
}

/// Bellman-Ford algorithm with custom iteration limit
///
/// This algorithm can handle graphs with negative edge weights and will detect
/// negative cycles. It requires edge weights through GraphWithEdgeValues.
/// Allows custom control over the maximum number of iterations.
///
/// # Arguments
/// * `graph` - Graph implementing GraphWithEdgeValues
/// * `source` - Source node to find shortest paths from
/// * `distance_map` - Map to store distances (None = infinite/unreachable, Some(v) = distance v)
/// * `max_iterations` - Maximum number of iterations (typically |V|-1)
///
/// # Returns
/// * `Ok(M)` populated distance map if shortest paths computed successfully
/// * `Err(AlgorithmError::CycleDetected)` if negative cycle detected
/// * `Err(AlgorithmError::GraphError(_))` for graph access errors
pub fn bellman_ford_bounded<G, NI, V, M>(
    graph: &G,
    source: NI,
    mut distance_map: M,
    max_iterations: usize,
) -> Result<M, AlgorithmError<NI>>
where
    G: GraphWithEdgeValues<NI, V>,
    NI: NodeIndex,
    M: MapTrait<NI, Option<V>>,
    V: PartialOrd + Copy + core::ops::Add<Output = V> + Default,
    AlgorithmError<NI>: From<G::Error>,
{
    // Initialize: source has distance 0, others are None (infinite/unreachable)
    distance_map
        .insert(source, Some(V::default()))
        .capacity_error()?;

    for node in graph.iter_nodes()? {
        if node != source {
            distance_map.insert(node, None).capacity_error()?;
        }
    }

    // Relax edges repeatedly
    for _ in 0..max_iterations {
        let mut changed = false;

        for (src, dst, weight_opt) in graph.iter_edge_values()? {
            if let Some(weight) = weight_opt {
                if let Some(Some(src_dist)) = distance_map.get(&src) {
                    let new_distance = *src_dist + *weight;

                    if let Some(dst_dist_opt) = distance_map.get(&dst) {
                        if dst_dist_opt.is_none() || new_distance < dst_dist_opt.unwrap() {
                            distance_map
                                .insert(dst, Some(new_distance))
                                .capacity_error()?;
                            changed = true;
                        }
                    }
                }
            }
        }

        if !changed {
            break;
        }
    }

    // Check for negative cycles
    for (src, dst, weight_opt) in graph.iter_edge_values()? {
        if let Some(weight) = weight_opt {
            if let Some(Some(src_dist)) = distance_map.get(&src) {
                if let Some(Some(dst_dist)) = distance_map.get(&dst) {
                    let new_distance = *src_dist + *weight;
                    if new_distance < *dst_dist {
                        return Err(AlgorithmError::CycleDetected);
                    }
                }
            }
        }
    }

    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_bellman_ford_simple() {
        // Create a simple weighted graph: 0 -> 1 (weight 5), 1 -> 2 (weight 3)
        let edge_data = EdgeValueStruct([(0usize, 1usize, 5i32), (1, 2, 3)]);
        let graph = EdgeList::<8, _, _>::new(edge_data);

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

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

        assert_eq!(result.get(&0), Some(&Some(0)));
        assert_eq!(result.get(&1), Some(&Some(5)));
        assert_eq!(result.get(&2), Some(&Some(8)));
    }

    #[test]
    fn test_bellman_ford_negative_cycle() {
        // Create graph with negative cycle: 0 -> 1 (weight -1), 1 -> 0 (weight -1)
        let edge_data = EdgeValueStruct([(0usize, 1usize, -1i32), (1, 0, -1)]);
        let graph = EdgeList::<8, _, _>::new(edge_data);

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

        let result = bellman_ford_bounded(&graph, 0, distance_map, 1);
        assert!(matches!(result, Err(AlgorithmError::CycleDetected)));
    }

    #[test]
    fn test_bellman_ford_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 result = bellman_ford(&graph, 0, 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)));
        // Note: node 2 doesn't exist in this graph, so we can't check has_distance for it
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2	//! Bellman-Ford 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	/// Bellman-Ford algorithm for finding shortest paths from a source node
12	///
13	/// This algorithm can handle graphs with negative edge weights and will detect
14	/// negative cycles. It requires edge weights through GraphWithEdgeValues.
15	/// Uses the standard \|V\|-1 iterations automatically.
16	///
17	/// # Arguments
18	/// * `graph` - Graph implementing GraphWithEdgeValues
19	/// * `source` - Source node to find shortest paths from
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::CycleDetected)` if negative cycle detected
25	/// * `Err(AlgorithmError::GraphError(_))` for graph access errors
26	pub fn bellman_ford<G, NI, V, M>(	2✔
27	graph: &G,	2✔
28	source: NI,	2✔
29	distance_map: M,	2✔
30	) -> Result<M, AlgorithmError<NI>>	2✔
31	where	2✔
32	G: GraphWithEdgeValues<NI, V>,	2✔
33	NI: NodeIndex,	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	// Auto-compute \|V\|-1 iterations
39	let node_count = graph.iter_nodes()?.count();	2✔
40	let max_iterations = if node_count > 0 { node_count - 1 } else { 0 };	2✔
41	bellman_ford_bounded(graph, source, distance_map, max_iterations)	2✔
42	}	2✔
43
44	/// Bellman-Ford algorithm with custom iteration limit
45	///
46	/// This algorithm can handle graphs with negative edge weights and will detect
47	/// negative cycles. It requires edge weights through GraphWithEdgeValues.
48	/// Allows custom control over the maximum number of iterations.
49	///
50	/// # Arguments
51	/// * `graph` - Graph implementing GraphWithEdgeValues
52	/// * `source` - Source node to find shortest paths from
53	/// * `distance_map` - Map to store distances (None = infinite/unreachable, Some(v) = distance v)
54	/// * `max_iterations` - Maximum number of iterations (typically \|V\|-1)
55	///
56	/// # Returns
57	/// * `Ok(M)` populated distance map if shortest paths computed successfully
58	/// * `Err(AlgorithmError::CycleDetected)` if negative cycle detected
59	/// * `Err(AlgorithmError::GraphError(_))` for graph access errors
60	pub fn bellman_ford_bounded<G, NI, V, M>(	3✔
61	graph: &G,	3✔
62	source: NI,	3✔
63	mut distance_map: M,	3✔
64	max_iterations: usize,	3✔
65	) -> Result<M, AlgorithmError<NI>>	3✔
66	where	3✔
67	G: GraphWithEdgeValues<NI, V>,	3✔
68	NI: NodeIndex,	3✔
69	M: MapTrait<NI, Option<V>>,	3✔
70	V: PartialOrd + Copy + core::ops::Add<Output = V> + Default,	3✔
71	AlgorithmError<NI>: From<G::Error>,	3✔
72	{	3✔
73	// Initialize: source has distance 0, others are None (infinite/unreachable)	3✔
74	distance_map	3✔
75	.insert(source, Some(V::default()))	3✔
76	.capacity_error()?;	3✔
77
78	for node in graph.iter_nodes()? {	7✔
79	if node != source {	7✔
80	distance_map.insert(node, None).capacity_error()?;	4✔
81	}	3✔
82	}
83
84	// Relax edges repeatedly
85	for _ in 0..max_iterations {	3✔
86	let mut changed = false;	4✔
87
88	for (src, dst, weight_opt) in graph.iter_edge_values()? {	7✔
89	if let Some(weight) = weight_opt {	7✔
90	if let Some(Some(src_dist)) = distance_map.get(&src) {	7✔
91	let new_distance = src_dist + weight;	7✔
92
93	if let Some(dst_dist_opt) = distance_map.get(&dst) {	7✔
94	if dst_dist_opt.is_none() \|\| new_distance < dst_dist_opt.unwrap() {	7✔
95	distance_map	5✔
96	.insert(dst, Some(new_distance))	5✔
97	.capacity_error()?;	5✔
98	changed = true;	5✔
99	}	2✔
NEW 100	}	×
NEW 101	}	×
UNCOV 102	}	×
103	}
104
105	if !changed {	4✔
106	break;	1✔
107	}	3✔
108	}
109
110	// Check for negative cycles
111	for (src, dst, weight_opt) in graph.iter_edge_values()? {	4✔
112	if let Some(weight) = weight_opt {	4✔
113	if let Some(Some(src_dist)) = distance_map.get(&src) {	4✔
114	if let Some(Some(dst_dist)) = distance_map.get(&dst) {	4✔
115	let new_distance = src_dist + weight;	4✔
116	if new_distance < *dst_dist {	4✔
117	return Err(AlgorithmError::CycleDetected);	1✔
118	}	3✔
NEW 119	}	×
NEW 120	}	×
UNCOV 121	}	×
122	}
123
124	Ok(distance_map)	2✔
125	}	3✔
126
127	#[cfg(test)]
128	mod tests {
129	use super::*;
130	use crate::containers::maps::staticdict::Dictionary;
131	use crate::edgelist::edge_list::EdgeList;
132	use crate::edges::EdgeValueStruct;
133
134	#[test]
135	fn test_bellman_ford_simple() {	1✔
136	// Create a simple weighted graph: 0 -> 1 (weight 5), 1 -> 2 (weight 3)	1✔
137	let edge_data = EdgeValueStruct([(0usize, 1usize, 5i32), (1, 2, 3)]);	1✔
138	let graph = EdgeList::<8, _, _>::new(edge_data);	1✔
139		1✔
140	let distance_map = Dictionary::<usize, Option<i32>, 16>::new();	1✔
141		1✔
142	let result = bellman_ford(&graph, 0, distance_map).unwrap();	1✔
143		1✔
144	assert_eq!(result.get(&0), Some(&Some(0)));	1✔
145	assert_eq!(result.get(&1), Some(&Some(5)));	1✔
146	assert_eq!(result.get(&2), Some(&Some(8)));	1✔
147	}	1✔
148
149	#[test]
150	fn test_bellman_ford_negative_cycle() {	1✔
151	// Create graph with negative cycle: 0 -> 1 (weight -1), 1 -> 0 (weight -1)	1✔
152	let edge_data = EdgeValueStruct([(0usize, 1usize, -1i32), (1, 0, -1)]);	1✔
153	let graph = EdgeList::<8, _, _>::new(edge_data);	1✔
154		1✔
155	let distance_map = Dictionary::<usize, Option<i32>, 16>::new();	1✔
156		1✔
157	let result = bellman_ford_bounded(&graph, 0, distance_map, 1);	1✔
158	assert!(matches!(result, Err(AlgorithmError::CycleDetected)));	1✔
159	}	1✔
160
161	#[test]
162	fn test_bellman_ford_disconnected() {	1✔
163	// Create disconnected graph: 0 -> 1 (weight 2), 2 isolated	1✔
164	let edge_data = EdgeValueStruct([(0usize, 1usize, 2i32)]);	1✔
165	let graph = EdgeList::<8, _, _>::new(edge_data);	1✔
166		1✔
167	let distance_map = Dictionary::<usize, Option<i32>, 16>::new();	1✔
168		1✔
169	let result = bellman_ford(&graph, 0, distance_map).unwrap();	1✔
170		1✔
171	// Check distances - node 1 should be reachable	1✔
172	assert_eq!(result.get(&0), Some(&Some(0)));	1✔
173	assert_eq!(result.get(&1), Some(&Some(2)));	1✔
174	// Note: node 2 doesn't exist in this graph, so we can't check has_distance for it
175	}	1✔
176	}

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