GotGraph provides a unique approach to graph manipulation in Rust that leverages the type system and lifetime checking to prevent common graph-related bugs at compile time.
- Lifetime Safety: Node and edge references cannot escape their intended scope
- Type Safety: Strong typing prevents mixing indices from different graphs
- Zero-Cost Abstractions: Safety features have no runtime overhead
- Flexible Graph Types: Support for different graph implementations
- Algorithm Support: Built-in graph algorithms with safe APIs
You can perform basic graph operations directly without scopes:
use gotgraph::prelude::*; let mut graph: VecGraph<&str, i32> = VecGraph::default(); // Add nodes directly let alice_idx = graph.add_node("Alice"); let bob_idx = graph.add_node("Bob"); let charlie_idx = graph.add_node("Charlie"); // Add edges directly let edge1 = graph.add_edge(10, alice_idx, bob_idx); let edge2 = graph.add_edge(20, bob_idx, charlie_idx); // Query graph information println!("Graph has {} nodes and {} edges", graph.len_nodes(), graph.len_edges()); // Access data using indices println!("Node data: {}", graph.node(alice_idx)); println!("Edge weight: {}", graph.edge(edge1)); // Iterate over all data for node_data in graph.nodes() { println!("Node: {}", node_data); } // Use algorithms directly let components: Vec<_> = gotgraph::algo::tarjan(&graph).collect(); println!("Found {} strongly connected components", components.len());use gotgraph::prelude::*; let mut graph: VecGraph<i32, &str> = VecGraph::default(); // Add nodes and edges in a scoped context graph.scope_mut(|mut ctx| { let n1 = ctx.add_node(42); let n2 = ctx.add_node(100); ctx.add_edge("connects", n1, n2); // Access data within the same scope println!("Node 1: {}", ctx.node(n1)); println!("Node 2: {}", ctx.node(n2)); });We provide scope() and scope_mut() to create a scope, which determines the lifetime of all NodeIx and EdgeIx. It ensures that all existing NodeIx or EdgeIx are pointing valid nodes or edges, without any runtime check.
This prevent some use-after-free bugs, which frequently occures in practical graph operation.
Node and edge indices are strongly typed and cannot be mixed between different graphs or scopes, preventing common indexing errors.
The safety features are enforced at compile time and have no runtime overhead. The generated code is as efficient as unsafe alternatives.
GotGraph provides competitive performance compared to other graph libraries.
- GotGraph(direct) : use gotgraph with runtime check
- GotGraph(scoped) : use gotgraph with compile-time check (safe)
- petgraph(DiGraph) : use unsafe operation of petgraph
- petgraph(Scoped) : use safe operation of petgraph
The benchmarks demonstrate that GotGraph's scoped operations provide competitive performance while maintaining compile-time safety guarantees. In traversal operations, GotGraph shows particularly strong performance characteristics.
use gotgraph::prelude::*; let mut graph: VecGraph<&str, i32> = VecGraph::default(); graph.scope_mut(|mut ctx| { let alice = ctx.add_node("Alice"); let bob = ctx.add_node("Bob"); let charlie = ctx.add_node("Charlie"); // Add weighted edges ctx.add_edge(10, alice, bob); ctx.add_edge(20, bob, charlie); ctx.add_edge(5, alice, charlie); // Query the graph println!("Graph has {} nodes and {} edges", ctx.len_nodes(), ctx.len_edges()); // Iterate over outgoing edges for edge_tag in ctx.outgoing_edge_indices(alice) { let weight = ctx.edge(edge_tag); let [from, to] = ctx.endpoints(edge_tag); println!("Edge from {} to {} with weight {}", ctx.node(from), ctx.node(to), weight); } });use gotgraph::algo::tarjan; use gotgraph::prelude::*; let mut graph: VecGraph<&str, ()> = VecGraph::default(); // Build a graph with cycles graph.scope_mut(|mut ctx| { let a = ctx.add_node("A"); let b = ctx.add_node("B"); let c = ctx.add_node("C"); ctx.add_edge((), a, b); ctx.add_edge((), b, c); ctx.add_edge((), c, a); // Creates a cycle }); // Find strongly connected components let components: Vec<_> = tarjan(&graph).collect(); println!("Found {} strongly connected components", components.len());