agent_compositor_test/documents/research/dags.md

DAGs for Node-Based Compositing

What is a DAG?

A Directed Acyclic Graph (DAG) is a graph where:

• Directed — every edge has a direction (A → B means "A feeds into B")
• Acyclic — no path forms a cycle; you cannot loop back to a node you've already visited

In compositing, nodes are the vertices and image/data flow defines the edges. A Read node feeds into a Blur node, which feeds into a Merge node, etc.

Why DAGs for Compositing

Property	Benefit
Non-linear	Any node can be tweaked without rebuilding the whole comp
Dependency-driven	Only re-evaluate nodes whose inputs changed ("dirty propagation")
Parallelism	Independent branches can run concurrently
Modular	Nodes are self-contained; easy to add new types

Real-world examples

• Nuke (Foundry) — the industry standard; everything is a DAG
• Fusion (Blackmagic) — same concept, node graph as the primary interface
• Blender Compositor — uses a dependency graph internally
• Shadertoy / MaterialX — similar DAG concepts for shader/node graphs

Core Algorithms

BFS (Breadth-First Search) explores a graph level by level — you visit all neighbours of a node before moving to their neighbours. Useful for shortest paths and spreading outward.

DFS (Depth-First Search) goes deep first — you follow one path as far as it goes, then backtrack. Useful for cycle detection, pathfinding, and topological sort.

Topological Sort

A topological ordering of a DAG is a linear sequence of all vertices such that for every edge u → v, u appears before v. This is the evaluation order for a node graph — you must process a node's inputs before processing the node itself.

There are two standard approaches, one based on each traversal strategy:

1. Kahn's Algorithm (BFS-based)

Uses in-degree (number of incoming edges) to determine which nodes are ready to execute.

1. Compute in-degree for every node
2. Queue all nodes with in-degree == 0 (no dependencies)
3. While queue is not empty:
   a. Dequeue node n, add to result order
   b. For each downstream node m of n:
      - Decrement m's in-degree
      - If m's in-degree reaches 0, enqueue m
4. If result count != node count → there is a cycle

Why Kahn's for compositing:

• Naturally detects cycles (a graph editor must prevent the user from creating cycles)
• Gives you ready-to-evaluate layers (all in-degree-0 nodes at a given step can run in parallel)
• O(V + E) time, O(V) space
• Easy to implement with arrays

2. DFS-based (Post-order)

1. For each unvisited node, run DFS
2. After visiting all descendants of a node, prepend it to the result

Simpler to code but less practical for incremental / parallel evaluation. Used more for DAG verification in build systems.

Data Structures for a DAG

Adjacency List (recommended for Prism)

Store the graph as two flat arrays:

// Node i's outgoing edges are adjacency[i] .. adjacency[i + 1]
u32 *adjacency;       // flat list of edge destinations
u32 *adjacency_begin; // start index into adjacency for each node
u32  node_count;
u32  edge_count;

Or simpler: each node stores its outputs:

typedef struct PrNode PrNode;
struct PrNode {
    u32          id;
    PrNodeType   type;
    u32          input_count;     // number of inputs (incoming edges)
    u32          input_nodes[4];  // fixed-size or pointer to array
    u32          output_count;    // number of downstream nodes
    u32         *output_nodes;    // allocated with arena
    // ... data for this node type
};

For a data-oriented approach in hot paths (graph evaluation), pack fields into parallel arrays:

// SoA layout for evaluation
u8          *node_types;     // PrNodeType for each node
u32         *in_degrees;     // current in-degree (Kahn's state)
u32         *topo_order;     // result of topological sort

Struct-of-Arrays (SoA) Layout

For the graph evaluation hot path, you can use parallel arrays instead of an array of structs:

struct PrGraphEvalState {
    u32   node_count;
    u32  *topo_order;        // [0..node_count-1] in eval order
    u32  *in_degrees;        // temp space for Kahn's
    u8   *dirty_flags;       // per-node dirty bit
    u32  *output_counts;
    u32 **output_lists;      // adjacency
};

This keeps only the data needed for traversal in cache-friendly contiguous memory.

Incremental / Dirty Evaluation

For interactive use, re-running the full topological sort every frame is wasteful. Instead:

1. When a node's parameter changes, mark it dirty
2. Propagate the dirty flag downstream (BFS along edges)
3. Only re-evaluate dirty nodes in topological order

Alternatively, skip dirty propagation and just always eval in topo order — each node checks if its inputs are dirty or if its own parameters changed. Simpler, but does more work.

Cycles in a Graph Editor

A graph editor must prevent the user from creating cycles in real time. Approaches:

1. Check on each edge creation: before adding edge A → B, check if there's already a path from B to A (DFS from B). O(V + E) per edge add.
2. Incremental cycle detection: more sophisticated data structures for dynamic graphs. Probably overkill for V1.
3. Kahn's validation: Run Kahn's after every edit; if it doesn't produce a full ordering, reject the edit.

Approach 1 (DFS reachability test) is the simplest for V1.

Evaluation Pipeline

User edits graph
        │
        ▼
Validate no cycles  ← (reject edit if cycle detected)
        │
        ▼
Topological sort    ← (Kahn's algorithm → list of node IDs)
        │
        ▼
Mark dirty nodes    ← (only nodes downstream of changes)
        │
        ▼
For each node in topo order:
    If node is dirty:
        Gather input images (from upstream node outputs)
        Execute node (CPU or dispatch GPU shader)
        Store output image
        │
        ▼
Render final output → display

Key Takeaways for Prism

1. Kahn's algorithm is the right choice — simple, O(V+E), built-in cycle detection, parallel-layer grouping
2. Adjacency list with flat arrays for the graph structure
3. Evaluate in topological order; skip clean nodes for efficiency
4. Cycle check on edge creation via DFS from the target node
5. SoA layout for evaluation state if profiling shows cache misses on the hot path
6. Node types (Read, Blur, Merge, etc.) can use a PrNodeType enum with a function dispatch table, or a union of type-specific data in the node struct

References

• Kahn, A. B. (1962). "Topological sorting of large networks." Communications of the ACM
• Cormen et al., Introduction to Algorithms, 3rd ed., Ch. 22.4 (Topological Sort)
• Foundry Nuke documentation: https://learn.foundry.com/nuke
• Taskflow C++ library: https://taskflow.github.io