Skip to content
HeliosDB HeliosDB Lite

Graph Engine Tutorial

Graph Engine Tutorial

Available since: v3.6.0 (2026-04-15) Build: default — no feature flag required Module: heliosdb_lite::graph (src/graph/) SQL functions (declared, descriptors only): graph_bfs, graph_shortest_path, graph_a_star, graph_neighbors

UVP

Adjacency-list graphs without a separate database. The graph module gives Lite a property-graph layer with directed, typed, optionally weighted edges; an EdgeStore trait for backend-agnostic storage; and three traversal algorithms — BFS with bounded depth, Dijkstra with negative-weight rejection, and A* with a pluggable admissible heuristic. Cheap to embed in any existing Lite application — the GraphStore facade and InMemoryEdgeStore are both Arc-cloneable, thread-safe, and need zero configuration. SQL bindings ship as descriptors today; a persistent EdgeStore wires them to the parser in a follow-up.

Prerequisites

  • HeliosDB Lite v3.6+ (heliosdb-lite = "3.6" in Cargo.toml)
  • Rust 1.75 or newer
  • About 15 minutes

1. Add the Dependency

[dependencies]
heliosdb-lite = "3.6"

The graph module is in the default build. No extra crates, no feature flags.

2. Build a Graph

The fastest way to start is the GraphStore::in_memory() facade, which wraps an InMemoryEdgeStore (DashMap-backed adjacency lists) in an Arc.

use heliosdb_lite::graph::{Edge, GraphStore};


fn main() {
    let g = GraphStore::in_memory();


    // Directed unweighted edges (weight defaults to 1.0).
    g.add_edge(Edge::new(1, 2, "FOLLOWS"));
    g.add_edge(Edge::new(2, 3, "FOLLOWS"));
    g.add_edge(Edge::new(1, 3, "FOLLOWS"));


    println!("nodes:  {}", g.node_count());     // 3
    println!("edges:  {}", g.edge_count());     // 3
    println!("out(1): {}", g.out_degree(1));    // 2
    println!("in(3):  {}", g.in_degree(3));     // 2
}

Edge is the only payload type:

pub struct Edge {
    pub from: u64,        // NodeId is a type alias for u64
    pub to: u64,
    pub label: String,    // "FOLLOWS", "WROTE", whatever you want
    pub weight: f32,      // default 1.0; used by Dijkstra/A*
}

For weighted graphs, use Edge::with_weight:

g.add_edge(Edge::with_weight(1, 2, "ROAD", 3.5));

3. BFS — Reachable Nodes With Bounded Depth

Layer-by-layer traversal. Each node is visited exactly once; pass u32::MAX for an unbounded walk.

use heliosdb_lite::graph::{Edge, GraphStore, bfs};


let g = GraphStore::in_memory();
g.add_edge(Edge::new(1, 2, "x"));
g.add_edge(Edge::new(2, 3, "x"));
g.add_edge(Edge::new(3, 4, "x"));


// Full traversal.
let r = bfs(g.backend().as_ref(), 1, u32::MAX);
assert_eq!(r.order, vec![1, 2, 3, 4]);
assert_eq!(r.depth.get(&4), Some(&3));


// Bounded — stop after one hop.
let r = bfs(g.backend().as_ref(), 1, 1);
assert_eq!(r.order, vec![1, 2]);

BfsResult exposes both fields you need:

pub struct BfsResult {
    pub order: Vec<u64>,                 // visit order
    pub depth: HashMap<u64, u32>,        // hops from source
}

4. Dijkstra — Single-Source Shortest Paths

use heliosdb_lite::graph::{Edge, GraphStore, dijkstra};
use heliosdb_lite::graph::traverse::reconstruct_path;


let g = GraphStore::in_memory();
// Diamond: 1->2->4 (cost 1+1) vs 1->3->4 (cost 5+1).
g.add_edge(Edge::with_weight(1, 2, "x", 1.0));
g.add_edge(Edge::with_weight(2, 4, "x", 1.0));
g.add_edge(Edge::with_weight(1, 3, "x", 5.0));
g.add_edge(Edge::with_weight(3, 4, "x", 1.0));


let result = dijkstra(g.backend().as_ref(), 1).expect("non-negative weights");
let path   = reconstruct_path(&result, 1, 4).expect("path exists");


assert_eq!(path.nodes, vec![1, 2, 4]);
assert!((path.cost - 2.0).abs() < 1e-6);

