# How CodeGraph Detects Circular Dependencies Using Depth-First Search

> CodeGraph uses depth-first search and recursion stack monitoring to detect circular dependencies in your code graph, preventing complex import issues and improving maintainability.

- Repository: [Colby Mchenry/codegraph](https://github.com/colbymchenry/codegraph)
- Tags: how-to-guide
- Published: 2026-05-17

---

**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`](https://github.com/colbymchenry/codegraph/blob/main/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`](https://github.com/colbymchenry/codegraph/blob/main/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:

```typescript
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`](https://github.com/colbymchenry/codegraph/blob/main/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`](https://github.com/colbymchenry/codegraph/blob/main/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`](https://github.com/colbymchenry/codegraph/blob/main/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.