Safegraph - A graph manipulation library with fully type-safe, zero-cost, stable graph APIs

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

use safegraph::BTreeGraph;
use safegraph::graph::capability::UniqueEdge;
use safegraph::graph::Graph;

let g: BTreeGraph<u32, u32> = safegraph::graph!(
    {0} -- {10} --> {1},
);
g.scope(|ctx| {
    let e0 = ctx.edge_index(&10).unwrap();
    assert_eq!(*ctx.edge(e0), 10);
});

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

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

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

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

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

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

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);
}

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
let dists = dijkstra(&graph, &"A", None, |_| 1u32);