Louvain Community Detection Algorithm Implementation for Functional Modules in Codebase Memory

Codebase Memory detects functional modules using a Leiden-enhanced Louvain community detection algorithm implemented in C within 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 and used throughout the pipeline.

Edge Representation

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

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:

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.

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:

// 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:

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

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	API declarations for cbm_louvain, cbm_louvain_edge_t, and cbm_louvain_result_t
src/store/store.c (lines 4970-5070)	Core Leiden phases: leiden_move, leiden_refine, leiden_aggregate
src/store/store.c (lines 5084-5113)	Leiden orchestration in cbm_leiden()
src/store/store.c (lines 5184-5187)	Public wrapper cbm_louvain()
src/store/store.c (lines 5317-5742)	Graph construction via arch_clusters()
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) 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 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 uses dense arrays and pointer arithmetic for cache efficiency, making it suitable for analyzing large codebases with thousands of functions and methods.

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