Topological Sorting Module¶

Part of AudioLab Graph System - TAREA 3

Overview¶

This module provides efficient topological sorting of audio processing graphs using Kahn's algorithm. It determines the correct processing order for nodes in a Directed Acyclic Graph (DAG) and detects parallel processing opportunities.

Features¶

Core Functionality¶

Kahn's Algorithm: O(V+E) topological sorting with cycle detection
Parallel Group Detection: Identifies nodes that can be processed concurrently
Priority-Based Ordering: Supports custom node priorities for scheduling
Caching: Lazy recomputation with cache invalidation
Dependency Levels: Assigns processing levels for pipeline stages

Key Capabilities¶

✅ Efficient DAG traversal
✅ Cycle detection (invalid graphs)
✅ Parallel branch identification
✅ Priority queue for same-level nodes
✅ Zero-copy operations
✅ Real-time safe (after initial sort)

Architecture¶

Class Hierarchy¶

TopologicalSorter
├── sort()                    // Basic topological sorting
├── sortWithParallelism()     // Sort + parallel group detection
├── setNodePriority()         // Set processing priority
└── invalidateCache()         // Force recalculation

Data Structures¶

struct SortResult {
    std::vector<NodeID> order;              // Topological order
    std::vector<ParallelGroup> parallelGroups;  // Groups for parallel processing
    bool isValid;                           // False if cycle detected
    std::string errorMessage;               // Error description
};

struct ParallelGroup {
    int level;                              // Dependency level
    std::vector<NodeID> nodes;              // Nodes at this level
    bool canProcessInParallel;              // True if independent
};

Usage Examples¶

Basic Topological Sort¶

#include "TopologicalSorter.h"

AudioGraph graph;
// ... add nodes and edges ...

TopologicalSorter sorter;
SortResult result = sorter.sort(graph);

if (result.isValid) {
    // Process nodes in order
    for (NodeID nodeId : result.order) {
        processNode(nodeId);
    }
} else {
    std::cerr << "Error: " << result.errorMessage << "\n";
}

Parallel Processing¶

SortResult result = sorter.sortWithParallelism(graph);

if (result.isValid) {
    // Process each level
    for (const auto& group : result.parallelGroups) {
        if (group.canProcessInParallel) {
            // Process nodes in parallel
            #pragma omp parallel for
            for (size_t i = 0; i < group.nodes.size(); ++i) {
                processNode(group.nodes[i]);
            }
        } else {
            // Process sequentially
            for (NodeID nodeId : group.nodes) {
                processNode(nodeId);
            }
        }
    }
}

Priority-Based Scheduling¶

TopologicalSorter sorter;

// Set priorities (higher = processed first)
sorter.setNodePriority(criticalNode, 100);
sorter.setNodePriority(normalNode, 50);
sorter.setNodePriority(lowPriorityNode, 10);

// Sort will respect priorities within same dependency level
SortResult result = sorter.sort(graph);

Cache Management¶

TopologicalSorter sorter;

// First sort - calculates and caches
SortResult result1 = sorter.sort(graph);

// Second sort - uses cache (fast!)
SortResult result2 = sorter.sort(graph);

// Modify graph...
graph.addEdge(nodeA, portA, nodeB, portB);

// Invalidate cache before sorting
sorter.invalidateCache();
SortResult result3 = sorter.sort(graph);

Algorithm Details¶

Kahn's Algorithm¶

Time Complexity: O(V + E) where V = vertices, E = edges

Steps: 1. Calculate in-degree for all nodes 2. Queue all nodes with in-degree = 0 (source nodes) 3. While queue not empty: - Dequeue node and add to result - Decrease in-degree of all neighbors - Queue neighbors with in-degree = 0 4. If all nodes processed → valid DAG 5. Otherwise → cycle detected

Pseudocode:

function topologicalSort(graph):
    inDegree = calculateInDegrees(graph)
    queue = [n for n in nodes if inDegree[n] == 0]
    result = []

    while queue not empty:
        node = queue.pop()
        result.append(node)

        for neighbor in node.neighbors:
            inDegree[neighbor]--
            if inDegree[neighbor] == 0:
                queue.push(neighbor)

    if len(result) == len(nodes):
        return result  // Valid
    else:
        return error   // Cycle detected

Parallel Group Detection¶

Algorithm: 1. Assign dependency levels to each node 2. Group nodes by level 3. Check independence within each group 4. Mark groups as parallel/sequential

Level Assignment:

levels[node] = 0  // Initialize

for node in topologicalOrder:
    for child in node.children:
        levels[child] = max(levels[child], levels[node] + 1)

Independence Check:

function areNodesIndependent(nodes):
    for nodeA in nodes:
        for nodeB in nodes:
            if hasEdge(nodeA, nodeB) or hasEdge(nodeB, nodeA):
                return false
    return true

Performance Characteristics¶

Time Complexity¶

Operation	Complexity	Notes
`sort()`	O(V + E)	First call or after invalidation
`sort()` (cached)	O(1)	Using cached result
`sortWithParallelism()`	O(V + E)	Includes parallel detection
`setNodePriority()`	O(1)	Invalidates cache
`invalidateCache()`	O(1)	Marks cache as dirty

