How VelesDB Handles Graph Traversal Using BFS and DFS: A Technical Deep Dive

VelesDB implements graph traversal as a pure-Rust, lock-free engine that provides iterative BFS and DFS algorithms with configurable depth limits, relationship filtering, and result capping across server, WebAssembly, and mobile platforms.

VelesDB is an open-source graph database that stores complex node-edge relationships and navigates them efficiently using native Rust implementations. This article examines how the cyberlife-coder/velesdb repository structures its VelesDB graph traversal capabilities, detailing the breadth-first search (BFS) and depth-first search (DFS) implementations found in the core library, HTTP service layer, and WebAssembly client bindings.

Core Traversal Engine in velesdb-core

The heart of VelesDB’s graph navigation resides in crates/velesdb-core/src/collection/graph/traversal.rs. This module defines a small, reusable API centered around the TraversalConfig struct, which holds min_depth, max_depth, limit, and optional relationship-type filters for variable-length path patterns.

BFS Implementation with VecDeque

The bfs_traverse function implements an iterative breadth-first search using a VecDeque for FIFO level-order processing. Unlike recursive approaches, this design handles massive graphs without stack overflow risks.

let mut visited = HashSet::new();        // O(1) “already seen” test
let mut queue   = VecDeque::new();       // FIFO for level order

visited.insert(source_id);
queue.push_back(BfsState { node_id: source_id, path: vec![], depth: 0 });

while let Some(state) = queue.pop_front() {
    if results.len() >= cfg.limit { break; }

    for edge in edge_store.get_outgoing(state.node_id) {
        // optional relationship‑type filter
        if !cfg.rel_types.is_empty() && !cfg.rel_types.contains(&edge.label().to_string()) {
            continue;
        }
        let target = edge.target();
        let new_depth = state.depth + 1;
        if new_depth > cfg.max_depth { continue; }

        // build the new path
        let mut new_path = state.path.clone();
        new_path.push(edge.id());

        // record the hit if it satisfies the depth window
        if new_depth >= cfg.min_depth {
            results.push(TraversalResult::new(target, new_path.clone(), new_depth));
        }

        // enqueue for the next level if we haven’t visited it yet
        if new_depth < cfg.max_depth && !visited.contains(&target) {
            visited.insert(target);
            queue.push_back(BfsState { node_id: target, path: new_path, depth: new_depth });
        }
    }
}

The algorithm guarantees termination via the visited HashSet, ensuring each node processes at most once. Depth-aware filtering (min_depth/max_depth) supports pattern matching like [*1..3], while early termination triggers once cfg.limit is reached.

DFS and Bidirectional Variants

For depth-first search, the engine swaps the queue for a stack (Vec), yielding results in depth-first order. The crate also provides bfs_traverse_reverse for following incoming edges and bfs_traverse_both, which merges forward and reverse BFS results while de-duplicating paths (lines 90-126 of traversal.rs).

Safety Limits and Configuration

Unbounded traversals are automatically capped at SAFETY_MAX_DEPTH = 100 (lines 22-28 of traversal.rs) to prevent runaway queries. Relationship-type filtering uses a HashSet<&str> for O(1) lookups, performed before edge expansion to minimize CPU overhead.

Server-Side HTTP API Implementation

The HTTP API exposes traversal through crates/velesdb-server/src/handlers/graph/service.rs. The GraphService translates request parameters into TraversalConfig instances and executes the core algorithms under read locks.

pub fn traverse_bfs(
    &self,
    collection_name: &str,
    source_id: u64,
    max_depth: u32,
    limit: usize,
    rel_types: &[String],
) -> Result<Vec<TraversalResultItem>, String> {
    let store = self.get_or_create_store(collection_name)?;
    let guard = store.read().map_err(|e| format!("Lock error: {e}"))?;

    // fast O(1) filter
    let rel_filter: HashSet<&str> = rel_types.iter().map(String::as_str).collect();

    let mut visited = HashSet::new();
    let mut queue   = VecDeque::new();
    visited.insert(source_id);
    queue.push_back((source_id, 0, Vec::new()));

    while let Some((node_id, depth, path)) = queue.pop_front() {
        if results.len() >= limit { break; }

        for edge in guard.get_outgoing(node_id) {
            if !rel_filter.is_empty() && !rel_filter.contains(edge.label()) { continue; }

            let target = edge.target();
            let new_depth = depth + 1;
            if new_depth > max_depth || visited.contains(&target) { continue; }
            visited.insert(target);

            let mut new_path = path.clone();
            new_path.push(edge.id());

            results.push(TraversalResultItem {
                target_id: target,
                depth: new_depth,
                path: new_path.clone(),
            });

            if new_depth < max_depth {
                queue.push_back((target, new_depth, new_path));
            }
        }
    }
    Ok(results)
}

The traverse_dfs endpoint follows an identical pattern but uses a stack instead of a queue, preserving the same safety caps and filtering logic.

WebAssembly Client Support

VelesDB compiles its traversal logic to WebAssembly for browser-based graph analytics. The WASM module in crates/velesdb-wasm/src/graph.rs re-exports bfs_traverse and dfs_traverse to JavaScript while maintaining a self-contained implementation to avoid bloating the binary.

