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

96.23

/src/graph.rs

// SPDX-License-Identifier: Apache-2.0

//! Core graph traits
//!
//! Defines the [`Graph`] trait and related error values
//! and sub-traits.

/// Trait for types that can be used as node indices in graphs
///
/// Node indices must support equality, ordering comparisons, and copying.
/// This is typically implemented for numeric types like `usize`, `u32`, etc.
///
/// The trait is automatically implemented for any type that satisfies the bounds,
/// making it easy to use custom index types while ensuring they have the required
/// operations for graph algorithms.
pub trait NodeIndex: PartialEq + PartialOrd + Copy {}
impl<T> NodeIndex for T where T: PartialEq + PartialOrd + Copy {}

/// Errors that can occur during graph operations
///
/// This enum represents various error conditions that may arise when working
/// with graph structures, such as accessing non-existent nodes or edges.
#[derive(PartialEq, Debug, Clone, Copy)]
pub enum GraphError<NI: NodeIndex> {
    /// Edge is referring to a node not present in graph
    EdgeHasInvalidNode(NI),
    /// Given node wasn't found in the graph
    NodeNotFound(NI),
    /// Index is out of bounds
    IndexOutOfBounds(usize, NI),
    /// Unexpected condition occurred
    Unexpected,
}

/// Core graph trait for immutable graph access
///
/// This trait provides read-only access to graph structure through owned values.
/// It forms the foundation for all graph representations in this library, with
/// concrete implementations like [`EdgeNodeList`](crate::edgelist::edge_node_list::EdgeNodeList)
/// and adjacency list representations.
///
/// All methods return owned values rather than references for better ergonomics,
/// though this may require cloning for some implementations.
pub trait Graph<NI: NodeIndex> {
    type Error: From<GraphError<NI>>;

    /// Return an iterator over all nodes in the graph
    fn iter_nodes(&self) -> Result<impl Iterator<Item = NI>, Self::Error>;
    /// Return an iterator over all edges in the graph
    fn iter_edges(&self) -> Result<impl Iterator<Item = (NI, NI)>, Self::Error>;

    /// Return an iterator over all outgoing edges for a node
    ///
    /// Default implementation filters all edges, which is inefficient.
    /// Implementers should override this method when they can provide
    /// direct access to outgoing edges (e.g., adjacency lists, matrices).
    fn outgoing_edges(&self, node: NI) -> Result<impl Iterator<Item = NI>, Self::Error> {
        Ok(self
            .iter_edges()?
            .filter(move |(src, _dst)| *src == node)
            .map(|(_src, dst)| dst))
    }

    /// Return an iterator over all incoming edges for a node
    ///
    /// Default implementation filters all edges, which is inefficient.
    /// Implementers should override this method when they can provide
    /// direct access to incoming edges (e.g., adjacency matrices).
    fn incoming_edges(&self, node: NI) -> Result<impl Iterator<Item = NI>, Self::Error> {
        Ok(self
            .iter_edges()?
            .filter(move |(_src, dst)| *dst == node)
            .map(|(src, _dst)| src))
    }

    /// Check if a node is present in the graph
    ///
    /// **Performance Warning**: Default implementation iterates all nodes, which is O(n).
    /// Implementers should override this method when they can provide
    /// faster lookup (e.g., hash-based storage for O(1) or tree-based storage for O(log n)).
    fn contains_node(&self, node: NI) -> Result<bool, Self::Error> {
        Ok(self.iter_nodes()?.any(|x| x == node))
    }
}

