05_02_03_cycle_detection - Detección de Ciclos Prohibidos

🔄 Propósito

El Cycle Detection System es el guardián de la arquitectura: detecta dependencias circulares prohibidas que romperían las reglas de jerarquía DAG (Directed Acyclic Graph). Sin ciclos, el sistema puede compilar en orden topológico y garantizar que módulos de nivel inferior nunca dependan de niveles superiores.

🏗️ Arquitectura

Componentes Principales

05_02_03_cycle_detection/
├── cycle_detector.hpp      # Algoritmos de detección
├── ci_hooks.hpp            # Integración CI/CD
├── test_cycle_detection.cpp # Tests
└── README.md              # Documentación

Clases Implementadas

1. DfsCycleDetector - DFS con colores (O(V+E))
2. TarjanSccDetector - Strongly Connected Components
3. CycleBreakingSuggester - Sugerencias automáticas
4. CycleValidator - Validación completa con reporting
5. CI Integration - Hooks para GitHub/GitLab

🔍 Algoritmos de Detección

1. DFS con Colores (Primary)

Algoritmo:

WHITE: No visitado
GRAY:  En proceso (en stack actual)
BLACK: Completamente procesado

Para cada nodo:
  Marcar GRAY
  Visitar dependencias:
    Si dependencia es GRAY → ¡CICLO!
  Marcar BLACK

Complejidad: O(V + E)

Uso:

#include "cycle_detector.hpp"

using namespace audio_lab::dependency_graph::validation;

Graph graph = /* ... */;
DfsCycleDetector detector(graph);

// Check rápido
if (detector.has_cycle()) {
    std::cout << "⚠️  Graph has cycles!\n";
}

// Encontrar primer ciclo
auto cycle = detector.find_cycle();
if (!cycle.empty()) {
    std::cout << "Cycle: " << cycle.to_string() << "\n";
    // Output: "module_a → module_b → module_c → module_a"
}

// Encontrar todos los ciclos
auto all_cycles = detector.find_all_cycles(10);
std::cout << "Found " << all_cycles.size() << " cycles\n";

Ventajas: - Simple y rápido - Encuentra path exacto del ciclo - Fácil de entender

2. Tarjan's Strongly Connected Components

Algoritmo: - Encuentra SCCs (Strongly Connected Components) - SCC = conjunto de nodos mutuamente alcanzables - En DAG: todos los SCCs tienen tamaño 1 - Ciclo existe ↔ algún SCC tiene tamaño > 1

Complejidad: O(V + E)

Uso:

TarjanSccDetector detector(graph);

// Encontrar todos los SCCs
auto sccs = detector.find_sccs();

for (const auto& scc : sccs) {
    if (scc.is_cycle()) {
        std::cout << "Cyclic SCC: " << scc.to_string() << "\n";
        // Output: "{module_a, module_b, module_c}"
    }
}

// Check rápido
if (detector.has_cycle()) {
    std::cout << "Graph has cycles\n";
}

// Solo SCCs cíclicos
auto cycles = detector.find_cycles();

Ventajas: - Encuentra todos los ciclos en un pass - Agrupa ciclos relacionados - Útil para análisis de clusters

💡 Sistema de Sugerencias

El CycleBreakingSuggester analiza ciclos y sugiere estrategias para romperlos.

Tipos de Sugerencias

1. REMOVE_EDGE - Eliminar dependencia débil
2. EXTRACT_MODULE - Extraer lógica común
3. INVERT_DEPENDENCY - Usar interfaces/DI
4. REFACTOR_ARCHITECTURE - Cambio estructural mayor

Heurísticas de Priorización

Priority 10: Dependencia OPTIONAL

// Si ciclo contiene edge opcional → safe to remove
svf_filter → reverb (OPTIONAL) → svf_filter
Suggestion: Remove optional dependency svf_filter → reverb

Priority 8: Edge con menor coupling

// link_strength < 1.0 = acoplamiento débil
module_a → module_b (strength: 0.3)
Suggestion: Weakest coupling - remove this edge

Priority 7: Módulos en misma categoría

// Si 2+ módulos de tipo FILTER en ciclo
Suggestion: Extract common FILTER logic to new L0/L1 module

Priority 6: Ciclos en L2+

// High-level modules cíclicos
Suggestion: Use interfaces/dependency injection

