Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Cycle Detection

Note: Cycle detection is planned but not yet implemented. This chapter describes how the feature will work when available.

Cycle detection identifies circular dependencies in requirement graphs, which are usually errors that break valid traceability hierarchies.

What are Cycles?

A cycle occurs when requirements form a circular dependency chain:

USR-001 → SYS-001 → SYS-002 → USR-001

Requirements form a loop: USR-001 depends on SYS-001, which depends on SYS-002, which depends back on USR-001.

Why Cycles are Problematic

Break hierarchy assumptions:

  • Requirements should form a Directed Acyclic Graph (DAG)
  • Cycles violate DAG properties

Logical impossibility:

  • A cannot be satisfied until B is satisfied
  • B cannot be satisfied until C is satisfied
  • C cannot be satisfied until A is satisfied
  • Nothing can be satisfied!

Review complexity:

  • Changes propagate indefinitely
  • Impossible to determine impact

Compliance issues:

  • Many standards require acyclic traceability
  • Auditors expect clear hierarchies

Example Cycles

Simple Cycle (2 requirements)

USR-001 → SYS-001 → USR-001

Why it happens: Accidental bi-directional linking.

Detection: SYS-001 lists USR-001 as parent; USR-001 lists SYS-001 as parent.

Complex Cycle (3+ requirements)

USR-001 → SYS-001 → SYS-002 → SWR-001 → USR-001

Why it happens: Accumulation of links over time without oversight.

Detection: Following parent chain eventually returns to starting requirement.

Self-Reference

USR-001 → USR-001

Why it happens: Data entry error.

Detection: Requirement lists itself as a parent.

Planned Functionality

Cycle Detection Command

req check-cycles

Output (if cycles found):

Error: Cycles detected in requirement graph

Cycle 1 (length 3):
  USR-001 → SYS-001 → SYS-002 → USR-001

Cycle 2 (length 2):
  SYS-005 → SWR-003 → SYS-005

Cycle 3 (self-reference):
  SWR-012 → SWR-012

Total cycles: 3

Fix these cycles to ensure valid traceability.

Output (no cycles):

No cycles detected. Requirement graph is acyclic.

Detailed Cycle Information

req check-cycles --detailed

Output:

Cycle 1:
  Path: USR-001 → SYS-001 → SYS-002 → USR-001
  Length: 3
  Requirements involved:
    - USR-001: User authentication
      Parent: SYS-002 (creates cycle)
    - SYS-001: Authentication service
      Parent: USR-001
    - SYS-002: Session management
      Parent: SYS-001

  Suggested fix:
    Remove parent link from USR-001 to SYS-002
    (User requirements should not depend on system requirements)

Visualization

Generate cycle diagrams:

req check-cycles --visualize > cycles.dot
dot -Tpng cycles.dot -o cycles.png

Output: Graph highlighting cyclic paths in red.

How Detection Works

Requiem will use DFS with cycle detection:

  1. Start from each requirement
  2. Follow parent links (or child links for reverse traversal)
  3. Track visited requirements in current path
  4. If revisit a requirement in current path: Cycle detected
  5. Report cycle: Full path from requirement back to itself

Example Walkthrough

Requirements:

USR-001 → SYS-001
SYS-001 → SYS-002
SYS-002 → USR-001  (creates cycle)

Detection:

1. Start at USR-001
2. Visit SYS-001 (parent of USR-001)
3. Visit SYS-002 (parent of SYS-001)
4. Visit USR-001 (parent of SYS-002)
5. USR-001 is already in path → Cycle detected!
6. Report: USR-001 → SYS-001 → SYS-002 → USR-001

Performance

  • Time complexity: O(V + E) where V = requirements, E = links
  • Expected runtime: Milliseconds for 1000s of requirements
  • Parallel detection: Possible for disconnected subgraphs

Use Cases

Use Case 1: Continuous Validation

Scenario: Automatically check for cycles in CI.

Workflow:

# .github/workflows/requirements.yml (planned)
- name: Check for cycles
  run: |
    req check-cycles
    if [ $? -ne 0 ]; then
      echo "Cycles detected!"
      req check-cycles --detailed
      exit 1
    fi

Benefit: Cycles are caught before merging.

Use Case 2: Fixing Legacy Requirements

Scenario: Inherited a requirement set with unknown quality.

Goal: Find and fix all cycles.

Workflow:

# Detect cycles
req check-cycles --detailed

# Output:
# Cycle 1: USR-001 → SYS-001 → SYS-002 → USR-001
# Suggested fix: Remove link from USR-001 to SYS-002

# Fix cycle
vim USR-001.md  # Remove SYS-002 from parents

# Verify
req check-cycles
# No cycles detected

Use Case 3: Incremental Checking

Scenario: Adding a new link between requirements.

Goal: Ensure the new link doesn't create a cycle.