/// Extension of [`Graph`] that provides access to node values
///
/// This trait extends basic graph functionality with the ability to associate
/// values of type `NV` with each node in the graph. Node values are optional,
/// allowing for sparse assignment of data to nodes.
///
/// Useful for algorithms that need to store additional data with nodes,
/// such as distances in shortest path algorithms, colors in graph coloring,
/// or any domain-specific node attributes.
pub trait GraphWithNodeValues<NI, NV>: Graph<NI>
where
    NI: NodeIndex,
{
    /// Get the value associated with a node
    fn node_value(&self, node: NI) -> Result<Option<&NV>, Self::Error>;
    /// Return an iterator over all node values in the graph
    fn iter_node_values<'a>(
        &'a self,
    ) -> Result<impl Iterator<Item = (NI, Option<&'a NV>)>, Self::Error>
    where
        NV: 'a;
}

/// Extension of [`Graph`] that provides access to edge values
///
/// This trait extends basic graph functionality with the ability to associate
/// values of type `EV` with each edge in the graph. Edge values are optional,
/// allowing for sparse assignment of data to edges.
///
/// Commonly used for weighted graphs where edges have costs, capacities,
/// distances, or other numeric values. Also useful for storing metadata
/// about relationships between nodes.
pub trait GraphWithEdgeValues<NI, EV>: Graph<NI>
where
    NI: NodeIndex,
{
    fn iter_edge_values<'a>(
        &'a self,
    ) -> Result<impl Iterator<Item = (NI, NI, Option<&'a EV>)>, Self::Error>
    where
        EV: 'a;

    /// Return outgoing edges with values for a specific node
    ///
    /// **Performance Warning**: Default implementation filters all edges, which is O(E).
    /// Implementers should override this method when they can provide
    /// direct access to outgoing edges (e.g., adjacency lists).
    fn outgoing_edge_values<'a>(
        &'a self,
        node: NI,
    ) -> Result<impl Iterator<Item = (NI, Option<&'a EV>)>, Self::Error>
    where
        EV: 'a,
    {
        Ok(self
            .iter_edge_values()?
            .filter(move |(src, _dst, _weight)| *src == node)
            .map(|(_src, dst, weight)| (dst, weight)))
    }

    /// Return incoming edges with values for a specific node
    ///
    /// **Performance Warning**: Default implementation filters all edges, which is O(E).
    /// Implementers should override this method when they can provide
    /// direct access to incoming edges (e.g., adjacency matrices).
    fn incoming_edge_values<'a>(
        &'a self,
        node: NI,
    ) -> Result<impl Iterator<Item = (NI, Option<&'a EV>)>, Self::Error>
    where
        EV: 'a,
    {
        Ok(self
            .iter_edge_values()?
            .filter(move |(_src, dst, _weight)| *dst == node)
            .map(|(src, _dst, weight)| (src, weight)))
    }
}

/// Integrity check for graphs - validates that all edges reference valid nodes
///
/// This function checks that every edge in the graph references nodes that actually
/// exist in the graph's node set. This is used during graph construction to ensure
/// data integrity and prevent invalid graph states.
pub(crate) fn integrity_check<NI, G>(graph: &G) -> Result<(), G::Error>
where
    NI: NodeIndex,
    G: Graph<NI>,
{
    for (src, dst) in graph.iter_edges()? {
        if !graph.contains_node(src)? {
            return Err(GraphError::EdgeHasInvalidNode(src).into());
        }
        if !graph.contains_node(dst)? {
            return Err(GraphError::EdgeHasInvalidNode(dst).into());
        }
    }

    // TODO: Perhaps check for duplicate nodes
    Ok(())
}

