# Safegraph - A graph manipulation library with fully type-safe, zero-cost, stable graph APIs [![Latest Version]][crates.io] [![Documentation]][docs.rs] [![GitHub Actions]][actions]
[Latest Version]: https://img.shields.io/crates/v/safegraph.svg
[crates.io]: https://crates.io/crates/safegraph
[Documentation]: https://img.shields.io/docsrs/safegraph
[docs.rs]: https://docs.rs/safegraph/latest/
[GitHub Actions]: https://github.com/yasuo-ozu/safegraph/actions/workflows/rust.yml/badge.svg
[actions]: https://github.com/yasuo-ozu/safegraph/actions/workflows/rust.yml
Safegraph is a graph library focused on type-safe, stable graph manipulation APIs.
It prevents common indexing mistakes using Rust's type system and zero-cost abstractions.
In this library, "stability" means an index keeps referring to the same logical
node or edge after it is obtained. Many graph libraries break this guarantee when
removing nodes or edges by compacting internal arrays, which can invalidate old indices.
```rust
use safegraph::graph::Graph;
use safegraph::VecGraph;
let g: VecGraph<u32, u32> = safegraph::graph!(
{0} -- {10} --> {1},
{1} -- {11} --> {2},
);
assert_eq!(g.len_node(), 4);
assert_eq!(g.len_edge(), 2);
```
Safegraph provides two main graph manipulation interfaces:
## scoped interface
This API provides stable indices inside a lexical scope. It uses a GhostCell-like
lifetime pattern so node/edge indices cannot escape their valid context. This gives
compile-time safety without runtime index validation overhead.
```rust
use safegraph::BTreeGraph;
use safegraph::graph::capability::UniqueEdge;
use safegraph::graph::Graph;
let g: BTreeGraph<u32, u32> = safegraph::graph!(
{0} -- {10} --> {1},
);
assert_eq!(*ctx.edge(e0), 10);
});
```
`scope_mut` allows mutation inside a scope. Combined with `graph!`, you can
insert nodes/edges and remove them with compile-time index safety:
```rust
use safegraph::graph::Graph;
use safegraph::VecGraph;
let mut g = VecGraph::<u32, u32>::default();
g.scope_mut(|mut ctx| {
safegraph::graph!(
&mut *ctx =>
n0 {0} -- {10} --> n1 {1} -- e1 {11} --> n2 {2},
);
ctx.remove_nodes_edges([n1], [e1]);
});
assert_eq!(g.len_node(), 2);
assert_eq!(g.len_edge(), 0);
```
## `stabilize()` interface
This API converts a graph into a tombstone-versioned stable wrapper. It preserves
index identity across mutations and validates index availability at runtime.
```rust
use safegraph::graph::Graph;
use safegraph::VecGraph;
let mut g = VecGraph::<(i64, u32), (i64, u32)>::default().stabilize();
safegraph::graph!(
&mut g =>
n0 {(0, 1)} -- {(0, 10)} --> n1 {(0, 2)},
);
g.remove_node(n0);
assert!(!g.contains_node_index(n0));
assert!(g.contains_node_index(n1));
let n2 = g.insert_node((0, 3)).unwrap();
assert!(g.contains_node_index(n2));
```
### `graph!` Macro
`graph!` supports two modes:
1. Expression mode (no input graph):
- `let g = graph!( ... );`
- Builds and returns a new graph (`Default::default()` + insertions).
- No `StableNode`/`StableEdge` assertion is emitted.
2. Statement mode (with input graph):
- `graph!(input_graph_expr => ...);`
- Mutates the provided graph expression in place.
- Does not return the graph.
- Exports named node/edge bindings (`ident` / `ident {expr}`) into the caller scope.
- Emits `StableNode` / `StableEdge` assertions when named node/edge bindings are used.
Examples:
```rust
use safegraph::VecGraph;
use safegraph::graph::Graph;
// Expression mode: returns graph value
let g: VecGraph<u32, u32> = safegraph::graph!(
{0} -- {10} --> {1},
{1} -- {11} --> {2},
);
assert_eq!(g.nodes().count(), 4);
```
```rust
use safegraph::graph::Graph;
use safegraph::VecGraph;
// Statement mode: mutates existing graph and exports bound idents
let mut g = VecGraph::<(i64, u32), (i64, u32)>::default().stabilize();
safegraph::graph!(
&mut g =>
a {(0, 1)} -- e {(0, 10)} --> b {(0, 2)}
);
assert_eq!(*g.node(a), (0, 1));
assert_eq!(*g.edge(e), (0, 10));
```
`ident {expr}` rule:
- You can specify both a binding name and an explicit payload expression.
- The same node/edge ident must not specify `{expr}` more than once in one macro call.
## Core Concepts
### Stability
In safegraph, **stability** means:
- `StableNode`: a `NodeIx` keeps referring to the same logical node during the lifetime.
- `StableEdge`: an `EdgeIx` keeps referring to the same logical edge during the lifetime.
Without stability, indices are *unstable*: after insertion/removal, previously saved indices may no longer be valid, or refers different nodes / edges from it originally refers.
Unstable graph example:
```rust
use safegraph::graph::Graph;
use safegraph::VecGraph;
let mut g = VecGraph::<u32, u32>::default();
let n = unsafe { g.insert_node_unchecked(1).unwrap() };
g.remove_node(n);
assert!(!g.contains_node_index(n)); // old index is invalid
g.push(2); // insert another node
assert_eq!(g.node(n), &2); // refering another node
```
Stable wrapper example:
```rust
use safegraph::graph::Graph;
use safegraph::VecGraph;
let mut g = VecGraph::<u32, u32>::default().stabilize();
let n = g.insert_node(1).unwrap();
g.remove_node(n);
assert!(!g.contains_node_index(n)); // removed generation is invalid
let n2 = g.insert_node(2).unwrap();
assert!(g.contains_node_index(n2));
assert_eq!(*g.node(n2), 2); // new generation points to new payload
```
This is why some APIs/macros require `StableNode` / `StableEdge`: they need indices that remain meaningful under mutation.
## Usage Examples
### Creating and Manipulating Graphs
```rust
use safegraph::graph::Graph;
use safegraph::BTreeGraph;
let mut graph: BTreeGraph<&str, i32> = BTreeGraph::default();
graph.insert_node("Alice").unwrap();
graph.insert_node("Bob").unwrap();
graph.insert_node("Charlie").unwrap();
// Add weighted edges
graph.insert_edge(10, [&"Alice", &"Bob"]).unwrap();
graph.insert_edge(20, [&"Bob", &"Charlie"]).unwrap();
graph.insert_edge(5, [&"Alice", &"Charlie"]).unwrap();
// Query the graph
assert_eq!(graph.len_node(), 3);
assert_eq!(graph.len_edge(), 3);
// Iterate over outgoing edges
for edge_tag in graph.edge_indices_from(&"Alice") {
let weight = graph.edge(edge_tag);
let [from, to] = graph.endpoints(edge_tag);
println!("Edge from {} to {} with weight {}", graph.node(from), graph.node(to), weight);
}
```
### Using Graph Algorithms
```rust
use safegraph::algo::connectivity::tarjan_scc;
use safegraph::algo::shortest_path::dijkstra;
use safegraph::algo::toposort::toposort;
use safegraph::BTreeGraph;
use safegraph::graph::Graph;
let mut graph = BTreeGraph::<&str, &str>::default();
graph.insert_node("A").unwrap();
graph.insert_node("B").unwrap();
graph.insert_node("C").unwrap();
graph.insert_edge("A->B", [&"A", &"B"]).unwrap();
graph.insert_edge("B->C", [&"B", &"C"]).unwrap();
graph.insert_edge("C->A", [&"C", &"A"]).unwrap();
// Find strongly connected components
let sccs: Vec<_> = tarjan_scc(&graph).collect();
println!("Found {} SCCs", sccs.len());
// Topological sort (returns Err for cyclic graphs)
assert!(toposort(&graph).is_err());
// Shortest paths