Priority 3: Refactoring general

Suggestion: Consider redesigning module relationships

Uso

CycleBreakingSuggester suggester(graph);

auto cycle = detector.find_cycle();
auto suggestions = suggester.suggest_breaking_strategies(cycle);

std::cout << "Breaking strategies:\n";
for (const auto& sug : suggestions) {
    std::cout << sug.to_string() << "\n";
}

Output Ejemplo:

Breaking strategies:
[Priority 10] Remove dependency: reverb_cell → svf_filter
  This is an optional dependency - safe to remove

[Priority 8] Remove dependency: module_a → module_b
  Weakest coupling in cycle (strength: 0.4)

[Priority 7] Extract common logic to new module
  Extract common FILTER logic to new L0/L1 module

[Priority 6] Invert dependency using interface
  Use interfaces/dependency injection to break cycle

📋 Validation Report

El CycleValidator genera reports completos:

CycleValidator validator(graph);
auto report = validator.validate();

std::cout << report.generate_report(graph);

Output si válido:

✅ VALIDATION PASSED - Graph is a valid DAG (no cycles)

Output si inválido:

❌ VALIDATION FAILED - Cycles detected

Found 2 cycle(s):

Cycle 1:
  Path: svf_filter → synth_voice → reverb_cell → svf_filter
  Nodes involved:
    - SVF Filter (L1_ATOM)
    - Synth Voice (L2_CELL)
    - Reverb Effect (L2_CELL)

Cycle 2:
  Path: module_a → module_b → module_a
  Nodes involved:
    - Module A (L1_ATOM)
    - Module B (L1_ATOM)

Breaking Suggestions:
1. [Priority 10] Remove dependency: reverb_cell → svf_filter
   This is an optional dependency - safe to remove

2. [Priority 8] Remove dependency: module_b → module_a
   Weakest coupling in cycle (strength: 0.4)

3. [Priority 7] Extract common logic to new module
   Extract common FILTER logic to new L0/L1 module

🚀 CI/CD Integration

Pre-Commit Hook

Instalación:

PreCommitHook::install_hook("/path/to/repo");

Genera script:

#!/bin/bash
# Auto-generated dependency graph validation hook

# Build and validate graph
dependency-graph validate --catalog catalog.json
exit $?

Uso manual:

PreCommitHook hook(graph);
int exit_code = hook.run(/* verbose= */ true);
return exit_code;  // 0 = success, 1 = cycle detected

GitHub Actions

Generate workflow:

std::cout << GitHubActionsIntegration::generate_workflow_yaml();

Output: .github/workflows/validate-graph.yml

name: Dependency Graph Validation

on:
  pull_request:
    branches: [ main, develop ]
  push:
    branches: [ main ]

jobs:
  validate-graph:
    runs-on: ubuntu-latest
    steps:
    - uses: actions/checkout@v3
    - name: Validate dependency graph
      run: ./dependency-graph-validator --catalog catalog.json --format github
    - name: Comment PR
      if: failure()
      uses: actions/github-script@v6
      # ... auto-comment on PR with cycle details

GitHub Annotations:

::error file=dependency_graph.json,title=Cycle Detected::Cycle: module_a → module_b → module_a

GitLab CI

Generate config:

std::cout << GitLabCiIntegration::generate_gitlab_ci_yaml();

Output: .gitlab-ci.yml

validate-dependency-graph:
  stage: validate
  script:
    - ./dependency-graph-validator --catalog catalog.json --format gitlab
  artifacts:
    reports:
      junit: validation-report.xml

JUnit XML output:

<?xml version="1.0" encoding="UTF-8"?>
<testsuites>
  <testsuite name="DependencyGraphValidation" tests="1" failures="1">
    <testcase name="CycleDetection" status="failed">
      <failure message="Cycles detected">
        <![CDATA[
        Cycle: module_a → module_b → module_a
        ]]>
      </failure>
    </testcase>
  </testsuite>
</testsuites>

CLI Tool

Uso:

# Console output (default)
dependency-graph validate --catalog catalog.json

# GitHub Actions format
dependency-graph validate --catalog catalog.json --format github

# GitLab CI format
dependency-graph validate --catalog catalog.json --format gitlab

# JUnit XML
dependency-graph validate --catalog catalog.json --format junit --output report.xml

