dag-dependency-resolver

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;
}

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 [];
}

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

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"

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"

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,
  };
}