proffesor-for-testing__agentic-qe/docs/code-intelligence/circular-dependency-detection.md

Circular Dependency Detection with MinCut Analysis

The CircularDependencyDetector uses Tarjan's algorithm to find strongly connected components (SCCs) in your code dependency graph, then applies MinCut analysis to identify optimal break points for resolving circular dependencies.

Overview

Circular dependencies are a common code smell that can lead to:

• Difficult-to-understand code
• Build system issues
• Runtime initialization problems
• Tight coupling between modules

The CircularDependencyDetector helps you:

1. Find all circular dependencies in your codebase
2. Analyze their severity based on cycle size and edge types
3. Suggest optimal break points using minimum cut analysis
4. Recommend specific refactoring strategies

Quick Start

import { CircularDependencyDetector } from '@agentic-qe/code-intelligence/analysis/mincut';
import { GraphBuilder } from '@agentic-qe/code-intelligence/graph';

// Build your code graph
const builder = new GraphBuilder();
// ... add files, nodes, edges ...

// Create detector
const detector = new CircularDependencyDetector(builder.exportGraph());

// Find all circular dependencies
const cycles = await detector.detectAll();

// Display results
for (const cycle of cycles) {
  console.log(`Cycle: ${cycle.cycle.join(' → ')}`);
  console.log(`Severity: ${cycle.severity}`);
  console.log('Break points:', cycle.breakPoints);
  console.log('Recommendations:', cycle.recommendations);
}

Core Concepts

Strongly Connected Components (SCCs)

An SCC is a set of nodes where every node is reachable from every other node. In code:

• If Class A imports Class B, and Class B imports Class A, they form an SCC
• Any SCC with more than one node represents a circular dependency

Tarjan's Algorithm

We use Tarjan's algorithm to find SCCs efficiently:

• Time Complexity: O(V + E) where V = nodes, E = edges
• Space Complexity: O(V) for the recursion stack
• Advantages: Single pass, optimal performance

MinCut Analysis

After identifying an SCC (cycle), we use MinCut to find the weakest link:

• Converts the cycle into an undirected graph
• Finds edges with minimum total weight
• These are the easiest edges to break

Edge Type Weights

Different edge types have different coupling strengths:

Edge Type	Weight	Meaning
extends	1.0	Strongest - inheritance creates tight coupling
implements	0.9	Very strong - interface implementation
imports	0.8	Strong - direct dependency
calls	0.6	Moderate - function calls
uses	0.5	Moderate - type usage
contains	0.3	Weak - parent-child containment

MinCut considers these weights to identify edges that are easier to break.

API Reference

CircularDependencyDetector

class CircularDependencyDetector {
  constructor(graph: CodeGraph);

  // Find all circular dependencies
  detectAll(): Promise<CircularDependencyResult[]>;

  // Check if a specific file is in a cycle
  checkFile(filePath: string): Promise<CircularDependencyResult | null>;

  // Get statistics about cycles
  getStats(): Promise<{
    totalCycles: number;
    bySeverity: { high: number; medium: number; low: number };
    largestCycle: number;
    avgCycleSize: number;
  }>;
}

CircularDependencyResult

interface CircularDependencyResult {
  // Files involved in the circular dependency
  cycle: string[];

  // Suggested break points (from MinCut)
  breakPoints: BreakPoint[];

  // Severity based on cycle size and edge types
  severity: 'low' | 'medium' | 'high';

  // Actionable recommendations
  recommendations: string[];
}

BreakPoint

interface BreakPoint {
  // Source file/entity
  source: string;

  // Target file/entity
  target: string;

  // Type of edge to break
  edgeType: string;

  // Estimated effort to break this dependency
  effort: 'low' | 'medium' | 'high';

  // Specific suggestion
  suggestion: string;
}

Severity Classification

The detector classifies circular dependencies by severity:

High Severity

• Large cycles: More than 5 files
• Inheritance cycles: Contains extends edges
• Impact: Very difficult to break, high refactoring cost
• Priority: Fix immediately

Medium Severity

• Medium cycles: 3-5 files
• Interface cycles: Contains implements edges
• Impact: Moderate refactoring required
• Priority: Fix soon

Low Severity

• Small cycles: 2 files
• Import-only cycles: Only imports edges
• Impact: Easy to break with dependency injection
• Priority: Fix when convenient

Break Point Effort Estimation

Low Effort

• Edge types: imports, calls
• Solution: Extract to shared module or use dependency injection
• Example:

  // Before: A imports B, B imports A
  // After: Both import SharedTypes
  

Medium Effort

• Edge types: uses, implements
• Solution: Introduce an interface/abstraction layer
• Example:

  // Before: A uses B, B uses A
  // After: A uses IB (interface), B implements IB
  

High Effort

• Edge types: extends, overrides
• Solution: Restructure inheritance hierarchy
• Example:

  // Before: A extends B, B extends A (impossible!)
  // After: Favor composition over inheritance
  

Usage Examples

Example 1: Simple Two-File Cycle

// UserService.ts imports AuthService.ts
// AuthService.ts imports UserService.ts

const detector = new CircularDependencyDetector(graph);
const results = await detector.detectAll();

// Output:
// Cycle: UserService.ts → AuthService.ts
// Severity: low
// Break point: UserService → AuthService (imports)
// Effort: low
// Suggestion: Extract to shared module or use dependency injection

Resolution:

1. Extract common types to types.ts
2. Both services import from types.ts
3. Use dependency injection for runtime dependencies

