Crate fast_graph

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.

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

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

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

Categorized - Trait that extends the Graph with category specific methods.

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.

Examples

Simple Graph and the ABA problem.

use fast_graph::{Graph, Node, Edge};
/* We need to have this trait in scope: */
use fast_graph::{GraphInterface};

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

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

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

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

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

graph.remove_node(node1).unwrap();

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

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

CategorizedGraph 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: CategorizedGraph<NodeData, ()> = CategorizedGraph::new();

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

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

• pub use categories::*;

Modules

• algorithms
• categories
  A graph with category nodes.

Structs

• Edge
  A struct representing an edge in the graph.
• EdgeID
  An index to an edge in the slotmap
• Graph
  The default Graph struct which implements the GraphInterface trait.
• Node
  A struct representing a node/vertex in the graph.
• NodeID
  A key to the node in the slotmap.
• SlotMap
  Slot map, storage with stable unique keys.

Enums

• GraphError

Traits

• GraphInterface
  GraphInterface is a trait for basic “read and write” operations on a graph; core operations needed to change a graph and some derived helper functions.