Workflow:

# Add link
req link SWR-001 SYS-005

# Check if cycle created
req check-cycles

# If cycle:
# Error: Cycle detected: SYS-005 → ... → SWR-001 → SYS-005

# If no cycle:
# No cycles detected

Benefit: Immediate feedback; don't commit cycle-inducing links.

Breaking Cycles

Identify the "weakest" link in the cycle and remove it:

USR-001 → SYS-001 → SYS-002 → USR-001
                               ^^^^^^^
                        Remove this link

Criteria for "weakest":

  • Violates hierarchy (e.g., user requirement depending on system requirement)
  • Accidental or incorrect
  • Least impactful to remove

Strategy 2: Reverse Hierarchy

If requirements are at wrong levels, reassign:

Before (cycle):
  USR-001 → SYS-001
  SYS-001 → USR-002
  USR-002 → USR-001

After (fixed):
  USR-001, USR-002 → SYS-001
  (SYS-001 now has both as parents; no cycle)

Strategy 3: Introduce Intermediate Requirement

Break cycle by adding a requirement:

Before (cycle):
  USR-001 → SYS-001 → USR-001

After (fixed):
  USR-001 → SYS-001 → SYS-002
  (SYS-002 is new, breaks cycle)

Strategy 4: Merge Requirements

If cycle indicates redundancy, merge:

Before (cycle):
  REQ-A → REQ-B → REQ-A

After (merged):
  REQ-AB (combines A and B; no cycle)

Configuration (Planned)

Enable/Disable Cycle Checking

# config.toml (planned)
[cycles]
# Enable cycle detection
enabled = true

# Fail on cycle detection (exit with error)
fail_on_cycle = true

# Report self-references separately
detect_self_references = true

CI Integration

[cycles.ci]
# Run cycle detection in CI
enabled = true

# Block merge if cycles detected
block_on_cycle = true

Exceptions (Planned)

In rare cases, cycles might be intentional. Allow marking exceptions:

# USR-001.md (hypothetical)
---
_version: '1'
uuid: ...
parents:
- uuid: ...
  hrid: SYS-002
  cycle_exception: true  # Mark as intentional cycle
---

Or in config:

[cycles.exceptions]
# Allow specific cycles
allowed = [
    ["USR-001", "SYS-001", "USR-001"],
]

Use sparingly: Cycles are almost always errors.

Topological Sort

After ensuring no cycles, enable topological sorting:

req sort --topological

Output: Requirements in dependency order (parents before children).

Use case: Determine implementation order.

Dependency Depth

Analyze requirement depth in hierarchy:

req depth USR-001

Output:

USR-001:
  Depth: 0 (root requirement)
  Max descendant depth: 4

  Path to deepest descendant:
    USR-001 → SYS-001 → SWR-003 → TST-012

Workarounds (Until Implemented)

Manual cycle detection:

Script to Detect Simple Cycles

#!/usr/bin/env python3
import glob
import yaml
import re

def parse_requirement(path):
    with open(path) as f:
        content = f.read()
    match = re.match(r'^---\n(.*?)\n---', content, re.DOTALL)
    if match:
        frontmatter = yaml.safe_load(match.group(1))
        return frontmatter
    return None

def find_cycles():
    # Build graph
    graph = {}
    for req_file in glob.glob("*.md"):
        hrid = req_file.replace('.md', '')
        frontmatter = parse_requirement(req_file)
        if frontmatter:
            parents = frontmatter.get('parents', [])
            parent_hrids = [p['hrid'] for p in parents]
            graph[hrid] = parent_hrids

    # Detect cycles with DFS
    def visit(req, path):
        if req in path:
            cycle = path[path.index(req):] + [req]
            print(f"Cycle detected: {' → '.join(cycle)}")
            return True
        if req not in graph:
            return False
        for parent in graph[req]:
            if visit(parent, path + [req]):
                return True
        return False

    for req in graph:
        visit(req, [])

if __name__ == '__main__':
    find_cycles()

Run:

python detect-cycles.py

Manual Inspection

For small requirement sets, manually trace parent chains:

  1. Pick a requirement (e.g., USR-001)
  2. Follow parent links
  3. Track visited requirements
  4. If you return to the starting requirement, cycle exists

Summary

Key concepts:

  • Cycle: Circular dependency chain in requirement graph
  • Problem: Breaks hierarchy, causes logical impossibility
  • Detection: Depth-first search with path tracking
  • Resolution: Remove links, reverse hierarchy, introduce intermediate requirements

Planned functionality:

  • Automatic cycle detection
  • Detailed cycle reports with suggested fixes
  • Visualization of cyclic paths
  • CI/CD integration
  • Configurable checking

Use cases:

  • CI validation
  • Legacy requirement cleanup
  • Incremental validation

Timeline: Implementation planned for future release

Next Steps