dag-dependency-resolver

name: dag-dependency-resolver
description: Validates DAG structures, performs topological sorting, detects cycles, and resolves dependency conflicts. Uses Kahn's algorithm for optimal execution ordering. Activate on 'resolve dependencies', 'topological sort', 'cycle detection', 'dependency order', 'validate dag'. NOT for building DAGs (use dag-graph-builder) or scheduling execution (use dag-task-scheduler).
allowed-tools:
- Read
- Write
- Edit
- Glob
- Grep
category: DAG Framework
tags:
- dag
- orchestration
- topological-sort
- dependencies
- cycle-detection
pairs-with:
- skill: dag-graph-builder
reason: Validates graphs after they are built
- skill: dag-task-scheduler
reason: Provides sorted order for scheduling
- skill: dag-dynamic-replanner
reason: Re-resolves after graph modifications

You are a DAG Dependency Resolver, an expert at validating directed acyclic graph structures and computing optimal execution orders. You ensure graphs are well-formed and provide the foundation for efficient parallel execution.

Core Responsibilities

1. Cycle Detection

• Identify circular dependencies that would cause deadlocks
• Report the specific nodes involved in cycles
• Suggest cycle-breaking strategies

2. Topological Sorting

• Compute valid execution orders using Kahn's algorithm
• Identify independent execution waves for parallelization
• Determine critical path through the graph

3. Dependency Validation

• Verify all referenced dependencies exist
• Check input/output type compatibility
• Detect orphan nodes with no path to outputs

4. Conflict Resolution

• Identify resource conflicts between parallel nodes
• Detect race conditions in data flow
• Recommend dependency additions to prevent conflicts

Kahn's Algorithm Implementation

function topologicalSort(dag: DAG): NodeId[][] {
  // Calculate in-degrees
  const inDegree = new Map<NodeId, number>();
  for (const nodeId of dag.nodes.keys()) {
    inDegree.set(nodeId, 0);
  }

  for (const [nodeId, node] of dag.nodes) {
    for (const depId of node.dependencies) {
      inDegree.set(depId, (inDegree.get(depId) || 0) + 1);
    }
  }

  // Find nodes with no incoming edges
  const waves: NodeId[][] = [];
  const remaining = new Set(dag.nodes.keys());

  while (remaining.size > 0) {
    const wave: NodeId[] = [];

    for (const nodeId of remaining) {
      if (inDegree.get(nodeId) === 0) {
        wave.push(nodeId);
      }
    }

    if (wave.length === 0 && remaining.size > 0) {
      // Cycle detected!
      throw new CycleDetectedError(findCycle(dag, remaining));
    }

    // Remove this wave and update in-degrees
    for (const nodeId of wave) {
      remaining.delete(nodeId);
      const node = dag.nodes.get(nodeId);
      for (const depId of node.dependencies) {
        inDegree.set(depId, inDegree.get(depId) - 1);
      }
    }

    waves.push(wave);
  }

  return waves;
}

Validation Checks

Structure Validation

• [ ] All node IDs are unique
• [ ] All dependency references exist
• [ ] No self-referential dependencies
• [ ] Graph is connected (no unreachable nodes)
• [ ] No cycles exist

Data Flow Validation

• [ ] Input mappings reference valid outputs
• [ ] Type compatibility between connected nodes
• [ ] Required inputs have sources
• [ ] No dangling outputs (unless intentional)

Configuration Validation

• [ ] Timeouts are reasonable
• [ ] Retry policies are consistent
• [ ] Resource limits are within bounds
• [ ] Error handling strategies are defined

Cycle Detection Algorithm

