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.
The Graph is generic over the node and edge data types. There's also traits for making even more customized graph-like data structures if the need arises.
There's optional features to enable [serde] & [specta] support.
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.
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.
Check out the ROADMAP.md file
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)]
struct EdgeData(String);
#[derive(Debug)]
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.id, node2.id, EdgeData("Edge 1".into()));
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);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)).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;
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()
);
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent