05_02_02_path_analysis - Análisis de Caminos y Rutas Críticas

🛤️ Propósito

El Path Analysis Engine identifica caminos específicos a través del grafo, calculando métricas agregadas y detectando puntos problemáticos. Responde preguntas como: - "¿Cuál es el camino crítico que determina el tiempo de build?" - "Si modifico este módulo, qué más se afecta?" - "¿Cómo se conectan dos módulos específicos?" - "¿Cuáles son los módulos de mayor impacto?"

🏗️ Arquitectura

Componentes Principales

05_02_02_path_analysis/
├── path_analyzer.hpp       # Analizadores de caminos
├── test_path_analysis.cpp  # Tests unitarios
└── README.md              # Documentación

Clases Implementadas

1. CriticalPathAnalyzer - Caminos críticos (build time, latency)
2. DependencyChainAnalyzer - Cadenas de dependencias (transitive closure)
3. ImpactAnalyzer - Blast radius de cambios
4. ShortestPathFinder - Rutas más cortas entre módulos
5. PathMetricsCalculator - Métricas agregadas de paths

🔍 Tipos de Análisis

1. Critical Path Analysis

Objetivo: Identificar la secuencia más larga de dependencias que determina el tiempo mínimo de build/procesamiento.

Algoritmo: 1. Topological sort del grafo (DFS) 2. Dynamic programming: calcular longest path desde fuentes 3. Path crítico = path con máximo peso acumulado

Uso:

#include "path_analyzer.hpp"

using namespace audio_lab::dependency_graph::analysis;

Graph graph = /* ... */;
CriticalPathAnalyzer analyzer(graph);

// Critical path por build time (CPU cycles)
auto build_path = analyzer.find_critical_path_build_time();
std::cout << "Build critical path: " << build_path.to_string() << "\n";
std::cout << "Total CPU: " << build_path.total_weight << " cycles\n";

// Critical path por latencia
auto latency_path = analyzer.find_critical_path_latency();
std::cout << "Latency critical path: " << latency_path.to_string() << "\n";
std::cout << "Total latency: " << latency_path.total_weight << " samples\n";

// Custom weight function
auto custom_path = analyzer.find_critical_path([](const NodePtr& node) {
    // Peso = CPU * latency (productos con alta latencia y CPU)
    return node->cpu_cycles * (node->latency_samples + 1);
});

Output Ejemplo:

Build critical path: add_kernel → svf_filter → synth_voice → poly_synth
Total CPU: 2585 cycles

Latency critical path: svf_filter → synth_voice → poly_synth
Total latency: 6 samples

Complejidad: O(V + E) donde V = nodos, E = aristas

2. Dependency Chain Analysis

Objetivo: Calcular transitive closure (todas las dependencias directas e indirectas).

Uso:

DependencyChainAnalyzer chain_analyzer(graph);

// Todas las dependencias de un módulo
auto all_deps = chain_analyzer.get_all_dependencies("poly_synth");
std::cout << "poly_synth needs " << all_deps.size() << " modules:\n";
for (const auto& dep : all_deps) {
    std::cout << "  - " << dep << "\n";
}

// Todos los dependientes (quién usa este módulo)
auto all_dependents = chain_analyzer.get_all_dependents("add_kernel");
std::cout << "add_kernel is used by " << all_dependents.size() << " modules\n";

// Árbol de dependencias completo
auto tree = chain_analyzer.build_dependency_tree("poly_synth");
// tree es estructura jerárquica navegable

Output Ejemplo:

poly_synth needs 7 modules:
  - synth_voice
  - sine_osc
  - svf_filter
  - envelope_generator
  - add_kernel
  - mul_kernel
  - clamp_kernel

add_kernel is used by 5 modules

Complejidad: O(V + E) con BFS

3. Impact Analysis (Blast Radius)

Objetivo: Determinar el impacto de modificar un módulo.

Uso:

ImpactAnalyzer impact_analyzer(graph);

// Analizar impacto de cambiar un módulo
auto report = impact_analyzer.analyze_change_impact("svf_filter");
std::cout << report.summary();

// Encontrar módulos de mayor impacto
auto high_impact = impact_analyzer.find_high_impact_modules(5);
std::cout << "Top 5 high-impact modules:\n";
for (const auto& [module, count] : high_impact) {
    std::cout << "  " << module << ": affects " << count << " modules\n";
}

Output Ejemplo:

Impact of changing 'svf_filter':
  Affected modules: 3
  Total CPU impact: 2450 cycles
  Max latency impact: 3 samples
  Max depth: 2

Top 5 high-impact modules:
  add_kernel: affects 7 modules
  mul_kernel: affects 6 modules
  svf_filter: affects 3 modules
  sine_osc: affects 2 modules
  envelope_generator: affects 2 modules

