# Louvain Community Detection Algorithm Implementation for Functional Modules in Codebase Memory

> Explore the Louvain community detection algorithm implementation in C for functional modules within Codebase Memory. Uncover how it clusters codebase elements based on call graph topology.

- Repository: [Martin Vogel/codebase-memory-mcp](https://github.com/DeusData/codebase-memory-mcp)
- Tags: deep-dive
- Published: 2026-07-08

---

**Codebase Memory detects functional modules using a Leiden-enhanced Louvain community detection algorithm implemented in C within [`src/store/store.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/store/store.c), clustering functions, methods, and classes based on call graph topology.**

The DeusData/codebase-memory-mcp repository provides an MCP (Memory-Cache-Proxy) server that analyzes codebases to identify functional modules—cohesive groups of functions and classes that work together. At the heart of this analysis lies a high-performance implementation of the Louvain community detection algorithm, enhanced with Leiden refinement phases, operating directly on the SQLite-backed graph store.

## Core Data Structures

The implementation defines lightweight C structures to represent graph edges and community assignments. These are declared in [`src/store/store.h`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/store/store.h) and used throughout the pipeline.

### Edge Representation

Each call relationship is stored as a pair of 64-bit node identifiers:

```c
typedef struct {
    int64_t src;
    int64_t dst;
} cbm_louvain_edge_t;          // Defined in src/store/store.h (lines 625-630)

```

### Result Mapping

After detection, each node maps to its assigned community:

```c
typedef struct {
    int64_t node_id;   // Original node id
    int     community; // Assigned community number
} cbm_louvain_result_t;       // Defined in src/store/store.h (lines 631-637)

```

## The Three-Stage Pipeline

The algorithm executes in three distinct phases orchestrated by `arch_clusters()` and `cbm_leiden()` in [`src/store/store.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/store/store.c).

### Stage 1: Graph Construction

The `arch_clusters()` function (lines 5317-5742) builds the functional module graph from the SQLite database:

1. **Node extraction** – Queries the `nodes` table for all entities labeled `Function`, `Method`, or `Class` (see SQL construction in lines 5230-5250)
2. **Edge extraction** – Fetches all `CALLS` edges where both endpoints exist in the node set (lines 5272-5399), populating an array of `cbm_louvain_edge_t` structures
3. **Index mapping** – Creates parallel arrays (`ids[]`, `names[]`, `qns[]`) to map database IDs to dense graph indices

### Stage 2: Leiden Community Detection

The `cbm_leiden()` function (lines 5084-5113) implements the Leiden algorithm, an enhancement over classic Louvain that guarantees well-connected communities. It iterates through three phases until convergence:

- **Local moving** (`leiden_move`): Reassigns each node to the neighboring community yielding maximum modularity gain
- **Refinement** (`leiden_refine`): Ensures each community is internally connected, merging sub-communities when necessary (implemented in lines 4970-5070)
- **Aggregation** (`leiden_aggregate`): Contracts each refined community into a super-node, building a coarser graph for the next iteration

These phases repeat until the partition stabilizes, optimizing the **modularity** metric at multiple scales.

### Stage 3: Public API and Resolution

The `cbm_louvain()` wrapper (lines 5184-5187) provides a simplified interface:

```c
// Wrapper fixes resolution to 1.0 (classic Louvain setting)
int cbm_louvain(const int64_t *nodes, int node_count,
                const cbm_louvain_edge_t *edges, int edge_count,
                cbm_louvain_result_t **out_results, int *out_count);

```

The `resolution` parameter controls community granularity—higher values yield more, smaller communities. The public API defaults to `1.0`, matching standard Louvain behavior. The function returns an array of `cbm_louvain_result_t` that the caller must free.

## Working with the Implementation

### High-Level Architecture Extraction

Most clients interact with the detection through `cbm_store_arch()`, which calls the Louvain pipeline internally to populate cluster metadata:

```c
#include "codebase_memory_mcp/store.h"

void find_modules(const cbm_store_t *store, const char *project) {
    cbm_architecture_info_t arch = {0};
    
    // cbm_store_arch calls arch_clusters() → cbm_louvain()
    if (cbm_store_arch(store, project, NULL, &arch) == CBM_STORE_OK) {
        for (int i = 0; i < arch.cluster_count; ++i) {
            const cbm_cluster_info_t *c = &arch.clusters[i];
            printf("Module %d (%d members, cohesion %.2f): %s\n",
                   c->id, c->members, c->cohesion,
                   c->label ? c->label : "-");
        }
        free(arch.clusters);
    }
}

```

### Direct Low-Level Access

For testing or custom graphs, call `cbm_louvain()` directly as implemented in [`tests/test_store_arch.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/tests/test_store_arch.c):

```c
int64_t nodes[] = {101, 102, 103, 104};
cbm_louvain_edge_t edges[] = {
    {101, 102},
    {102, 103},
    {101, 103},
    {103, 104}
};

cbm_louvain_result_t *result = NULL;
int count = 0;

int rc = cbm_louvain(nodes, 4, edges, 4, &result, &count);
if (rc == CBM_STORE_OK) {
    for (int i = 0; i < count; ++i) {
        printf("Node %ld → community %d\n", 
               result[i].node_id, result[i].community);
    }
    free(result);  // Caller owns the buffer
}

```

## Key Files and Locations

| File | Purpose |
|------|---------|
| [`src/store/store.h`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/store/store.h) | API declarations for `cbm_louvain`, `cbm_louvain_edge_t`, and `cbm_louvain_result_t` |
| [`src/store/store.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/store/store.c) (lines 4970-5070) | Core Leiden phases: `leiden_move`, `leiden_refine`, `leiden_aggregate` |
| [`src/store/store.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/store/store.c) (lines 5084-5113) | Leiden orchestration in `cbm_leiden()` |
| [`src/store/store.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/store/store.c) (lines 5184-5187) | Public wrapper `cbm_louvain()` |
| [`src/store/store.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/store/store.c) (lines 5317-5742) | Graph construction via `arch_clusters()` |
| [`tests/test_store_arch.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/tests/test_store_arch.c) (lines 882-949) | Unit tests: `louvain_basic`, `louvain_empty`, `louvain_single_node`, `louvain_converges` |

## Summary

- **Codebase Memory** implements a **Leiden-enhanced Louvain** algorithm in pure C within the SQLite store layer
- **Graph construction** in `arch_clusters()` extracts Function/Method/Class nodes and CALLS edges from the database
- **Three-phase detection** (`leiden_move`, `leiden_refine`, `leiden_aggregate`) optimizes modularity while guaranteeing connected communities
- **Default resolution** is fixed at `1.0` through the `cbm_louvain()` wrapper, matching classic Louvain behavior
- **Memory management**: The library returns heap-allocated results that the caller must free

## Frequently Asked Questions

### How does Codebase Memory handle disconnected components in the call graph?

The Leiden refinement phase (`leiden_refine` in [`src/store/store.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/store/store.c)) specifically ensures that each detected community forms a connected subgraph. If the algorithm assigns nodes to communities that would create disconnected components, the refinement step merges appropriate sub-communities to maintain internal connectivity, producing more meaningful functional modules than standard Louvain.

### What determines the number of communities detected?

The detection depends on two factors: the **resolution parameter** (fixed at `1.0` in `cbm_louvain`) and the **modularity optimization** convergence criteria. Higher resolution values produce more granular communities, while the default setting balances granularity with cohesion. The algorithm stops when aggregating communities no longer improves the modularity score.

### Can I use the Louvain implementation independently of the SQLite store?

Yes. While `arch_clusters()` handles graph construction from the database, the `cbm_louvain()` function accepts raw node arrays and edge lists, making it usable for any graph represented as `cbm_louvain_edge_t` structures. The unit tests in [`tests/test_store_arch.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/tests/test_store_arch.c) demonstrate this standalone usage with synthetic graphs.

### What is the computational complexity of the implementation?

The Leiden algorithm runs in **O(m)** time per iteration, where *m* is the number of edges (CALLS relationships), with the number of iterations typically small for real-world graphs. The C implementation in [`src/store/store.c`](https://github.com/DeusData/codebase-memory-mcp/blob/main/src/store/store.c) uses dense arrays and pointer arithmetic for cache efficiency, making it suitable for analyzing large codebases with thousands of functions and methods.