Example 2: Complex Cycle with Inheritance

// BaseModel extends Repository
// Repository uses QueryBuilder
// QueryBuilder calls UserModel
// UserModel extends BaseModel

const results = await detector.detectAll();

// Output:
// Cycle: BaseModel → Repository → QueryBuilder → UserModel
// Severity: high (inheritance involved!)
// Break points:
//   1. QueryBuilder → UserModel (low effort)
//   2. Repository → QueryBuilder (medium effort)

Resolution (option 1 - easiest):

1. Break QueryBuilder → UserModel
2. Extract model interface: IUserModel
3. QueryBuilder depends on IUserModel instead of UserModel

Example 3: Batch Analysis

const detector = new CircularDependencyDetector(graph);
const stats = await detector.getStats();

console.log(`Found ${stats.totalCycles} cycles:`);
console.log(`  High severity: ${stats.bySeverity.high}`);
console.log(`  Medium severity: ${stats.bySeverity.medium}`);
console.log(`  Low severity: ${stats.bySeverity.low}`);
console.log(`Largest cycle: ${stats.largestCycle} files`);

// Prioritize high-severity cycles
const results = await detector.detectAll();
const highSeverity = results.filter(r => r.severity === 'high');

for (const cycle of highSeverity) {
  // Focus on these first
  console.log(`Fix: ${cycle.cycle.join(' → ')}`);
  console.log(`Easiest break point: ${cycle.breakPoints[0].suggestion}`);
}

Example 4: CI/CD Integration

import { CircularDependencyDetector } from '@agentic-qe/code-intelligence';

async function checkCircularDependencies() {
  const detector = new CircularDependencyDetector(graph);
  const results = await detector.detectAll();

  // Fail CI if high-severity cycles exist
  const highSeverity = results.filter(r => r.severity === 'high');
  if (highSeverity.length > 0) {
    console.error(`❌ Found ${highSeverity.length} high-severity circular dependencies`);
    highSeverity.forEach(cycle => {
      console.error(`   ${cycle.cycle.join(' → ')}`);
    });
    process.exit(1);
  }

  // Warn about medium/low severity
  const otherCycles = results.filter(r => r.severity !== 'high');
  if (otherCycles.length > 0) {
    console.warn(`⚠️  Found ${otherCycles.length} circular dependencies (non-critical)`);
  }

  console.log('✅ No critical circular dependencies');
}

Common Refactoring Patterns

Pattern 1: Extract Shared Types

Before:

// A.ts
import { B } from './B';
export class A { b: B; }

// B.ts
import { A } from './A';
export class B { a: A; }

After:

// types.ts
export interface IA { b: IB; }
export interface IB { a: IA; }

// A.ts
import { IA, IB } from './types';
export class A implements IA { b: IB; }

// B.ts
import { IA, IB } from './types';
export class B implements IB { a: IA; }

Pattern 2: Dependency Injection

Before:

// OrderService.ts
import { PaymentService } from './PaymentService';
class OrderService {
  payment = new PaymentService();
}

// PaymentService.ts
import { OrderService } from './OrderService';
class PaymentService {
  orders = new OrderService();
}

After:

// IPaymentService.ts
export interface IPaymentService {
  processPayment(order: Order): Promise<void>;
}

// OrderService.ts
import { IPaymentService } from './IPaymentService';
class OrderService {
  constructor(private payment: IPaymentService) {}
}

// PaymentService.ts
import { IPaymentService } from './IPaymentService';
class PaymentService implements IPaymentService {
  async processPayment(order: Order): Promise<void> {
    // No need to reference OrderService
  }
}

Pattern 3: Event-Driven Communication

Before:

// A.ts
import { B } from './B';
class A {
  doSomething() { new B().notify(this); }
}

// B.ts
import { A } from './A';
class B {
  notify(a: A) { a.doSomething(); }
}

After:

// EventBus.ts
export const eventBus = new EventEmitter();

// A.ts
import { eventBus } from './EventBus';
class A {
  doSomething() {
    eventBus.emit('something-happened', this);
  }
}

// B.ts
import { eventBus } from './EventBus';
class B {
  constructor() {
    eventBus.on('something-happened', this.onSomething);
  }
  onSomething(data: any) { }
}

Best Practices

1. Fix High-Severity First: Start with inheritance cycles and large cycles
2. Use Interfaces: Abstract dependencies through interfaces
3. Favor Composition: Avoid inheritance cycles by using composition
4. Dependency Injection: Inject dependencies instead of creating them
5. Event-Driven: Use events for loose coupling
6. Regular Checks: Run detection in CI/CD to prevent new cycles

Performance

• Tarjan's Algorithm: O(V + E) - very efficient even for large codebases
• MinCut Analysis: O(V³) worst case, but typically much faster for small cycles
• Practical Performance:
  • 1000-file codebase: < 5 seconds
  • 10,000-file codebase: < 30 seconds
  • 100,000-file codebase: < 5 minutes (mostly graph construction)

Limitations

1. Dynamic Dependencies: Cannot detect runtime/reflection-based dependencies
2. Conditional Imports: May miss conditional or lazy imports
3. External Modules: Only analyzes your codebase, not node_modules
4. Language-Specific: Requires language-specific parsers (currently TypeScript/JavaScript)

Related

• MinCut Analysis
• Graph Builder
• Code Intelligence Guide
• Module Coupling Analysis

Examples

See /examples/code-intelligence/circular-dependency-detection.ts for complete working examples.