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}