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

> Discover how VelesDB tackles graph traversal with efficient BFS and DFS in pure Rust. Explore configurable options and multi-platform support for your graph database needs.

- Repository: [Wiscale/velesdb](https://github.com/cyberlife-coder/velesdb)
- Tags: deep-dive
- Published: 2026-02-28

---

**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`](https://github.com/cyberlife-coder/velesdb/blob/main/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.

```rust
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`](https://github.com/cyberlife-coder/velesdb/blob/main/traversal.rs)).

### Safety Limits and Configuration

Unbounded traversals are automatically capped at `SAFETY_MAX_DEPTH = 100` (lines 22-28 of [`traversal.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/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`](https://github.com/cyberlife-coder/velesdb/blob/main/crates/velesdb-server/src/handlers/graph/service.rs). The `GraphService` translates request parameters into `TraversalConfig` instances and executes the core algorithms under read locks.

```rust
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`](https://github.com/cyberlife-coder/velesdb/blob/main/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.

```rust
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`](https://github.com/cyberlife-coder/velesdb/blob/main/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

```rust
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

```rust
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

```javascript
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`](https://github.com/cyberlife-coder/velesdb/blob/main/crates/velesdb-core/src/collection/graph/traversal.rs).
- The architecture extends seamlessly from server-side Rust ([`service.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/service.rs)) to WebAssembly clients ([`graph.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/graph.rs)) and parallel query executors ([`parallel_traversal/traverser.rs`](https://github.com/cyberlife-coder/velesdb/blob/main/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`](https://github.com/cyberlife-coder/velesdb/blob/main/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`](https://github.com/cyberlife-coder/velesdb/blob/main/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.