ADR-006: DFS-based circular reference detection in graph validation
Status: accepted
Deciders: Richard Attermeyer
Date: 2026-08-04
Context and Problem Statement
The traceability graph is a directed graph of items connected by typed relationships.
Users can create cycles — either accidentally (bidirectional addresses/addressed-by pairs where the inverse is explicit) or deliberately (complex traceability chains).
Auto-generated inverse relationships create implicit backward edges that should NOT count as cycles.
The detection must find all cycles and report them with human-readable paths.
Decision Drivers
-
Detect all cycles in the directed relationship graph
-
Skip auto-generated inverse relationships to avoid false positives
-
Report cycle paths in human-readable form for actionable user feedback
-
Run efficiently on typical traceability graphs (hundreds of items)
Considered Options
-
DFS with visited/recursion-stack tracking — tracks current exploration path
-
BFS-based cycle detection — cannot readily report cycle paths
-
Union-Find — only detects connectivity, not directed cycles
-
Tarjan’s strongly connected components — overkill, harder to produce user-friendly errors
Decision Outcome
Chosen option: DFS with visited/recursion-stack tracking, because it naturally captures the cycle path in the recursion stack and integrates cleanly with the existing graph structure.
Implementation
The findCircularReferences() method in TraceabilityGraph uses an iterative DFS with explicit call stack.
Two sets track progress: visited (fully explored nodes) and recursionStack (nodes currently on the exploration path).
When a node is encountered that is already in recursionStack, a cycle is detected and the full path is reported.
Auto-generated inverse relationships (rel.autoGenerated === true) are skipped entirely — cycle detection only follows explicitly declared forward edges.
Self-referencing edges (A → A) are detected as 1-node cycles.