DAG Structure for Computational Framework¶

This document describes the optional Directed Acyclic Graph (DAG) structure that can be added to the computational framework described in computational-framework.md.

Overview¶

While the standard framework can operate without explicit DAG structure, in some complex models it may be beneficial to represent the relationship between perches and mover_s as a DAG. This document outlines how DAG structure can be integrated into the framework.

When DAG structure is used, additional boolean flags track its state:

Perch Flags - has_DAG_info: Whether directed acyclic graph information has been provided

Mover Flags - has_DAG_info: Whether information about predecessor and successor perches is available

Stage Flags - has_DAG_structure: Whether a directed acyclic graph structure for this stage_ has been defined

Graph-Theoretic Structure¶

Within each period, the structure can be represented as a directed acyclic graph (DAG):

Graph Definition: 𝒢 = (𝒫, 𝔐) where 𝒫 is the set of perches and 𝔐 is the set of mover_s
Acyclicity Property: For any sequence of perches p₁, p₂, ..., pₙ ∈ 𝒫 such that (pᵢ, pᵢ₊₁) ∈ 𝔐 for i = 1, 2, ..., n-1, we must have p₁ ≠ pₙ.

This DAG structure induces a topological ordering that determines the sequence of operations:

Backward Solution: Process perches in reverse topological order
Forward Simulation: Process perches in topological order

DAG-Based Solution Process¶

When DAG structure is available, the solution process takes advantage of it:

Starting Point: The solution process begins at sink perches (those with no outgoing mover_s)
These typically have terminal conditions attached to their continuation perches
Traversal Order:
perches are processed in reverse topological order

Method Using DAG Structure:

# For each mover in reverse topological order
if mover.has_backward_operator():
    pred_value_fn, pred_policy_fn = mover.backward_solve()
    mover.get_pred().set_value_function(pred_value_fn, mover.id)
    mover.get_pred().set_policy_function(pred_policy_fn, mover.id)

DAG-Based Simulation Process¶

When DAG structure is available, the simulation process takes advantage of it:

Starting Point: The simulation process begins at source perches (those with no incoming mover_s)
Initial conditions come either from forward simulation of a predecessor stage or as direct input
Traversal Order:
perches are processed in topological order

Simulation Flow with DAG Structure:

# For each mover in topological order
distribution = mover.get_pred().get_distribution()
transformed_distribution = mover.forward_simulate(distribution)
mover.get_succ().update_distribution(transformed_distribution, mover.id)

Backend Selection with DAG Structure¶

When using DAG structure, backend selection follows the flexible backend architecture:

# List available backends
available_backends = WhispererFactory.available_backends()
print(f"Available backends: {available_backends}")

# Select a backend
backend_name = "dolo"  # Can be any registered backend
whisperer = WhispererFactory.create(backend_name)

# Create Stage with DAG structure and assign backend
stage_cons = create_and_solve_stage(
    stage_kind="cons",
    config_dir=stage_cons_config_dir,
    mode="multilithic",
    use_DAG=True,  # Enable DAG structure
    backend_name=backend_name  # Specify backend
)

This approach allows for integration of any computational backend that has been registered with the BackendRegistry system, while maintaining all DAG structure benefits.

DAG-Aware Construction¶

In some cases, component creation may be enhanced with DAG awareness:

# Create `stage_`s with DAG structure
stage_cons = create_and_solve_stage(
    stage_kind="cons",
    config_dir=stage_cons_config_dir,
    mode="multilithic",
    use_DAG=True  # Enable DAG structure
)

Multi-Source Perches¶

A perch may have multiple incoming movers (e.g., at a reconvergence point after branching). The DAG simulation protocol handles this as follows:

Readiness condition: A multi-source perch is ready for downstream processing only after ALL incoming movers have called update_distribution().
Combine operation: Once all incoming movers have deposited their sub-distributions, the perch executes:

perch.combine_distributions()

This produces the unified distribution for downstream consumption. The mathematical specification is method-independent (summation of branch-specific measures); see population-dynamics.md § Reconvergent Branch Combination for details.

Topological order: The standard topological-order traversal naturally respects the readiness condition: a perch is processed only after all its predecessors in the DAG have been processed.
Tracking: Each multi-source perch maintains a set of expected incoming mover IDs and tracks which have reported. The combine is triggered when the set is complete.

Design Patterns for DAG-Based Implementations¶

Certain design patterns are particularly useful for DAG-based implementations:

Visitor Pattern - Essential for traversing the DAG structure, enabling:
Clean implementation of forward and backward traversal algorithms
Addition of new operations without modifying the graph structure
Decoupling between traversal logic and perch_/mover_ operations

This pattern is key for DAG traversal since it separates traversal logic from the operations performed at each node.