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

63.64

/src/algorithms.rs

// SPDX-License-Identifier: Apache-2.0

//! Provides some common graph algorithms
//!
//! Sample implementations of frequently used graph algorithms.
//!
//! Note: These are not necessarily efficient implementations,
//! nor thoroughly tested.

mod bellman_ford;
mod connected_components;
mod dijkstra;
mod greedy_coloring;
mod kahns;
mod kruskals;
mod tarjan_scc;
mod topological_sort;
mod traversal;

pub use bellman_ford::bellman_ford;
pub use connected_components::{connected_components, count_connected_components};
pub use dijkstra::dijkstra;
pub use greedy_coloring::greedy_color;
pub use kahns::kahns;
pub use kruskals::kruskals;
pub use tarjan_scc::{count_tarjan_scc, tarjan_scc};
pub use topological_sort::topological_sort_dfs;
pub use traversal::{bfs, bfs_unchecked, dfs_iterative, dfs_recursive, dfs_recursive_unchecked};

use crate::edgelist::edge_list::EdgeListError;
use crate::edges::EdgeNodeError;
use crate::graph::{GraphError, NodeIndex};

/// Errors that can occur during graph algorithm execution
///
/// This enum represents various error conditions that may arise when running
/// graph algorithms, including capacity limitations and graph-related errors.
#[derive(Debug, Clone, Copy, PartialEq)]
pub enum AlgorithmError<NI: NodeIndex> {
    /// Queue capacity exceeded during breadth-first operations
    QueueCapacityExceeded,
    /// Stack capacity exceeded during depth-first operations
    StackCapacityExceeded,
    /// Buffer for edges too small
    EdgeCapacityExceeded,
    /// Visited tracker capacity exceeded
    VisitedTrackerCapacityExceeded,
    /// Cycle detected in algorithm that requires acyclic graph
    CycleDetected,
    /// Output buffer too small
    ResultCapacityExceeded,
    /// Invalid algorithm state (e.g., empty stack when expecting nodes)
    InvalidState,
    /// Graph operation error
    GraphError(GraphError<NI>),
    /// Edge node error
    EdgeNodeError(EdgeNodeError),
}

impl<NI: NodeIndex> From<GraphError<NI>> for AlgorithmError<NI> {
    fn from(e: GraphError<NI>) -> Self {
        AlgorithmError::GraphError(e)
    }
}

// Helper to easily cast container capacity errors to algorithm errors
pub trait ContainerResultExt<T, NI: NodeIndex> {
    fn capacity_error(self) -> Result<T, AlgorithmError<NI>>;
}

impl<T, V, NI: NodeIndex> ContainerResultExt<T, NI> for Result<T, V> {
    fn capacity_error(self) -> Result<T, AlgorithmError<NI>> {
        self.map_err(|_| AlgorithmError::ResultCapacityExceeded)
    }
}

impl<NI: NodeIndex> From<EdgeListError<NI>> for AlgorithmError<NI> {
    fn from(e: EdgeListError<NI>) -> Self {
        match e {
            EdgeListError::GraphError(ge) => AlgorithmError::GraphError(ge),
            EdgeListError::EdgeNodeError(ene) => AlgorithmError::EdgeNodeError(ene),
        }
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2
3	//! Provides some common graph algorithms
4	//!
5	//! Sample implementations of frequently used graph algorithms.
6	//!
7	//! Note: These are not necessarily efficient implementations,
8	//! nor thoroughly tested.
9
10	mod bellman_ford;
11	mod connected_components;
12	mod dijkstra;
13	mod greedy_coloring;
14	mod kahns;
15	mod kruskals;
16	mod tarjan_scc;
17	mod topological_sort;
18	mod traversal;
19
20	pub use bellman_ford::bellman_ford;
21	pub use connected_components::{connected_components, count_connected_components};
22	pub use dijkstra::dijkstra;
23	pub use greedy_coloring::greedy_color;
24	pub use kahns::kahns;
25	pub use kruskals::kruskals;
26	pub use tarjan_scc::{count_tarjan_scc, tarjan_scc};
27	pub use topological_sort::topological_sort_dfs;
28	pub use traversal::{bfs, bfs_unchecked, dfs_iterative, dfs_recursive, dfs_recursive_unchecked};
29
30	use crate::edgelist::edge_list::EdgeListError;
31	use crate::edges::EdgeNodeError;
32	use crate::graph::{GraphError, NodeIndex};
33
34	/// Errors that can occur during graph algorithm execution
35	///
36	/// This enum represents various error conditions that may arise when running
37	/// graph algorithms, including capacity limitations and graph-related errors.
38	#[derive(Debug, Clone, Copy, PartialEq)]
39	pub enum AlgorithmError<NI: NodeIndex> {
40	/// Queue capacity exceeded during breadth-first operations
41	QueueCapacityExceeded,
42	/// Stack capacity exceeded during depth-first operations
43	StackCapacityExceeded,
44	/// Buffer for edges too small
45	EdgeCapacityExceeded,
46	/// Visited tracker capacity exceeded
47	VisitedTrackerCapacityExceeded,
48	/// Cycle detected in algorithm that requires acyclic graph
49	CycleDetected,
50	/// Output buffer too small
51	ResultCapacityExceeded,
52	/// Invalid algorithm state (e.g., empty stack when expecting nodes)
53	InvalidState,
54	/// Graph operation error
55	GraphError(GraphError<NI>),
56	/// Edge node error
57	EdgeNodeError(EdgeNodeError),
58	}
59
60	impl<NI: NodeIndex> From<GraphError<NI>> for AlgorithmError<NI> {
61	fn from(e: GraphError<NI>) -> Self {	×
62	AlgorithmError::GraphError(e)	×
63	}	×
64	}
65
66	// Helper to easily cast container capacity errors to algorithm errors
67	pub trait ContainerResultExt<T, NI: NodeIndex> {
68	fn capacity_error(self) -> Result<T, AlgorithmError<NI>>;
69	}
70
71	impl<T, V, NI: NodeIndex> ContainerResultExt<T, NI> for Result<T, V> {
72	fn capacity_error(self) -> Result<T, AlgorithmError<NI>> {	124✔
73	self.map_err(\|_\| AlgorithmError::ResultCapacityExceeded)	124✔
74	}	124✔
75	}
76
77	impl<NI: NodeIndex> From<EdgeListError<NI>> for AlgorithmError<NI> {
78	fn from(e: EdgeListError<NI>) -> Self {	1✔
79	match e {	1✔
NEW 80	EdgeListError::GraphError(ge) => AlgorithmError::GraphError(ge),	×
81	EdgeListError::EdgeNodeError(ene) => AlgorithmError::EdgeNodeError(ene),	1✔
82	}
83	}	1✔
84	}

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