dag-dependency-resolver

license	BSL-1.1
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	Agent & Orchestration
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, ensuring graphs are executable by detecting cycles, computing optimal execution orders, and resolving dependency conflicts.

DECISION POINTS

Algorithm Selection Strategy

Graph Size < 100 nodes AND Dense connections (>50% edge density)?
├── YES → Use Kahn's algorithm (better for dense graphs)
└── NO → Graph Size > 1000 nodes?
    ├── YES → Use DFS with early termination (memory efficient)
    └── NO → Use Kahn's algorithm (clearer wave structure)

Cycle Breaking Strategy (when cycles detected):
├── Single cycle with 2-3 nodes? → Suggest node merge
├── Multiple interconnected cycles? → Find minimum feedback arc set
├── Cycle involves external dependencies? → Add intermediate buffer node
└── Self-referential cycle? → Remove self-dependency (always safe)

Parallelization Opportunity Assessment:
├── Wave has >5 independent nodes? → Flag high parallelization potential
├── Critical path > 3x average path? → Recommend breaking bottleneck nodes
├── Resource conflicts detected? → Add ordering constraints
└── No conflicts? → Mark wave as fully parallelizable

FAILURE MODES

Fan-Out Explosion

• Symptom: Single node has >20 dependents, execution waves become unbalanced
• Detection: if node.dependents.length > 20 && maxWaveSize/avgWaveSize > 5
• Fix: Introduce intermediate aggregation nodes to batch dependencies

Deep Chain Dependency

• Symptom: Critical path >5x longer than shortest path, poor parallelization
• Detection: if criticalPath.length > shortestPath.length * 5
• Fix: Identify parallelizable sub-chains, split monolithic nodes

Phantom Dependency

• Symptom: Node references dependency that doesn't exist, validation fails silently
• Detection: if dependency not in dag.nodes && not flagged as missing
• Fix: Strict reference checking with explicit error for each missing dep

Resource Thrashing

• Symptom: Multiple nodes in same wave access same exclusive resource
• Detection: if nodes in wave share exclusive resource without ordering
• Fix: Add artificial dependencies to serialize resource access

Cycle Masking

• Symptom: Conditional dependencies create cycles only under certain conditions