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

To efficiently traverse the graph in codebase-memory-mcp, use the O(1) iterator macros defined in 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, 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, 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.

#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.

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.

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:

#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 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 demonstrates these patterns when building the CALLS edge type, while 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.
• 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 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. 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 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.

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