Space Complexity¶

Structure	Space	Notes
In-degrees	O(V)	Temporary during sort
Priority queue	O(V)	Maximum all nodes queued
Result order	O(V)	Output vector
Parallel groups	O(V)	Grouped by level
Cache	O(V)	Stored result

Optimization Strategies¶

Caching: Reuse results when graph unchanged
Priority Queue: std::priority_queue for O(log V) operations
Reserve Memory: Pre-allocate vectors
Move Semantics: Avoid unnecessary copies
Lazy Evaluation: Only detect parallel groups when requested

Testing¶

Test Coverage¶

The module includes 40+ test cases covering:

✅ Construction and configuration
✅ Simple chains (empty, single, linear)
✅ Parallel branches (diamond, Y-junction)
✅ Cycle detection (self-loop, 2-node, 3-node)
✅ Parallel group detection
✅ Priority sorting
✅ Caching behavior
✅ Complex scenarios
✅ Edge cases

Running Tests¶

# Build
mkdir build && cd build
cmake ..
cmake --build .

# Run tests
./tests/test_topological_sorter

# Run specific test
./tests/test_topological_sorter "[cycle]"

Test Statistics¶

Test Files: 1
Test Cases: 40+
Lines of Test Code: ~680
Code Coverage: 100% of public API

Integration¶

Dependencies¶

graph_core: AudioGraph, GraphNode, GraphEdge types
Standard Library: <queue>, <algorithm>, <unordered_map>

CMake Integration¶

add_subdirectory(path/to/topological_sorting)

target_link_libraries(your_target
    PRIVATE
        topological_sorting
        graph_core
)

Examples¶

See examples/sorting_demo.cpp for comprehensive demonstrations:

Simple Chain: Basic linear dependency
Diamond Graph: Parallel branches converging
Priority Sorting: Custom scheduling priorities
Cycle Detection: Invalid graph handling
Complex Graph: Multi-level parallelism
Cache Performance: Efficient repeated sorting

Common Patterns¶

Audio Processing Pipeline¶

// Build audio effect chain
graph.addEdge(input, output, eq, input);
graph.addEdge(eq, output, compressor, input);
graph.addEdge(compressor, output, limiter, input);
graph.addEdge(limiter, output, outputNode, input);

// Sort for processing order
SortResult result = sorter.sort(graph);
// Result: input → eq → compressor → limiter → output

Parallel Send Effects¶

// Main chain with parallel sends
graph.addEdge(input, out, mainChain, in);
graph.addEdge(mainChain, send1, reverb, in);  // Parallel
graph.addEdge(mainChain, send2, delay, in);   // Parallel
graph.addEdge(reverb, out, mix, in1);
graph.addEdge(delay, out, mix, in2);
graph.addEdge(mainChain, out, mix, in3);

// Detect parallel processing
SortResult result = sorter.sortWithParallelism(graph);
// Reverb and delay can process concurrently!

Real-Time Scheduling¶

// Set priorities based on latency requirements
sorter.setNodePriority(lowLatencyNode, 100);
sorter.setNodePriority(normalNode, 50);
sorter.setNodePriority(bufferNode, 10);

// Sort will prioritize low-latency nodes
SortResult result = sorter.sort(graph);

Error Handling¶

Cycle Detection¶

SortResult result = sorter.sort(graph);

if (!result.isValid) {
    std::cerr << "Cycle detected: " << result.errorMessage << "\n";

    // Use CycleDetector for detailed cycle information
    CycleDetector detector;
    auto cycles = detector.detectCycles(graph);

    for (const auto& cycle : cycles.cycles) {
        std::cerr << "Cycle path: ";
        for (NodeID node : cycle.path) {
            std::cerr << node.value << " → ";
        }
        std::cerr << cycle.path[0].value << "\n";
    }
}

Best Practices¶

1. Cache Management¶

Invalidate cache after graph modifications
Use cached results for repeated queries
Consider cache lifetime in dynamic graphs

2. Priority Usage¶

Use priorities for real-time scheduling
Higher priorities for latency-critical nodes
Consistent priority ranges across graph

3. Parallel Processing¶

Check canProcessInParallel flag before parallelizing
Consider thread overhead for small groups
Balance parallelism with CPU availability

4. Error Recovery¶

Always check isValid before using result
Handle cycles gracefully in UI
Provide meaningful error messages to users

Limitations¶

DAG Requirement: Only works on acyclic graphs (use CycleDetector first)
Static Graph: Best performance with infrequent modifications
Memory: Caches entire sort result (O(V) space)
Priority Granularity: Only affects same-level nodes

Future Enhancements¶

Potential improvements (TAREA 12 - Optimization): - Incremental sorting after small changes - Parallel Kahn's algorithm for large graphs - Custom comparators for advanced scheduling - Integration with thread pool management - Performance profiling hooks

05_11_01_topology_validation: Validates graph before sorting
05_11_03_latency_management: Uses sort order for latency calculation
05_11_09_parallel_processing: Executes parallel groups concurrently

References¶

Kahn, A. B. (1962). "Topological sorting of large networks"
Cormen et al., "Introduction to Algorithms" (CLRS)
AudioLab Graph System documentation