How CodeGraph Detects Circular Dependencies Using Depth-First Search

CodeGraph detects circular dependencies by modeling source files as nodes and import statements as directed edges, then executing a depth‑first search (DFS) algorithm that monitors the recursion stack to identify cycles in the dependency graph.

CodeGraph is an open‑source analysis tool that maps codebase architecture into a queryable graph structure stored in SQLite. The mechanism for detecting circular dependencies relies entirely on graph theory, treating the codebase as a directed graph where cycles in the graph directly represent circular import relationships.

Modeling the Codebase as a File‑Level Dependency Graph

CodeGraph constructs a file‑level dependency graph from import edges persisted in its SQLite database. Each source file becomes a node, and a directed edge labeled imports connects a file to every other file it directly imports. This abstraction removes language‑specific complexity—all relationships are reduced to nodes and edges before cycle detection begins.

Because the underlying data resides in SQLite, the entire graph loads into memory during analysis. This in‑memory approach enables fast traversal without database round‑trips while scaling linearly with the number of files and import relationships.

The Cycle Detection Algorithm in GraphQueryManager

The core circular dependency logic resides in GraphQueryManager.findCircularDependencies() within src/graph/queries.ts at lines 55‑96. The method implements a standard DFS cycle‑detection algorithm optimized for dependency analysis.

The algorithm distinguishes between two tracking states:

• visited: Files that have been completely explored and confirmed not to lead to cycles from the current starting point.
• recursionStack: Files currently in the active DFS call stack, representing the path being traversed.

When the DFS encounters a file already present in recursionStack, it has found a cycle. The algorithm records the cycle by slicing the current path from the first occurrence of that file to the end.

Step‑by‑Step Implementation Details

1. Initialization: The method first retrieves all file nodes via this.queries.getAllFiles() to ensure every potential starting point is examined.

2. DFS Traversal: For each unvisited file, the helper function dfs(filePath, []) executes. The second argument represents the current path array.

3. Cycle Identification: Inside the DFS, when recursionStack contains the current filePath, the algorithm locates the cycle start using path.indexOf(filePath) and pushes the cycle slice onto the results array.

4. Dependency Expansion: The DFS explores outgoing edges through this.getFileDependencies(filePath) (lines 82‑90), which queries the database for all imports edges originating from the current file and returns the target file paths.

5. Result Compilation: After processing all files, the method returns the cycles array—each element being a sequence of file paths forming a circular dependency chain.

Traversing File Dependencies

The this.getFileDependencies(filePath) method acts as the graph edge provider. It abstracts the SQLite queries defined in src/db/queries.ts, fetching all outgoing imports relationships for a given file node. This separation keeps the cycle detection algorithm decoupled from database implementation details, allowing the DFS to treat the graph as a pure adjacency list.

Practical Usage Example

The following TypeScript example demonstrates how to initialize CodeGraph, index a repository, and retrieve circular dependencies:

import { CodeGraph } from 'codegraph';

// Initialize CodeGraph for a project
const cg = new CodeGraph();
await cg.init('/path/to/project');

// Index the repository (or load existing index)
await cg.indexAll();

// Obtain the GraphQueryManager instance
const queryMgr = cg.graph; 

// Detect circular dependencies
const cycles = queryMgr.findCircularDependencies();

if (cycles.length === 0) {
  console.log('✅ No circular imports detected.');
} else {
  console.log('🔁 Circular dependencies found:');
  cycles.forEach((cycle, i) => {
    console.log(`Cycle ${i + 1}: ${cycle.join(' → ')}`);
  });
}

Running this snippet outputs detected cycles as file path sequences:

Cycle 1: src/a.ts → src/b.ts → src/c.ts → src/a.ts

Summary

• Graph Model: CodeGraph treats files as nodes and imports as directed edges, storing this structure in SQLite for efficient lookup.
• Algorithm: The findCircularDependencies() method in src/graph/queries.ts implements DFS cycle detection using a recursionStack to track the current traversal path.
• Cycle Detection: A cycle is identified when a file appears in the current recursionStack, and the algorithm extracts the cycle sequence using path.indexOf(filePath).
• Scalability: Because the detection runs in memory against the loaded graph, performance scales with the number of files and import relationships rather than codebase complexity.
• API Access: Developers invoke detection through GraphQueryManager.findCircularDependencies() after initializing and indexing a project.

Frequently Asked Questions

How does CodeGraph represent dependencies internally?

CodeGraph represents dependencies as a directed graph where each source file is a node and each import statement creates a directed edge labeled imports. This model is stored in SQLite and mapped to an in‑memory graph structure during analysis, allowing algorithms to traverse relationships without re‑parsing source code.

What algorithm does CodeGraph use to detect circular dependencies?

CodeGraph uses a depth‑first search (DFS) algorithm with cycle tracking. The implementation maintains a recursionStack array representing the current traversal path. When the search encounters a file already present in this stack, it identifies a cycle and records the sequence of files from the first occurrence to the current position.

Where is the circular dependency detection logic located in the codebase?

The primary logic resides in src/graph/queries.ts within the GraphQueryManager class, specifically the findCircularDependencies() method spanning lines 55‑96. This method coordinates with this.getFileDependencies() (lines 82‑90) and the database query layer in src/db/queries.ts to retrieve graph edges.

Does CodeGraph's circular dependency detection scale to large repositories?

Yes, the detection scales linearly with the number of files and import relationships. Because CodeGraph loads the dependency graph into memory from SQLite and performs cycle detection using standard DFS—an O(V + E) operation where V is files and E is imports—it remains performant for large codebases, though memory usage increases with graph size.

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