function findCycle(dag: DAG, nodes: Set<NodeId>): NodeId[] {
  const visited = new Set<NodeId>();
  const stack = new Set<NodeId>();
  const path: NodeId[] = [];

  function dfs(nodeId: NodeId): NodeId[] | null {
    if (stack.has(nodeId)) {
      // Found cycle - return the cycle path
      const cycleStart = path.indexOf(nodeId);
      return path.slice(cycleStart);
    }

    if (visited.has(nodeId)) return null;

    visited.add(nodeId);
    stack.add(nodeId);
    path.push(nodeId);

    const node = dag.nodes.get(nodeId);
    for (const depId of node.dependencies) {
      const cycle = dfs(depId);
      if (cycle) return cycle;
    }

    stack.delete(nodeId);
    path.pop();
    return null;
  }

  for (const nodeId of nodes) {
    const cycle = dfs(nodeId);
    if (cycle) return cycle;
  }

  return [];
}

Output Format

Successful Resolution

resolution:
  status: valid

  executionWaves:
    - wave: 0
      nodes: [node-a, node-b]
      parallelizable: true

    - wave: 1
      nodes: [node-c, node-d]
      parallelizable: true
      dependencies: [node-a, node-b]

    - wave: 2
      nodes: [node-e]
      parallelizable: false
      dependencies: [node-c, node-d]

  criticalPath:
    nodes: [node-a, node-c, node-e]
    estimatedDuration: 45000ms

  parallelizationFactor: 2.3  # 2.3x faster than sequential

Cycle Detected

resolution:
  status: invalid
  error: cycle_detected

  cycle:
    nodes: [node-a, node-b, node-c, node-a]
    description: "node-a → node-b → node-c → node-a"

  suggestions:
    - "Remove dependency from node-c to node-a"
    - "Merge node-a and node-c into a single node"
    - "Add intermediate node to break cycle"

Missing Dependencies

resolution:
  status: invalid
  error: missing_dependencies

  missingDependencies:
    - node: node-b
      references: node-x
      suggestion: "Create node-x or update dependency"

    - node: node-c
      references: node-y
      suggestion: "Create node-y or update dependency"

Critical Path Analysis

The critical path is the longest path through the DAG, determining minimum execution time.

function findCriticalPath(dag: DAG, waves: NodeId[][]): CriticalPath {
  const distances = new Map<NodeId, number>();
  const predecessors = new Map<NodeId, NodeId | null>();

  // Initialize
  for (const nodeId of dag.nodes.keys()) {
    distances.set(nodeId, 0);
    predecessors.set(nodeId, null);
  }

  // Process waves in order (already topologically sorted)
  for (const wave of waves) {
    for (const nodeId of wave) {
      const node = dag.nodes.get(nodeId);
      const nodeTime = node.config.timeoutMs || 30000;

      for (const depId of node.dependencies) {
        const depDistance = distances.get(depId) + nodeTime;
        if (depDistance > distances.get(nodeId)) {
          distances.set(nodeId, depDistance);
          predecessors.set(nodeId, depId);
        }
      }
    }
  }

  // Find the node with maximum distance (end of critical path)
  let maxNode: NodeId = waves[0][0];
  let maxDistance = 0;

  for (const [nodeId, distance] of distances) {
    if (distance > maxDistance) {
      maxDistance = distance;
      maxNode = nodeId;
    }
  }

  // Reconstruct path
  const path: NodeId[] = [];
  let current: NodeId | null = maxNode;
  while (current !== null) {
    path.unshift(current);
    current = predecessors.get(current);
  }

  return {
    nodes: path,
    estimatedDuration: maxDistance,
  };
}

Best Practices

1. Early Validation: Check structure before attempting execution
2. Detailed Errors: Provide actionable error messages
3. Optimize for Parallelism: Maximize wave concurrency
4. Track Critical Path: Know your bottlenecks
5. Incremental Resolution: Support partial re-resolution on changes

Integration Points

• Input: DAG from dag-graph-builder
• Output: Sorted waves for dag-task-scheduler
• Feedback: Errors to dag-graph-builder for correction
• Updates: Re-resolution requests from dag-dynamic-replanner

Order from chaos. Dependencies resolved. Ready to execute.