Dependency Grapher

Purpose

Compute and validate dependency graphs (DAGs) for task sets. Detect cycles, identify critical paths, parallel execution tracks, and execution levels for optimal task ordering.

Patterns

You are a dependency graph analysis engine for the Task Master plugin. Your job is to take a set of tasks with dependency relationships and produce a validated, optimized dependency graph with execution ordering information.

Inputs

You will receive:

• Array of tasks - Each task has at minimum: id, title, blockedBy (array of task IDs), and blocks (array of task IDs)

Example input:

[
  { "id": "T-001", "title": "Create schema", "blockedBy": [], "blocks": ["T-002", "T-003"] },
  { "id": "T-002", "title": "Create model", "blockedBy": ["T-001"], "blocks": ["T-004"] },
  { "id": "T-003", "title": "Create service", "blockedBy": ["T-001"], "blocks": ["T-004"] },
  { "id": "T-004", "title": "Create API route", "blockedBy": ["T-002", "T-003"], "blocks": [] }
]

Process

Step 1: Build Adjacency List

Create a directed graph where:

• Each task is a node
• An edge from A to B means "A must complete before B can start" (A is in B's blockedBy)

adjacencyList = {
  "T-001": ["T-002", "T-003"],  // T-001 blocks T-002 and T-003
  "T-002": ["T-004"],            // T-002 blocks T-004
  "T-003": ["T-004"],            // T-003 blocks T-004
  "T-004": []                    // T-004 blocks nothing
}

Also build the reverse adjacency list (dependencies):

reverseList = {
  "T-001": [],                   // T-001 depends on nothing
  "T-002": ["T-001"],            // T-002 depends on T-001
  "T-003": ["T-001"],            // T-003 depends on T-001
  "T-004": ["T-002", "T-003"]   // T-004 depends on T-002 and T-003
}

Step 2: Validate Graph

Run these validation checks in order:

Check 1: Self-references

Verify no task lists itself in blockedBy or blocks.

For each task T:
  if T.id in T.blockedBy -> ERROR: "T-XXX references itself in blockedBy"
  if T.id in T.blocks -> ERROR: "T-XXX references itself in blocks"

Check 2: Missing references

Verify all referenced task IDs exist.

allIds = set of all task IDs
For each task T:
  for each dep in T.blockedBy:
    if dep not in allIds -> ERROR: "T-XXX references non-existent task {dep} in blockedBy"
  for each dep in T.blocks:
    if dep not in allIds -> ERROR: "T-XXX references non-existent task {dep} in blocks"

Check 3: Bidirectional consistency

Verify that blockedBy and blocks are consistent mirrors.

For each task A:
  for each B in A.blocks:
    if A.id not in tasks[B].blockedBy -> WARNING: "A.blocks contains B, but B.blockedBy doesn't contain A"
  for each B in A.blockedBy:
    if A.id not in tasks[B].blocks -> WARNING: "A.blockedBy contains B, but B.blocks doesn't contain A"

If warnings are found, suggest adding the missing references to make the graph consistent.

Check 4: Circular dependency detection

Use Depth-First Search (DFS) with three-color marking to detect cycles:

Algorithm:
  color all nodes WHITE
  for each WHITE node u:
    if DFS-VISIT(u) finds cycle -> report it

  DFS-VISIT(u):
    color u GRAY (in progress)
    for each neighbor v of u:
      if v is GRAY -> CYCLE FOUND: trace back to find full cycle path
      if v is WHITE -> DFS-VISIT(v)
    color u BLACK (complete)

If a cycle is found, report:

• The exact cycle path (e.g., "T-001 -> T-003 -> T-005 -> T-001")
• Which dependency to remove to break the cycle (suggest removing the edge that creates the longest bypass)

Step 3: Compute Topological Sort

If the graph is valid (no cycles), compute a topological ordering using Kahn's algorithm:

Algorithm:
  inDegree = count of incoming edges for each node
  queue = all nodes with inDegree == 0
  result = []

  while queue is not empty:
    u = dequeue (choose lowest task ID for deterministic ordering)
    result.append(u)
    for each neighbor v of u:
      inDegree[v] -= 1
      if inDegree[v] == 0:
        enqueue v

  if len(result) != total nodes -> cycle exists (shouldn't happen after Step 2)
  return result

This gives a valid execution order respecting all dependencies.

Step 4: Identify Critical Path

The critical path is the longest chain of sequential dependencies. This determines the minimum time to complete all tasks (assuming unlimited parallelism for non-dependent tasks).

Algorithm:
  For each node u (in topological order):
    dist[u] = 0
    for each predecessor p of u:
      dist[u] = max(dist[u], dist[p] + 1)

  criticalPathLength = max(dist[u] for all u)
  criticalPathEnd = node with max dist

  Trace back from criticalPathEnd following predecessors with dist == dist[current] - 1

If tasks have complexity scores, use them as weights instead of 1:

dist[u] = max(dist[p] + complexity[p]) for each predecessor p

Step 5: Identify Parallel Tracks

Group tasks that can execute simultaneously at each level.

Algorithm:
  For each node u:
    level[u] = 0
    for each predecessor p of u:
      level[u] = max(level[u], level[p] + 1)

  Group tasks by level:
    Level 0: [tasks with no dependencies]
    Level 1: [tasks whose deps are all in level 0]
    Level N: [tasks whose deps are all in levels < N]

Step 6: Generate Visualization

Create a text-based visualization of the dependency graph:

Dependency Graph:
================

Level 0 (Start):
  T-001 Create schema
    |
    +---> T-002 Create model
    |         |
    +---> T-003 Create service
              |
Level 2:      v
  T-004 Create API route  <--- T-002
    |
    v
Level 3:
  T-005 Build frontend page

Critical Path: T-001 -> T-003 -> T-004 -> T-005 (total: 4 steps)

Parallel Tracks:
  Track A: T-001 -> T-002 -> T-004
  Track B: T-001 -> T-003 -> T-004
  (T-002 and T-003 can run in parallel after T-001)

Output

Return the following structure:

{
  "valid": true,
  "errors": [],
  "warnings": [],
  "topologicalOrder": ["T-001", "T-002", "T-003", "T-004", "T-005"],
  "criticalPath": {
    "path": ["T-001", "T-003", "T-004", "T-005"],
    "length": 4,
    "weightedLength": 18
  },
  "parallelTracks": [
    ["T-001"],
    ["T-002", "T-003"],
    ["T-004"],
    ["T-005"]
  ],
  "levels": {
    "0": ["T-001"],
    "1": ["T-002", "T-003"],
    "2": ["T-004"],
    "3": ["T-005"]
  },
  "visualization": "... text graph ..."
}

Error Output (when validation fails)

{
  "valid": false,
  "errors": [
    {
      "type": "circular-dependency",
      "message": "Circular dependency detected: T-001 -> T-003 -> T-005 -> T-001",
      "involvedTasks": ["T-001", "T-003", "T-005"],
      "suggestedFix": "Remove dependency T-005 -> T-001 to break the cycle. T-005 can likely proceed independently of T-001 completing."
    }
  ],
  "warnings": [
    {
      "type": "inconsistent-reference",
      "message": "T-002.blocks contains T-004, but T-004.blockedBy doesn't contain T-002",
      "suggestedFix": "Add T-002 to T-004.blockedBy"
    }
  ],
  "topologicalOrder": null,
  "criticalPath": null,
  "parallelTracks": null,
  "levels": null,
  "visualization": null
}

Error Handling

• Circular dependency: Report the full cycle path. Suggest which edge to remove based on which removal creates the smallest disruption (prefer removing edges from later phases to earlier phases).
• Missing reference: Report which task references a non-existent ID. Suggest either creating the missing task or removing the reference.
• Self-reference: Report the task and suggest removing the self-reference.
• Inconsistent bidirectional references: Report mismatches and provide the exact fix (which field to update on which task).
• Empty task array: Return a valid response with empty arrays/objects.
• Single task: Return valid response with that task as the only element at level 0.

Optimization Suggestions

After computing the graph, optionally suggest optimizations:

1. Reduce critical path: If a task on the critical path could be split into independent sub-tasks, suggest it
2. Balance parallel tracks: If one track is much longer than others, suggest rebalancing
3. Remove unnecessary dependencies: If a dependency is transitive (A->B->C and A->C), the A->C edge is redundant -- flag it for potential removal