dependency-grapher

What this skill does

# 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:

```json
[
  { "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:

```json
{
  "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)

```json
{
  "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 th