# Verbose mode
dependency-graph validate --catalog catalog.json --verbose

Código:

ValidationCli::Options opts;
opts.catalog_path = "catalog.json";
opts.format = "github";
opts.verbose = true;

int exit_code = ValidationCli::run(opts);
return exit_code;

📊 Exit Codes

Code	Enum	Significado
0	SUCCESS	Validación pasó (DAG válido)
1	CYCLE_DETECTED	Ciclos encontrados
2	HIERARCHY_VIOLATION	Violación de jerarquía
3	VALIDATION_ERROR	Error en validación
4	IO_ERROR	Error leyendo catálogo

Uso en scripts:

if ./validate-graph --catalog catalog.json; then
    echo "✅ Graph is valid"
    git commit -m "..."
else
    echo "❌ Fix cycles before committing"
    exit 1
fi

🧪 Testing

Test Cases

TEST_CASE("DFS detects simple cycle") {
    Graph g;
    // Create: A → B → C → A
    add_nodes_and_edges(g, {"A", "B", "C"}, {{"A","B"}, {"B","C"}, {"C","A"}});

    DfsCycleDetector detector(g);
    REQUIRE(detector.has_cycle() == true);

    auto cycle = detector.find_cycle();
    REQUIRE(cycle.get_cycle_nodes().size() == 3);
}

TEST_CASE("Tarjan finds all SCCs") {
    Graph g;
    // Complex graph with multiple SCCs

    TarjanSccDetector detector(g);
    auto sccs = detector.find_sccs();

    auto cyclic_sccs = detector.find_cycles();
    REQUIRE(cyclic_sccs.size() > 0);
}

TEST_CASE("Suggester prioritizes optional edges") {
    Graph g;
    // Cycle with optional dependency

    CycleBreakingSuggester suggester(g);
    auto cycle = find_cycle(g);
    auto suggestions = suggester.suggest_breaking_strategies(cycle);

    REQUIRE(suggestions[0].priority == 10);
    REQUIRE(suggestions[0].type == Suggestion::Type::REMOVE_EDGE);
}

📈 Complejidad

Operación	Algoritmo	Tiempo	Espacio
has_cycle()	DFS	O(V + E)	O(V)
find_cycle()	DFS	O(V + E)	O(V)
find_all_cycles()	DFS	O(V + E)	O(V)
Tarjan SCCs	Tarjan	O(V + E)	O(V)
Breaking suggestions	Analysis	O(E)	O(1)

🎯 Casos de Uso Prácticos

Caso 1: Validación Pre-Deploy

#!/bin/bash
# deploy.sh

echo "Validating dependency graph..."
if ! ./validate-graph --catalog catalog.json; then
    echo "❌ Deployment blocked - fix cycles first"
    exit 1
fi

echo "✅ Graph valid - proceeding with deployment"
# ... deploy steps

Caso 2: PR Review Bot

# .github/workflows/pr-validation.yml
- name: Validate Graph
  run: |
    ./validate-graph --catalog catalog.json --format github

- name: Comment PR
  if: failure()
  run: |
    gh pr comment ${{ github.event.number }} \
      --body-file validation-report.md

Caso 3: Development Feedback

// En desarrollo
CycleValidator validator(graph);

if (!validator.is_dag()) {
    auto report = validator.validate();
    std::cout << "\n⚠️  WARNING: Cycles detected!\n\n";
    std::cout << report.generate_report(graph);

    std::cout << "\n💡 Fix suggestions above before committing.\n";
}

🚀 Próximos Pasos

✅ Implementado: - DFS cycle detection (O(V+E)) - Tarjan's SCC algorithm - Breaking suggestions con priorización - CI/CD hooks (GitHub, GitLab) - Multiple report formats

⏳ Futuras Mejoras: - Johnson's algorithm (todos los ciclos simples) - Cycle impact analysis (cuánto cuesta romper cada ciclo) - Auto-fixing (sugerir + aplicar cambios automáticamente) - Visualización interactiva de ciclos - Historical tracking (ciclos a través de commits)

---

Status: ✅ Cycle Detection Completo Algoritmos: 2 (DFS + Tarjan) CI/CD: GitHub Actions + GitLab CI + Pre-commit hooks Complejidad: O(V + E) detección garantizada