fast_graph/lib.rs
1#![crate_name = "fast_graph"]
2
3//! # A fast, lightweight and extensible implementation of a graph data structure.
4//!
5//! ## Lightweight & fast.
6//!
7//! By default, [SlotMaps](`slotmap`) are used to store the nodes and edges which solves the [ABA problem] while also providing O(1) insertion, deletion and lookup times.
8//!
9//! [ABA problem]: https://en.wikipedia.org/wiki/ABA_problem
10//!
11//! ## Extensible & Generic
12//!
13//! The [Graph] is generic over the node and edge data types, which can be any type that implements [Clone]. There's also traits for making even more customized graph-like data structures if the need arises.
14//!
15//! [`std::HashMap`]: https://doc.rust-lang.org/std/collections/struct.HashMap.html
16//!
17//! ## Serde & Specta
18//!
19//! There's optional features to enable [serde] & [specta] support.
20//!
21//! ## Categories
22//!
23//! The [CategorizedGraph] struct uses a hash map to map category names ([String]) to a category node ([NodeID]) (where the node's edges are the nodes belonging to the category).
24//! There's also some useful extra functions to query categories and their nodes, and a [Categorized] trait that can be implemented for a custom struct if needed.
25//!
26//! In other words a simple extension to the graph that allows for efficient and easy grouping of nodes by strings.
27//!
28//! # Structure
29//! [Node] - Struct representing a node in the graph. Contains a [NodeID] which is a key to the node in the slotmap, which has a generic data field and a list of edges.
30//!
31//! [Edge] - Struct representing an edge in the graph. Contains an [EdgeID] which is a key to the edge in the slotmap, and two [NodeID]s which are the nodes the edge connects (from & to). An edge can also have "data", which could be anything or nothing; for example the weight of the connection or a struct or enum representing something else.
32//!
33//! [GraphInterface] - Trait defining methods to alter a graph, i.e. adding, removing, and editing nodes and edges.
34//!
35//!
36//! [Graph] - The default graph struct which implements [GraphInterface]. It only contains two slotmaps, one for nodes and one for edges.
37//!
38//! [Categorized] - Trait that extends the [Graph] with category specific methods.
39//!
40//! [CategorizedGraph] - A graph with categories. Categories are normal nodes (which can contain edges & data), but the graph also contains a hashmap that maps category names to category nodes for easy access.
41//!
42//!
43//! # Examples
44//!
45//! ## Simple [Graph] and the ABA problem.
46//!
47//! ```
48//! use fast_graph::{Graph, Node, Edge};
49//! /* We need to have this trait in scope: */
50//! use fast_graph::{GraphInterface};
51//!
52//! #[derive(Debug, Clone)]
53//! struct EdgeData(String);
54//!
55//! #[derive(Debug, Clone)]
56//! struct NodeData(String);
57//!
58//! let mut graph: Graph<NodeData, EdgeData> = Graph::new();
59//!
60//! let node1 = graph.add_node(NodeData("Node 1".into()));
61//! let node2 = graph.add_node(NodeData("Node 2".into()));
62//! let edge1 = graph.add_edge(node1, node2, EdgeData("Edge 1".into()));
63//!
64//! assert_eq!(graph.node(node1).unwrap().id, node1);
65//! assert_eq!(graph.edge(edge1).unwrap().id, edge1);
66//!
67//! graph.remove_node(node1).unwrap();
68//!
69//! // Since we just removed node 1, it should be None now.
70//! assert!(graph.node(node1).is_err());
71//! // And node 2 still points to node 2.
72//! assert_eq!(graph.node(node2).unwrap().id, node2);
73//!
74//! println!("{:#?}", graph);
75//!
76//! ```
77//!
78//! ## [CategorizedGraph] example
79//! ```
80//! use fast_graph::*;
81//!
82//! #[derive(Clone, Debug, Default, PartialEq)]
83//! #[cfg_attr(feature = "serde", derive(serde::Serialize))]
84//! enum NodeData {
85//! Number(u32),
86//! CategoryData(String),
87//! #[default]
88//! None,
89//! }
90//!
91//! let mut graph: CategorizedGraph<NodeData, ()> = CategorizedGraph::new();
92//!
93//! let node1 = graph.add_node(NodeData::Number(1));
94//! let node2 = graph.add_node(NodeData::Number(2));
95//! let node3 = graph.add_node(NodeData::Number(3));
96//!
97//! let category1 = graph.create_category("Category 1", vec![node1, node2],
98//! NodeData::CategoryData("Category 1".into())
99//! ).unwrap();
100//!
101//! assert_eq!(graph.category("Category 1").unwrap().connections.len(), 2);
102//!
103//! // The category node should have the same data as the one we passed in.
104//! let category1_data = graph.category("Category 1").unwrap().data.clone();
105//! if let NodeData::CategoryData(category1_name) = category1_data {
106//! assert_eq!(category1_name, "Category 1".to_string());
107//! }
108//!
109//! // Adding to a category that doesn't exist will create it.
110//! let category2 = graph.add_to_category("Category 2", vec![node2]);
111//! assert_eq!(graph.all_categories().len(), 2);
112//!
113//! // Adding to the same category twice will return the same category node.
114//! let category2_1 = graph.add_to_category("Category 2", vec![node3]);
115//! assert_eq!(graph.all_categories().len(), 2);
116//! assert_eq!(category2, category2_1);
117//!
118//! // The "Category 2" node should have two connections, one to node2 and one to node3.
119//! let category2_node = graph.category("Category 2").unwrap();
120//! assert_eq!(
121//! // this:
122//! category2_node.connections.iter()
123//! .map(|edge_id|
124//! graph.edge(*edge_id).unwrap().to
125//! )
126//! .collect::<Vec<NodeID>>(),
127//! // should equal:
128//! vec![node2, node3]
129//! );
130//!
131//! // Creating a category twice will error.
132//! assert!(
133//! graph.create_category("Category 1",
134//! vec![node3], NodeData::CategoryData("Category 1".into())
135//! ).is_err()
136//! );
137//! ```
138
139#[cfg(feature = "specta")]
140pub use specta_derives::*;
141
142use core::fmt;
143use std::fmt::Formatter;
144
145pub use slotmap::SlotMap;
146use thiserror::Error;
147
148#[cfg(feature = "categories")]
149pub mod categories;
150
151#[cfg(feature = "categories")]
152pub use categories::*;
153
154pub mod algorithms;
155
156mod edge;
157mod interface;
158mod node;
159mod specta_derives;
160
161pub use edge::{Edge, EdgeID};
162pub use interface::GraphInterface;
163pub use node::{Node, NodeID};
164
165#[cfg(test)]
166#[path = "./tests.rs"]
167mod tests;
168
169/* -------------------------------------------------------------------------- */
170/* Simple very performant graph implementation */
171/* -------------------------------------------------------------------------- */
172
173/* ---------------------------------- Graph --------------------------------- */
174/// The default Graph struct which implements the [GraphInterface] trait.
175///
176///
177/// # Examples
178/// ```
179/// use fast_graph::{Graph, Node, Edge};
180/// /* We need to have this trait in scope: */
181/// use fast_graph::{GraphInterface};
182///
183/// #[derive(Clone, Debug)]
184/// struct EdgeData(String);
185/// #[derive(Clone, Debug)]
186/// struct NodeData(String);
187///
188/// let mut graph: Graph<NodeData, EdgeData> = Graph::new();
189///
190/// let node1 = graph.add_node(NodeData("Node 1".into()));
191/// let node2 = graph.add_node(NodeData("Node 2".into()));
192/// let edge1 = graph.add_edge(node1, node2, EdgeData("Edge 1".into()));
193///
194/// assert_eq!(graph.node(node1).unwrap().id, node1);
195/// assert_eq!(graph.edge(edge1).unwrap().id, edge1);
196///
197/// graph.remove_node(node1).unwrap();
198///
199/// assert!(graph.node(node1).is_err());
200/// assert_eq!(graph.node(node2).unwrap().id, node2);
201///
202/// println!("{:#?}", graph);
203///
204/// ```
205pub struct Graph<N, E> {
206 pub nodes: SlotMap<NodeID, Node<N>>,
207 pub edges: SlotMap<EdgeID, Edge<E>>,
208}
209
210impl<N, E> GraphInterface for Graph<N, E> {
211 type NodeData = N;
212 type EdgeData = E;
213
214 fn nodes(&self) -> impl Iterator<Item = NodeID> {
215 self.nodes.keys()
216 }
217
218 fn node_count(&self) -> usize {
219 self.nodes.len()
220 }
221
222 fn node(&self, id: NodeID) -> Result<&Node<N>, GraphError> {
223 self.nodes.get(id).ok_or(GraphError::NodeNotFound)
224 }
225
226 fn node_mut(&mut self, id: NodeID) -> Result<&mut Node<N>, GraphError> {
227 self.nodes.get_mut(id).ok_or(GraphError::NodeNotFound)
228 }
229
230 fn edge(&self, id: EdgeID) -> Result<&Edge<E>, GraphError> {
231 self.edges.get(id).ok_or(GraphError::EdgeNotFound)
232 }
233
234 fn edge_mut(&mut self, id: EdgeID) -> Result<&mut Edge<E>, GraphError> {
235 self.edges.get_mut(id).ok_or(GraphError::EdgeNotFound)
236 }
237
238 fn remove_node(&mut self, id: NodeID) -> Result<(), GraphError> {
239 let node = self
240 .nodes
241 .remove(id)
242 .map_or(Err(GraphError::NodeNotFound), |n| Ok(n))?;
243 for edge_id in node.connections.iter() {
244 self.edges
245 .remove(*edge_id)
246 .map_or(Err(GraphError::EdgeNotFound), |_| Ok(()))?;
247 }
248 Ok(())
249 }
250
251 fn remove_edge(&mut self, id: EdgeID) -> Result<(), GraphError> {
252 self.edges
253 .remove(id)
254 .map_or(Err(GraphError::EdgeNotFound), |_| Ok(()))?;
255 Ok(())
256 }
257
258 fn add_node(&mut self, data: N) -> NodeID {
259 let id = self.nodes.insert_with_key(|id| Node::new(id, data));
260 id
261 }
262
263 fn add_nodes(&mut self, data: &[N]) -> Vec<NodeID>
264 where
265 N: Clone,
266 {
267 let mut nodes = Vec::new();
268 for data in data {
269 let node = self.add_node(data.clone());
270 nodes.push(node);
271 }
272 nodes
273 }
274
275 fn add_edges(&mut self, data: &[(NodeID, NodeID)]) -> Vec<EdgeID>
276 where
277 E: Default + Clone,
278 N: Clone,
279 {
280 let with_data: Vec<(NodeID, NodeID, E)> = data
281 .iter()
282 .map(|(from, to)| (*from, *to, E::default()))
283 .collect();
284
285 self.add_edges_with_data(&with_data)
286 }
287
288 fn add_edge(&mut self, from: NodeID, to: NodeID, data: E) -> EdgeID {
289 let id = self
290 .edges
291 .insert_with_key(|id| Edge::new(id, from, to, data));
292 if let Some(node) = self.nodes.get_mut(from) {
293 node.add_connection(id);
294 }
295 if let Some(node) = self.nodes.get_mut(to) {
296 node.add_connection(id);
297 }
298 id
299 }
300}
301
302impl<N: fmt::Debug + Clone, E: fmt::Debug + Clone> fmt::Debug for Graph<N, E> {
303 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
304 write!(
305 f,
306 "Graph {{ nodes: {:#?}, edges: {:#?} }}",
307 self.nodes, self.edges
308 )
309 }
310}
311
312impl<N, E> Graph<N, E> {
313 pub fn new() -> Graph<N, E> {
314 Graph {
315 nodes: SlotMap::with_key(),
316 edges: SlotMap::with_key(),
317 }
318 }
319}
320
321#[derive(Debug, Clone, Error)]
322#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
323pub enum GraphError {
324 #[error("Edge not found")]
325 EdgeNotFound,
326 #[error("Node not found")]
327 NodeNotFound,
328}