Skip to content

Dependency Graph (08_08_00)

Graph-based dependency management system for AudioLab plugins.

Features

DependencyGraphBuilder

  • Node Management: Add, remove, update nodes with metadata
  • Edge Management: Define dependency relationships
  • Dependency Analysis:
  • Direct dependencies (immediate dependencies)
  • Transitive dependencies (full dependency tree)
  • Reverse dependencies (what depends on X)
  • Cycle Detection: Identify circular dependencies
  • Graph Validation: Ensure graph integrity
  • Root/Leaf Analysis: Find entry and exit points

TopologicalSorter

  • Kahn's Algorithm: BFS-based topological sort
  • DFS Algorithm: Depth-first topological sort
  • Batch Processing: Group independent nodes for parallel processing
  • Subgraph Sorting: Sort only relevant portions
  • Build Order: Calculate minimal build order for targets

BuildOrderAnalyzer

  • Incremental Builds: Determine what needs rebuilding
  • Build Time Estimation: Predict total build time
  • Critical Path Analysis: Find longest dependency chain

GraphVisualizer

  • Multiple Formats:
  • DOT (Graphviz)
  • SVG (requires Graphviz)
  • JSON
  • ASCII art tree
  • Mermaid diagrams
  • Layout Algorithms: Hierarchical, circular, force-directed
  • Styling: Customizable colors, shapes, labels
  • Statistics: Graph metrics and analysis

Usage Example

#include "DependencyGraphBuilder.hpp"
#include "TopologicalSorter.hpp"
#include "GraphVisualizer.hpp"

using namespace audiolab::plugins::dependency;

// Build graph
DependencyGraphBuilder graph;
graph.addNode({"core_dsp", "Core DSP", "2.0.0", "library", {}});
graph.addNode({"eq_plugin", "EQ Plugin", "1.0.0", "plugin", {"core_dsp"}});

// Validate
auto validation = graph.validate();
if (!validation.success) {
    std::cerr << validation.error_message << std::endl;
}

// Sort
TopologicalSorter sorter(graph);
auto result = sorter.sort();
for (const auto& node_id : result.sorted_nodes) {
    std::cout << "Build: " << node_id << std::endl;
}

// Visualize
GraphVisualizer viz(graph);
std::cout << viz.generateASCII() << std::endl;
viz.saveToFile("graph.dot", GraphFormat::DOT);

API Reference

DependencyNode

struct DependencyNode {
    std::string id;                    // Unique identifier
    std::string name;                  // Human-readable name
    std::string version;               // Semantic version
    std::string type;                  // Component type
    std::vector<std::string> dependencies;
    std::unordered_map<std::string, std::string> metadata;
};

DependencyGraphBuilder Methods

bool addNode(const DependencyNode& node);
bool removeNode(const std::string& node_id);
std::optional<DependencyNode> getNode(const std::string& node_id) const;

bool addEdge(const DependencyEdge& edge);
bool removeEdge(const std::string& from, const std::string& to);

std::vector<std::string> getDirectDependencies(const std::string& node_id) const;
std::vector<std::string> getTransitiveDependencies(const std::string& node_id) const;
std::vector<std::string> getDirectDependents(const std::string& node_id) const;

std::vector<std::vector<std::string>> detectCycles() const;
bool isAcyclic() const;
GraphAnalysisResult validate() const;

TopologicalSorter Methods

TopologicalSortResult sortKahn() const;
TopologicalSortResult sortDFS() const;
std::vector<std::vector<std::string>> getBatches() const;
std::vector<std::string> getBuildOrder(const std::vector<std::string>& targets) const;
bool isValidTopologicalOrder(const std::vector<std::string>& order) const;

GraphVisualizer Methods

std::string generateDOT(const GraphStyle& style = {}) const;
std::string generateSVG(const GraphStyle& style = {}) const;
std::string generateJSON(bool include_metadata = false) const;
std::string generateASCII(const std::string& root_node = "", bool show_versions = true) const;
std::string generateMermaid(const std::string& direction = "TD") const;

bool saveToFile(const std::string& filename, GraphFormat format) const;
size_t exportMultiple(const std::string& base_filename, const std::vector<GraphFormat>& formats) const;

Build Instructions

cd tests
mkdir build && cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
cmake --build .
./test_dependency_graph

Examples

Run the demo: 

cd examples
mkdir build && cd build
cmake ../..
cmake --build .
./dependency_graph_demo

Performance

  • Graph Construction: O(V + E)
  • Cycle Detection: O(V + E)
  • Topological Sort: O(V + E)
  • Transitive Dependencies: O(V + E)
  • Memory: O(V + E) for graph storage

Where V = number of nodes, E = number of edges.

Thread Safety

  • ❌ Not thread-safe - External synchronization required
  • Use separate instances per thread or lock access

Dependencies

  • C++20
  • Catch2 (for tests)
  • Optional: Graphviz (for SVG generation)

Integration

add_subdirectory(08_08_00_dependency_graph)
target_link_libraries(your_target PRIVATE dependency_graph)