Dijkstra explicitly rejects negative weights — they break the algorithm’s correctness guarantee. The error tells you exactly which edge was offending so you can fix the data:

use heliosdb_lite::graph::{Edge, InMemoryEdgeStore, dijkstra};
use heliosdb_lite::graph::traverse::PathfindError;


let s = InMemoryEdgeStore::new();
s.add_edge(Edge::with_weight(1, 2, "x", -1.0));


match dijkstra(&s, 1) {
    Err(PathfindError::NegativeWeight { from, to, weight }) => {
        eprintln!("bad edge {from}->{to} weight {weight}");
    }
    other => panic!("expected NegativeWeight, got {other:?}"),
}

5. A* — Heuristic-Guided Search

A* is Dijkstra with a hint: a function that estimates the remaining cost from any node to the target. As long as your heuristic never over-estimates (admissible), A* still returns the optimal path while expanding fewer nodes.

use heliosdb_lite::graph::{Edge, GraphStore, a_star};


let g = GraphStore::in_memory();
g.add_edge(Edge::with_weight(1, 2, "x", 1.0));
g.add_edge(Edge::with_weight(2, 4, "x", 1.0));
g.add_edge(Edge::with_weight(1, 3, "x", 5.0));
g.add_edge(Edge::with_weight(3, 4, "x", 1.0));


// Trivial admissible heuristic: always 0.0 — degenerates to Dijkstra
// but proves the contract holds.
let path = a_star(g.backend().as_ref(), 1, 4, |_node| 0.0)
    .expect("path found");


assert_eq!(path.nodes, vec![1, 2, 4]);
assert!((path.cost - 2.0).abs() < 1e-6);

A real heuristic — for road networks, straight-line distance to the target; for grid worlds, Manhattan distance — typically explores 5–50× fewer nodes than Dijkstra at the same correctness.

6. Listing Neighbors

For UI walks, recommendation feeds, or traversal frontends, out_edges gives you the adjacency list directly. The graph::sql::neighbors helper packages it as (to, label, weight) triples — the shape the future SQL function will expose:

use heliosdb_lite::graph::{Edge, GraphStore};
use heliosdb_lite::graph::sql::neighbors;


let g = GraphStore::in_memory();
g.add_edge(Edge::with_weight(1, 2, "FOLLOWS", 0.5));
g.add_edge(Edge::with_weight(1, 3, "BLOCKS", 0.0));


for (to, label, weight) in neighbors(&g, 1) {
    println!("1 -[{label}, w={weight}]-> {to}");
}

7. Custom Backends — the EdgeStore Trait

Every traversal in the module operates on &dyn EdgeStore. To plug in your own storage (mmap’d file, RocksDB, etc.) implement the trait:

use heliosdb_lite::graph::{Edge, EdgeStore};


pub trait EdgeStore: Send + Sync {
    fn add_edge(&self, edge: Edge);
    fn remove_edges(&self, from: u64, to: u64) -> usize;
    fn out_edges(&self, node: u64) -> Vec<Edge>;
    fn in_edges(&self, node: u64) -> Vec<Edge>;
    fn node_count(&self) -> usize;
    fn edge_count(&self) -> usize;
    // out_degree / in_degree have default impls.
}

Then wrap your impl in a GraphStore:

use std::sync::Arc;
use heliosdb_lite::graph::{EdgeStore, GraphStore};


let custom: Arc<dyn EdgeStore> = Arc::new(MyBackend::open("./graph.dat")?);
let g = GraphStore::new(custom);

The crate ships TODOs for RocksDB and NativeBackend variants; both are gated behind the existing storage backend feature flags and are tracked for v3.7.

8. SQL Function Descriptors

graph::sql::declared_functions() returns the four SQL functions the module intends to register with the parser:

use heliosdb_lite::graph::sql::declared_functions;


for f in declared_functions() {
    println!("{}: {}", f.name, f.description);
}
// graph_bfs:           Breadth-first traversal: returns reachable node ids ordered by depth.
// graph_shortest_path: Dijkstra shortest path between two node ids.
// graph_a_star:        A* search with a user-supplied numeric heuristic column.
// graph_neighbors:     List immediate out-neighbours of a node.

Status (v3.6.0): the SQL function bindings ship as descriptors only. Wiring them into src/sql/functions.rs is intentionally deferred until at least one of the persistent EdgeStore variants (RocksDB or NativeBackend) is in place — otherwise the SQL functions would only see an ephemeral in-memory graph that is invisible to the relational engine. Today, drive graphs through the Rust API.

Where Next