taskgraph_ts/tasks/implementation/analysis/parallel-groups.md

id, name, status, depends_on, scope, risk, impact, level

id	name	status	depends_on	scope	risk	impact	level
analysis/parallel-groups	Implement parallelGroups analysis function	completed	graph/construction graph/queries	narrow	low	component	implementation

Description

Implement parallelGroups(graph: TaskGraph): string[][] in src/analysis/index.ts or a dedicated module. This returns groups of tasks that can be executed concurrently — tasks at the same topological depth. Uses graphology-dag.topologicalGenerations.

Acceptance Criteria

• parallelGroups returns string[][] where each inner array is a generation of tasks at the same depth from sources
• Uses graphology-dag.topologicalGenerations() for the generation computation
• Tasks with zero prerequisites are in the first group
• Throws CircularDependencyError if the graph is cyclic (delegated to topologicalGenerations behavior)
• Works on disconnected graphs (each connected component sorted independently, then merged by depth)
• Unit tests: linear chain (each group size 1), diamond graph, disconnected components

References

• docs/architecture/api-surface.md — parallelGroups signature
• docs/architecture/graph-model.md — parallel groups definition

Notes

Implementation uses topologicalGenerations from graphology-dag which internally uses Kahn's algorithm. It naturally handles disconnected graphs by grouping source nodes (zero in-degree) from all components into the same first generation. On cyclic graphs, topologicalGenerations throws and we catch it to re-throw CircularDependencyError with cycle information (same pattern as topologicalOrder in queries.ts).

Summary

Implemented parallelGroups(graph: TaskGraph): string[][] in a dedicated module.

• Created: src/analysis/parallel-groups.ts, test/parallel-groups.test.ts
• Modified: src/analysis/index.ts (added re-export)
• Tests: 14, all passing (full suite: 457 tests passing, lint clean)