pub fn dfs_traverse(
    &self,
    source_id: u64,
    max_depth: usize,
    limit: usize,
) -> Result<JsValue, JsValue> {
    let mut results = Vec::new();
    let mut visited = HashSet::new();
    let mut stack   = vec![(source_id, 0)];

    while let Some((node_id, depth)) = stack.pop() {
        if results.len() >= limit { break; }
        if visited.contains(&node_id) { continue; }
        visited.insert(node_id);

        if depth > 0 { results.push((node_id, depth)); }

        if depth < max_depth {
            // push neighbours in reverse order to preserve DFS order
            let neighbors: Vec<_> = self.get_outgoing(node_id)
                .into_iter()
                .filter(|e| !visited.contains(&e.target))
                .collect();
            for edge in neighbors.into_iter().rev() {
                stack.push((edge.target, depth + 1));
            }
        }
    }
    serde_wasm_bindgen::to_value(&results).map_err(|e| JsValue::from_str(&e.to_string()))
}

This implementation mirrors the server-side behavior, including the visited-set tracking and result limiting, ensuring consistent query semantics across platforms.

Parallel Traversal for Query Optimization

For multi-threaded workloads, crates/velesdb-core/src/collection/search/query/parallel_traversal/traverser.rs provides bfs_parallel and dfs_parallel variants. These functions reuse the core traversal logic while distributing edge expansion across threads, significantly improving performance for large-scale graph analytics.

Practical Usage Examples

Server-Side BFS via GraphService

use velesdb_server::handlers::graph::service::GraphService;

// Create a service (usually injected by the web server)
let svc = GraphService::new(state);

// Traverse up to depth 3, limit 50 results, only "knows" edges
let results = svc.traverse_bfs(
    "my_collection",
    42,                     // source node ID
    3,                      // max_depth
    50,                     // limit
    &["knows".to_string()], // relationship filter
).expect("traversal failed");

// Inspect one result
println!("Reached node {} at depth {}", results[0].target_id, results[0].depth);

Direct Core Library Usage

use velesdb_core::collection::graph::{
    bfs_traverse, TraversalConfig, EdgeStore,
};

// Assume `store` implements `EdgeStore`
let cfg = TraversalConfig::default()
    .with_max_depth(5)
    .with_limit(200)
    .with_rel_types(vec!["friend".into(), "colleague".into()]);

let results = bfs_traverse(&store, 7, &cfg);
println!("Found {} reachable nodes", results.len());

Browser-Based DFS with WebAssembly

import init, { Graph } from "./velesdb_wasm.js";

await init(); // loads the WASM module
const g = new Graph();

// …populate graph with `add_node` / `add_edge`…

// Depth-first traversal limited to 10 hops, max 100 results
const raw = g.dfs_traverse(1, 10, 100);
const results = JSON.parse(raw);
console.log(`Visited ${results.length} nodes`);

Summary

• VelesDB graph traversal relies on iterative (non-recursive) BFS and DFS implementations using VecDeque and Vec respectively, preventing stack overflows on deep graphs.
• The TraversalConfig system provides granular control over depth ranges, result limits, and relationship-type filtering via O(1) HashSet lookups.
• All traversal variants—including forward, reverse, and bidirectional BFS—share the core safety mechanisms in crates/velesdb-core/src/collection/graph/traversal.rs.
• The architecture extends seamlessly from server-side Rust (service.rs) to WebAssembly clients (graph.rs) and parallel query executors (parallel_traversal/traverser.rs).
• Hard caps at SAFETY_MAX_DEPTH = 100 and visited-set tracking guarantee termination and prevent infinite cycles in cyclic graphs.

Frequently Asked Questions

What is the difference between BFS and DFS in VelesDB?

BFS (bfs_traverse) uses a VecDeque to explore nodes level-by-level, guaranteeing the shortest path in unweighted graphs, while DFS uses a Vec stack to dive deep into branches before backtracking. Both implementations support identical configuration options for depth limits and relationship filtering, but BFS is preferred for shortest-path queries while DFS suits topological sorting or exhaustive path enumeration.

How does VelesDB prevent infinite loops during graph traversal?

VelesDB maintains a HashSet<u64> visited tracker that records processed node IDs before enqueueing or pushing to the stack. According to the source code in traversal.rs, the engine checks visited.contains(&target) before expansion, ensuring each node processes at most once regardless of graph cyclicity. Additionally, unbounded traversals are capped at SAFETY_MAX_DEPTH = 100 to prevent runaway queries.

Can I filter traversal results by specific relationship types?

Yes, VelesDB supports relationship-type filtering via the rel_types parameter in TraversalConfig. Both the core engine and server-side API convert these filters into HashSet<&str> for O(1) containment checks performed before edge expansion. This optimization prevents unnecessary node visits when traversing heterogeneous graphs with multiple edge labels.

Is VelesDB graph traversal implemented recursively or iteratively?

VelesDB implements all traversal algorithms iteratively using while loops with explicit VecDeque (BFS) or Vec (DFS) data structures. This design choice, evident in crates/velesdb-core/src/collection/graph/traversal.rs, eliminates stack overflow risks and enables the engine to handle graphs with millions of nodes and arbitrary depth within available memory constraints.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}