Aplicación: - Refactoring: Saber cuántos módulos se afectan antes de cambiar - Testing: Priorizar tests de módulos de alto impacto - Code review: Revisar más cuidadosamente cambios de alto impacto

Complejidad: O(V + E) por módulo

4. Shortest Path Queries

Objetivo: Encontrar cómo se conectan dos módulos (mínimo saltos).

Uso:

ShortestPathFinder path_finder(graph);

// Camino más corto (bidireccional)
auto path = path_finder.find_shortest_path("poly_synth", "add_kernel");
if (!path.empty()) {
    std::cout << "Shortest path: " << path.to_string() << "\n";
    std::cout << "Distance: " << path.total_weight << " hops\n";
}

// Todos los caminos (hasta 10)
auto all_paths = path_finder.find_all_paths("poly_synth", "add_kernel", 10);
std::cout << "Found " << all_paths.size() << " paths:\n";
for (const auto& p : all_paths) {
    std::cout << "  " << p.to_string() << "\n";
}

Output Ejemplo:

Shortest path: poly_synth → synth_voice → svf_filter → add_kernel
Distance: 3 hops

Found 2 paths:
  poly_synth → synth_voice → svf_filter → add_kernel
  poly_synth → synth_voice → sine_osc → add_kernel

Complejidad: - Shortest: O(V + E) con BFS - All paths: O(V!) en peor caso (con límite configurable)

5. Path Metrics

Objetivo: Calcular métricas agregadas de un path.

Uso:

PathMetricsCalculator metrics_calc(graph);

// Calcular métricas de critical path
auto build_path = analyzer.find_critical_path_build_time();
auto metrics = metrics_calc.calculate_metrics(build_path);

std::cout << "Depth: " << metrics.depth << " modules\n";
std::cout << "Total CPU: " << metrics.total_cpu_cycles << " cycles\n";
std::cout << "Total latency: " << metrics.total_latency_samples << " samples\n";
std::cout << "Max latency: " << metrics.max_latency_samples << " samples\n";
std::cout << "Avg CPU/level: " << metrics.avg_cpu_per_level << " cycles\n";

// O usar formato automático
std::cout << metrics_calc.format_metrics(build_path);

Output Ejemplo:

Path: add_kernel → svf_filter → synth_voice → poly_synth
  Depth: 4 modules
  Total CPU: 2585 cycles
  Total Latency: 6 samples
  Max Latency: 3 samples
  Avg CPU/Level: 646.25 cycles

📊 Casos de Uso Prácticos

Caso 1: Optimizar Build Time

// 1. Encontrar critical path
auto critical = analyzer.find_critical_path_build_time();
std::cout << "Build bottleneck: " << critical.to_string() << "\n";

// 2. Calcular métricas
auto metrics = metrics_calc.calculate_metrics(critical);
std::cout << "Total build CPU: " << metrics.total_cpu_cycles << " cycles\n";

// 3. Identificar módulo más costoso en path
UUID most_expensive;
uint32_t max_cpu = 0;
for (const auto& node_id : critical.nodes) {
    auto node = graph.get_node(node_id);
    if (node->cpu_cycles > max_cpu) {
        max_cpu = node->cpu_cycles;
        most_expensive = node_id;
    }
}

std::cout << "Optimize this module first: " << most_expensive
          << " (" << max_cpu << " cycles)\n";

Caso 2: Safe Refactoring

// Antes de refactorizar un módulo
std::string module_to_change = "svf_filter";

auto impact = impact_analyzer.analyze_change_impact(module_to_change);

std::cout << "Refactoring safety analysis:\n";
std::cout << "  Modules affected: " << impact.affected_modules.size() << "\n";
std::cout << "  CPU to rebuild: " << impact.total_cpu_impact << " cycles\n";

if (impact.affected_modules.size() > 10) {
    std::cout << "  ⚠️  HIGH IMPACT - Review carefully!\n";
} else if (impact.affected_modules.size() > 5) {
    std::cout << "  ⚡ MEDIUM IMPACT - Test thoroughly\n";
} else {
    std::cout << "  ✅ LOW IMPACT - Safe to change\n";
}

// Listar módulos afectados
std::cout << "\nModules requiring rebuild:\n";
for (const auto& mod : impact.affected_modules) {
    std::cout << "  - " << mod << "\n";
}

Caso 3: Understanding Architecture

// ¿Cómo se relacionan dos módulos?
auto path = path_finder.find_shortest_path("poly_synth", "add_kernel");

