# How to Efficiently Traverse the Graph in codebase-memory-mcp

> Efficiently traverse the graph in codebase-memory-mcp using O(1) iterator macros like CBM_GRAPH_BUFFER_FOR_EACH_NODE. Implement DFS or BFS on these cache-friendly primitives for optimal performance.

- Repository: [Martin Vogel/codebase-memory-mcp](https://github.com/DeusData/codebase-memory-mcp)
- Tags: how-to-guide
- Published: 2026-07-05

---

**To efficiently traverse the graph in codebase-memory-mcp, use the O(1) iterator macros defined in [`src/graph_buffer/graph_buffer.h`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/graph_buffer/graph_buffer.h)—`CBM_GRAPH_BUFFER_FOR_EACH_NODE` for linear node scans and `CBM_GRAPH_BUFFER_FOR_EACH_OUT_EDGE` for adjacency walks—then implement DFS or BFS on top of these cache-friendly primitives.**

The `graph_buffer` module serves as the core in-memory data structure for **codebase-memory-mcp**, storing call graphs, dependency graphs, and analysis results as compact adjacency lists. Efficient traversal is critical because the graph may contain millions of nodes and edges, and the module provides zero-overhead iterator macros that expand to simple `for` loops over contiguous struct arrays.

## Understanding the Graph Buffer Architecture

The graph buffer uses a dense, cache-friendly layout that maps node IDs directly to array indices, enabling O(1) random access and linear traversal costs proportional to the number of visited elements.

### Node and Edge Storage

Nodes (representing functions, packages, files) and edges (representing CALLS, IMPORTS) are stored in contiguous memory blocks. In [`src/graph_buffer/graph_buffer.h`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/graph_buffer/graph_buffer.h), the `cbm_graph_buffer` struct maintains dense arrays for `nodes` and `edges`, with adjacency lists tracking outgoing and incoming connections. This layout ensures that iterating over a node's neighbors touches only contiguous memory regions, minimizing cache misses.

### The Iterator Macro Design

The module exposes iterator macros rather than function callbacks to eliminate call overhead. As implemented in [`src/graph_buffer/graph_buffer.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/graph_buffer/graph_buffer.c), `CBM_GRAPH_BUFFER_FOR_EACH_NODE` expands to a plain `for` loop over the dense nodes array, while `CBM_GRAPH_BUFFER_FOR_EACH_OUT_EDGE` and `CBM_GRAPH_BUFFER_FOR_EACH_IN_EDGE` walk the adjacency lists stored in the `edges` vector. These macros access data directly from the underlying arrays without indirection.

## Linear Traversal with Node Iterators

For full-graph analysis or exporting data, iterate over all nodes in storage order. This approach guarantees **O(N)** complexity and optimal cache utilization.

```c
#include "graph_buffer.h"

cbm_graph_buffer *gb = cbm_graph_buffer_new();

/* Populate via cbm_graph_buffer_add_node() ... */

CBM_GRAPH_BUFFER_FOR_EACH_NODE(gb, nid, node) {
    printf("Node %zu – kind=%s name=%s\n",
           nid,
           node->kind,               /* e.g., "Function", "Package" */
           node->name);
}

```

The macro expands to `for (size_t i = 0; i < gb->node_count; ++i)`, making the walk linear and branch-predictor friendly.

## Walking Adjacency Lists with Edge Iterators

When analyzing relationships (e.g., finding all functions called by a specific routine), use the directed edge iterators to traverse only relevant connections.

```c
size_t start_nid = 42;  /* ID of the node to explore */

CBM_GRAPH_BUFFER_FOR_EACH_OUT_EDGE(gb, start_nid, eid, edge) {
    printf("Edge %zu → %zu (type=%s)\n",
           start_nid,
           edge->target,
           edge_type_name(edge->type));
}

```

This iterator reads directly from `gb->out_edges`, visiting only the edges attached to `start_nid` without scanning unrelated graph regions.

## Implementing Depth-First Search (DFS)

Because node IDs are stable integers, you can implement classic graph traversals on top of the primitives. The following recursive DFS uses the out-edge iterator to explore the CALLS graph, achieving **O(V + E)** total work.

```c
static void dfs(cbm_graph_buffer *gb, size_t nid,
                bool *visited)
{
    visited[nid] = true;
    printf("Visit %zu (%s)\n", nid, gb->nodes[nid].name);

    CBM_GRAPH_BUFFER_FOR_EACH_OUT_EDGE(gb, nid, eid, edge) {
        if (!visited[edge->target]) {
            dfs(gb, edge->target, visited);
        }
    }
}

/* Usage */
size_t n = gb->node_count;
bool *visited = calloc(n, sizeof(bool));
dfs(gb, 0, visited);  /* Start from root node 0 */
free(visited);

```

The recursion depth is bounded by the longest call chain, and each edge is examined exactly once.

## Parallel Breadth-First Search (BFS)

The adjacency-list layout enables lock-free parallel traversal. Each worker thread processes a contiguous range of node IDs, and the contiguous edge storage allows safe concurrent reads. The following example partitions the node space across `WORKERS` threads:

```c
#include <pthread.h>
#include <stdatomic.h>
#define WORKERS 4

typedef struct {
    cbm_graph_buffer *gb;
    size_t            start;
    size_t            end;
    atomic_bool      *global_visited;
} bfs_worker_t;

void *bfs_worker(void *arg) {
    bfs_worker_t *w = arg;
    for (size_t i = w->start; i < w->end; ++i) {
        if (!atomic_load(&w->global_visited[i])) continue;

        CBM_GRAPH_BUFFER_FOR_EACH_OUT_EDGE(w->gb, i, eid, edge) {
            if (!atomic_exchange(&w->global_visited[edge->target], true)) {
                /* Enqueue edge->target for next BFS layer */
            }
        }
    }
    return NULL;
}

/* Setup and launch */
size_t per = (gb->node_count + WORKERS - 1) / WORKERS;
pthread_t th[WORKERS];
bfs_worker_t ws[WORKERS];
atomic_bool *visited = calloc(gb->node_count, sizeof(atomic_bool));
atomic_store(&visited[0], true);  /* Start from node 0 */

for (int i = 0; i < WORKERS; ++i) {
    ws[i] = (bfs_worker_t){
        .gb = gb,
        .start = i * per,
        .end = (i + 1) * per < gb->node_count ? (i + 1) * per : gb->node_count,
        .global_visited = visited
    };
    pthread_create(&th[i], NULL, bfs_worker, &ws[i]);
}
for (int i = 0; i < WORKERS; ++i) pthread_join(th[i], NULL);
free(visited);

```

Atomic operations on the `visited` bitmap prevent duplicate processing without mutex contention on the graph structure itself.

## Performance Characteristics

The traversal implementation in [`src/graph_buffer/graph_buffer.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/graph_buffer/graph_buffer.c) offers specific performance guarantees:

- **O(1) node access**: Direct array indexing via node ID eliminates hash lookups during traversal.
- **Cache-friendly iteration**: The `CBM_GRAPH_BUFFER_FOR_EACH_NODE` macro walks the dense `nodes` array sequentially, maximizing prefetch efficiency.
- **O(1) edge retrieval**: Adjacency lists store edge indices in contiguous blocks, making neighbor access constant-time.
- **Parallelizable**: The read-only nature of edge data during traversal allows thread-safe concurrent walks without locks.

Real-world usage in [`src/pipeline/pass_calls.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/pipeline/pass_calls.c) demonstrates these patterns when building the CALLS edge type, while [`tests/test_vmem.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/tests/test_vmem.c) provides a minimal test harness verifying correct iteration semantics.

## Summary

- **Use `CBM_GRAPH_BUFFER_FOR_EACH_NODE`** for full-graph linear scans over [`src/graph_buffer/graph_buffer.h`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/graph_buffer/graph_buffer.h).
- **Use `CBM_GRAPH_BUFFER_FOR_EACH_OUT_EDGE`** and `CBM_GRAPH_BUFFER_FOR_EACH_IN_EDGE`** for directed adjacency walks without scanning the entire edge set.
- **Implement DFS/BFS** on top of these macros to achieve **O(V + E)** complexity with minimal overhead.
- **Leverage parallel traversal** by partitioning node ID ranges across threads, relying on atomic bitmaps for synchronization.
- **Reference `cbm_graph_buffer_new()` and `cbm_graph_buffer_add_edge()`** in [`src/graph_buffer/graph_buffer.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/graph_buffer/graph_buffer.c) to construct the graph before traversing.

## Frequently Asked Questions

### What is the time complexity of traversing the graph in codebase-memory-mcp?

Traversal runs in **O(V + E)** time for complete walks (visiting every node and edge) or **O(1)** per element accessed via the iterator macros. The `CBM_GRAPH_BUFFER_FOR_EACH_NODE` macro touches each node exactly once in linear time, while the edge iterators examine each edge once when walking adjacency lists.

### How do I traverse only incoming edges to a specific node?

Use the `CBM_GRAPH_BUFFER_FOR_EACH_IN_EDGE` macro defined in [`src/graph_buffer/graph_buffer.h`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/graph_buffer/graph_buffer.h). It functions identically to the out-edge iterator but walks the incoming adjacency list stored for the node ID, allowing you to find all callers or importers of a specific symbol.

### Can I modify the graph while traversing it?

No, the iterator macros do not support concurrent modification. If you need to add nodes or edges via `cbm_graph_buffer_add_node()` or `cbm_graph_buffer_add_edge()` during traversal, first collect the required changes in a temporary structure, then apply them after the iteration completes to avoid reallocating the underlying arrays while pointers are being dereferenced.

### Is the graph_buffer thread-safe for parallel reads?

Yes, the storage layout in [`src/graph_buffer/graph_buffer.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/graph_buffer/graph_buffer.c) permits lock-free parallel reads. Multiple threads can simultaneously use `CBM_GRAPH_BUFFER_FOR_EACH_OUT_EDGE` on different node ranges, as demonstrated in the parallel BFS example, provided writes (graph construction) are complete before traversal begins. Use atomic operations only for shared mutable state like visited bitmaps, not for the graph structure itself.