Crate fast_graph

source ·
Expand description

§A fast, lightweight and extensible implementation of a graph data structure.

§Lightweight & fast.

By default, SlotMaps are used to store the nodes and edges which solves the ABA problem while also providing O(1) insertion, deletion and lookup times. Additionally, and optionally, HashBrown is used instead of std::HashMap to map category names to ids in the CategoryGraph struct.

§Extensible & Generic

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.

§Serde & Specta

There’s optional features to enable [serde] & [specta] support.

§Categories

The CategoryGraph 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). 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.

In other words a simple extension to the graph that allows for efficient and easy grouping of nodes by strings.

§Structure

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.

Edge - Struct representing an edge in the graph. Contains an EdgeID which is a key to the edge in the slotmap, and two NodeIDs 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.

GraphWriter - Trait defining methods to alter a graph, i.e. adding, removing, and editing nodes and edges.

SlotMapGraph - Trait defining methods to access the nodes and edges of a graph where the nodes and edges are stored in slotmaps. Implements GraphWriter.

Graph - The default graph struct which implements SlotMapGraph. It only contains two slotmaps, one for nodes and one for edges.

Categorized - Trait that extends SlotMapGraph with category specific methods.

CategoryGraph - 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.

§Examples

§Simple Graph and the ABA problem.

use fast_graph::{Graph, Node, Edge};
/* We need to have these traits in scope: */
use fast_graph::{SlotMapGraph, GraphWriter};

#[derive(Clone, Debug)]
struct EdgeData(String);
#[derive(Clone, Debug)]
struct NodeData(String);

let mut graph: Graph<NodeData, EdgeData> = Graph::new();

let node1 = graph.add_node(NodeData("Node 1".into())).clone();
let node2 = graph.add_node(NodeData("Node 2".into())).clone();
let edge1 = graph.add_edge(node1.id, node2.id, EdgeData("Edge 1".into())).clone();

assert_eq!(graph.node(node1.id).unwrap().id, node1.id);
assert_eq!(graph.edge(edge1.id).unwrap().id, edge1.id);

graph.remove_node(node1.id).unwrap();

// Since we just removed node 1, it should be None now.
assert_eq!(graph.node(node1.id), None);
// And node 2 still points to node 2.
assert_eq!(graph.node(node2.id).unwrap().id, node2.id);

println!("{:#?}", graph);

§CategoryGraph example

use fast_graph::*;

#[derive(Clone, Debug, Default, PartialEq)]
#[cfg_attr(feature = "serde", derive(serde::Serialize))]
enum NodeData {
    Number(u32),
    CategoryData(String),
    #[default]
    None,
}

let mut graph: CategoryGraph<NodeData, ()> = CategoryGraph::new();

let node1 = graph.add_node(NodeData::Number(1)).id;
let node2 = graph.add_node(NodeData::Number(2)).id;
let node3 = graph.add_node(NodeData::Number(3)).id;

let category1 = graph.create_category("Category 1", vec![node1, node2],
    NodeData::CategoryData("Category 1".into())
).unwrap();
 
assert_eq!(graph.category("Category 1").unwrap().connections.len(), 2);
 
// The category node should have the same data as the one we passed in.
let category1_data = graph.category("Category 1").unwrap().data.clone();
if let NodeData::CategoryData(category1_name) = category1_data {
   assert_eq!(category1_name, "Category 1".to_string());
}
 
// Adding to a category that doesn't exist will create it. 
let category2 = graph.add_to_category("Category 2", vec![node2]);
assert_eq!(graph.all_categories().len(), 2);
 
// Adding to the same category twice will return the same category node.
let category2_1 = graph.add_to_category("Category 2", vec![node3]);
assert_eq!(graph.all_categories().len(), 2);
assert_eq!(category2, category2_1);
 
// The "Category 2" node should have two connections, one to node2 and one to node3.
let category2_node = graph.category("Category 2").unwrap();
assert_eq!(
// this:
    category2_node.connections.iter()
        .map(|edge_id|
            graph.edge(*edge_id).unwrap().to
        )
        .collect::<Vec<NodeID>>(),
// should equal:
    vec![node2, node3]
);

// Creating a category twice will error.
assert!(
    graph.create_category("Category 1",
        vec![node3], NodeData::CategoryData("Category 1".into())
    ).is_err()
);

Re-exports§

Modules§

Structs§

Enums§