if (path.empty()) {
    std::cout << "No connection between modules\n";
} else {
    std::cout << "Connection path:\n";
    std::cout << path.to_string() << "\n";
    std::cout << "\nInterpretation:\n";

    for (size_t i = 0; i < path.nodes.size() - 1; ++i) {
        auto source = graph.get_node(path.nodes[i]);
        auto target = graph.get_node(path.nodes[i + 1]);

        std::cout << "  " << source->label << " (" << to_string(source->level) << ")\n";
        std::cout << "    ↓ depends on\n";
    }
    auto last = graph.get_node(path.nodes.back());
    std::cout << "  " << last->label << " (" << to_string(last->level) << ")\n";
}

Caso 4: Prioritize Testing

// Encontrar módulos críticos para testing
auto high_impact = impact_analyzer.find_high_impact_modules(10);

std::cout << "Test Priority List (by impact):\n";
for (size_t i = 0; i < high_impact.size(); ++i) {
    const auto& [module, impact_count] = high_impact[i];
    auto node = graph.get_node(module);

    std::cout << (i + 1) << ". " << node->label << "\n";
    std::cout << "   Affects: " << impact_count << " modules\n";
    std::cout << "   Level: " << to_string(node->level) << "\n";
    std::cout << "   CPU: " << node->cpu_cycles << " cycles\n\n";
}

🧪 Testing

Test Cases

TEST_CASE("Critical path finds longest weighted path") {
    auto graph = create_linear_graph();  // A→B→C→D

    CriticalPathAnalyzer analyzer(graph);
    auto path = analyzer.find_critical_path_build_time();

    REQUIRE(path.nodes.size() == 4);
    REQUIRE(path.nodes[0] == "A");
    REQUIRE(path.nodes[3] == "D");
}

TEST_CASE("Dependency chain computes transitive closure") {
    auto graph = create_diamond_graph();  // A→B,C ; B,C→D

    DependencyChainAnalyzer analyzer(graph);
    auto deps = analyzer.get_all_dependencies("D");

    REQUIRE(deps.size() == 3);
    REQUIRE(deps.count("A") == 1);
    REQUIRE(deps.count("B") == 1);
    REQUIRE(deps.count("C") == 1);
}

TEST_CASE("Impact analysis calculates blast radius") {
    auto graph = create_simple_graph();

    ImpactAnalyzer analyzer(graph);
    auto report = analyzer.analyze_change_impact("svf_filter");

    REQUIRE(report.affected_modules.size() > 0);
    REQUIRE(report.total_cpu_impact > 0);
}

TEST_CASE("Shortest path finds minimal connection") {
    auto graph = create_simple_graph();

    ShortestPathFinder finder(graph);
    auto path = finder.find_shortest_path("poly_synth", "add_kernel");

    REQUIRE(!path.empty());
    REQUIRE(path.nodes.front() == "poly_synth");
    REQUIRE(path.nodes.back() == "add_kernel");
}

📈 Complejidad Algorítmica

Operación	Algoritmo	Complejidad Tiempo	Complejidad Espacio
Critical Path	Topological Sort + DP	O(V + E)	O(V)
All Dependencies	BFS	O(V + E)	O(V)
All Dependents	Reverse BFS	O(V + E)	O(V)
Impact Analysis	BFS + Metrics	O(V + E)	O(V)
Shortest Path	BFS	O(V + E)	O(V)
All Paths	DFS with backtrack	O(V!) peor caso	O(V)
Path Metrics	Linear scan	O(k) donde k = path length	O(1)

🔍 Interpretación de Resultados

Critical Path

add_kernel → svf_filter → synth_voice → poly_synth
Total: 2585 cycles

Interpretación: - El build NO puede completar en menos de 2585 cycles - Optimizar módulos en este path tiene máximo impacto - Paralelizar otros paths no reduce tiempo total

Impact Report

svf_filter affects 3 modules (2450 cycles)

Interpretación: - Cambiar svf_filter requiere recompilar 3 módulos - Total CPU para rebuild: 2450 cycles - Planning: reservar tiempo para testing downstream

Shortest Path

poly_synth → synth_voice → svf_filter → add_kernel (3 hops)

Interpretación: - Acoplamiento indirecto entre poly_synth y add_kernel - Cambios en add_kernel eventualmente afectan poly_synth - 3 niveles de indirección = bajo acoplamiento directo

🚀 Próximos Pasos

✅ Implementado: - Critical path analysis - Dependency chains (transitive closure) - Impact analysis (blast radius) - Shortest path queries - Path metrics calculation

⏳ Futuras Mejoras: - Dijkstra's algorithm para weighted shortest path - A* para pathfinding con heurísticas - Parallel path computation para grafos grandes - Path caching para queries frecuentes - Temporal analysis (cómo cambian paths entre versiones)

---

Status: ✅ Path Analysis Completo Analizadores: 5 tipos implementados Complejidad: O(V + E) para mayoría de operaciones