1	// SPDX-License-Identifier: Apache-2.0
2
3	//! Core graph traits
4	//!
5	//! Defines the [`Graph`] trait and related error values
6	//! and sub-traits.
7
8	/// Trait for types that can be used as node indices in graphs
9	///
10	/// Node indices must support equality, ordering comparisons, and copying.
11	/// This is typically implemented for numeric types like `usize`, `u32`, etc.
12	///
13	/// The trait is automatically implemented for any type that satisfies the bounds,
14	/// making it easy to use custom index types while ensuring they have the required
15	/// operations for graph algorithms.
16	pub trait NodeIndex: PartialEq + PartialOrd + Copy {}
17	impl<T> NodeIndex for T where T: PartialEq + PartialOrd + Copy {}
18
19	/// Errors that can occur during graph operations
20	///
21	/// This enum represents various error conditions that may arise when working
22	/// with graph structures, such as accessing non-existent nodes or edges.
23	#[derive(PartialEq, Debug, Clone, Copy)]
24	pub enum GraphError<NI: NodeIndex> {
25	/// Edge is referring to a node not present in graph
26	EdgeHasInvalidNode(NI),
27	/// Given node wasn't found in the graph
28	NodeNotFound(NI),
29	/// Index is out of bounds
30	IndexOutOfBounds(usize, NI),
31	/// Unexpected condition occurred
32	Unexpected,
33	}
34
35	/// Core graph trait for immutable graph access
36	///
37	/// This trait provides read-only access to graph structure through owned values.
38	/// It forms the foundation for all graph representations in this library, with
39	/// concrete implementations like [`EdgeNodeList`](crate::edgelist::edge_node_list::EdgeNodeList)
40	/// and adjacency list representations.
41	///
42	/// All methods return owned values rather than references for better ergonomics,
43	/// though this may require cloning for some implementations.
44	pub trait Graph<NI: NodeIndex> {
45	type Error: From<GraphError<NI>>;
46
47	/// Return an iterator over all nodes in the graph
48	fn iter_nodes(&self) -> Result<impl Iterator<Item = NI>, Self::Error>;
49	/// Return an iterator over all edges in the graph
50	fn iter_edges(&self) -> Result<impl Iterator<Item = (NI, NI)>, Self::Error>;
51
52	/// Return an iterator over all outgoing edges for a node
53	///
54	/// Default implementation filters all edges, which is inefficient.
55	/// Implementers should override this method when they can provide
56	/// direct access to outgoing edges (e.g., adjacency lists, matrices).
57	fn outgoing_edges(&self, node: NI) -> Result<impl Iterator<Item = NI>, Self::Error> {	292✔
58	Ok(self	292✔
59	.iter_edges()?	292✔
60	.filter(move \|(src, _dst)\| *src == node)	1,248✔
61	.map(\|(_src, dst)\| dst))	292✔
62	}	292✔
63
64	/// Return an iterator over all incoming edges for a node
65	///
66	/// Default implementation filters all edges, which is inefficient.
67	/// Implementers should override this method when they can provide
68	/// direct access to incoming edges (e.g., adjacency matrices).
69	fn incoming_edges(&self, node: NI) -> Result<impl Iterator<Item = NI>, Self::Error> {	30✔
70	Ok(self	30✔
71	.iter_edges()?	30✔
72	.filter(move \|(_src, dst)\| *dst == node)	79✔
73	.map(\|(src, _dst)\| src))	30✔
74	}	30✔
75
76	/// Check if a node is present in the graph
77	///
78	/// Performance Warning: Default implementation iterates all nodes, which is O(n).
79	/// Implementers should override this method when they can provide
80	/// faster lookup (e.g., hash-based storage for O(1) or tree-based storage for O(log n)).
81	fn contains_node(&self, node: NI) -> Result<bool, Self::Error> {	158✔
82	Ok(self.iter_nodes()?.any(\|x\| x == node))	494✔
83	}	158✔
84	}
85
86	/// Extension of [`Graph`] that provides access to node values
87	///
88	/// This trait extends basic graph functionality with the ability to associate
89	/// values of type `NV` with each node in the graph. Node values are optional,
90	/// allowing for sparse assignment of data to nodes.
91	///
92	/// Useful for algorithms that need to store additional data with nodes,
93	/// such as distances in shortest path algorithms, colors in graph coloring,
94	/// or any domain-specific node attributes.
95	pub trait GraphWithNodeValues<NI, NV>: Graph<NI>
96	where
97	NI: NodeIndex,
98	{
99	/// Get the value associated with a node
100	fn node_value(&self, node: NI) -> Result<Option<&NV>, Self::Error>;
101	/// Return an iterator over all node values in the graph
102	fn iter_node_values<'a>(
103	&'a self,
104	) -> Result<impl Iterator<Item = (NI, Option<&'a NV>)>, Self::Error>
105	where
106	NV: 'a;
107	}
108
109	/// Extension of [`Graph`] that provides access to edge values
110	///
111	/// This trait extends basic graph functionality with the ability to associate
112	/// values of type `EV` with each edge in the graph. Edge values are optional,
113	/// allowing for sparse assignment of data to edges.
114	///
115	/// Commonly used for weighted graphs where edges have costs, capacities,
116	/// distances, or other numeric values. Also useful for storing metadata
117	/// about relationships between nodes.
118	pub trait GraphWithEdgeValues<NI, EV>: Graph<NI>
119	where
120	NI: NodeIndex,
121	{
122	fn iter_edge_values<'a>(
123	&'a self,
124	) -> Result<impl Iterator<Item = (NI, NI, Option<&'a EV>)>, Self::Error>
125	where
126	EV: 'a;
127
128	/// Return outgoing edges with values for a specific node
129	///
130	/// Performance Warning: Default implementation filters all edges, which is O(E).
131	/// Implementers should override this method when they can provide
132	/// direct access to outgoing edges (e.g., adjacency lists).
133	fn outgoing_edge_values<'a>(	8✔
134	&'a self,	8✔
135	node: NI,	8✔
136	) -> Result<impl Iterator<Item = (NI, Option<&'a EV>)>, Self::Error>	8✔
137	where	8✔
138	EV: 'a,	8✔
139	{	8✔
140	Ok(self	8✔
141	.iter_edge_values()?	8✔
142	.filter(move \|(src, _dst, _weight)\| *src == node)	31✔
143	.map(\|(_src, dst, weight)\| (dst, weight)))	10✔
144	}	8✔
145
146	/// Return incoming edges with values for a specific node
147	///
148	/// Performance Warning: Default implementation filters all edges, which is O(E).
149	/// Implementers should override this method when they can provide
150	/// direct access to incoming edges (e.g., adjacency matrices).
151	fn incoming_edge_values<'a>(	4✔
152	&'a self,	4✔
153	node: NI,	4✔
154	) -> Result<impl Iterator<Item = (NI, Option<&'a EV>)>, Self::Error>	4✔
155	where	4✔
156	EV: 'a,	4✔
157	{	4✔
158	Ok(self	4✔
159	.iter_edge_values()?	4✔
160	.filter(move \|(_src, dst, _weight)\| *dst == node)	16✔
161	.map(\|(src, _dst, weight)\| (src, weight)))	4✔
162	}	4✔
163	}
164
165	/// Integrity check for graphs - validates that all edges reference valid nodes
166	///
167	/// This function checks that every edge in the graph references nodes that actually
168	/// exist in the graph's node set. This is used during graph construction to ensure
169	/// data integrity and prevent invalid graph states.
170	pub(crate) fn integrity_check<NI, G>(graph: &G) -> Result<(), G::Error>	17✔
171	where	17✔
172	NI: NodeIndex,	17✔
173	G: Graph<NI>,	17✔
174	{	17✔
175	for (src, dst) in graph.iter_edges()? {	53✔
176	if !graph.contains_node(src)? {	53✔
NEW 177	return Err(GraphError::EdgeHasInvalidNode(src).into());	×
178	}	53✔
179	if !graph.contains_node(dst)? {	53✔
NEW 180	return Err(GraphError::EdgeHasInvalidNode(dst).into());	×
181	}	53✔
182	}
183
184	// TODO: Perhaps check for duplicate nodes
185	Ok(())	17✔
186	}	17✔

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