Task graph helpers

TaskGraph is the dependency graph the scheduler walks, and the four functions here build it, search it, guard it and label it. All four are runtime exports of the package root, and none of them touch React or the DOM, so they run in Node, in a worker, or in a test.

import {
  buildTaskGraph,
  canLink,
  findPath,
  linkKey,
  type SchedulingLink,
  type TaskGraph,
} from '@jaeungkim/gantt-chart';

SchedulingLink — one dependency with both ends resolved — is defined on Scheduling core. The Task shape these functions read is on Task. Behaviour lives in Dependencies and Scheduling; running the core without the chart is Headless core.

`TaskGraph`

export interface TaskGraph {
  byId: Map<string, Task>;
  links: SchedulingLink[];
  /** successor id -> the links that constrain it */
  incoming: Map<string, SchedulingLink[]>;
  /** predecessor id -> the links it constrains */
  outgoing: Map<string, SchedulingLink[]>;
  /** Topological order, predecessors first. Excludes anything caught in a cycle. */
  order: string[];
  /** Ids that could not be ordered because they sit on a cycle (null when there is none) */
  cycle: string[] | null;
}

Field	Type	Contents	Empty or absent case
`byId`	`Map<string, Task>`	Every task passed in, keyed by `id`	Empty `Map` for an empty `tasks` array
`links`	`SchedulingLink[]`	One entry per surviving dependency, in task order then per-task `dependencies` order	`[]` when no dependency survives the drop rules below
`incoming`	`Map<string, SchedulingLink[]>`	Successor id to the links that constrain it	`.get(id)` is `undefined`, not `[]`, for a task with no predecessors
`outgoing`	`Map<string, SchedulingLink[]>`	Predecessor id to the links it constrains	`.get(id)` is `undefined`, not `[]`, for a task with no successors
`order`	`string[]`	Topological order, predecessors first. Tasks with no links at all are included	`[]` for an empty `tasks` array
`cycle`	`string[] \| null`	Every id left unordered, in input order	`null` when `order.length === tasks.length`

The cycle field's own comment says these ids "sit on a cycle". The code says something wider: cycle is every id whose indegree never reached zero, which includes tasks merely downstream of a loop. With a and b pointing at each other and down depending only on a, cycle is ['a', 'b', 'down'].

`buildTaskGraph`

/**
 * Builds the dependency graph and topologically sorts it (Kahn).
 *
 * Links pointing at a task that is not in the data are dropped, and anything caught in a
 * cycle is left out of `order` and reported in `cycle` - so every caller walks a finite,
 * acyclic list no matter what the data says.
 */
export function buildTaskGraph(tasks: Task[]): TaskGraph

Parameter	Type	Required	Meaning
`tasks`	`Task[]`	yes	The flat task list. Read, never mutated

Returns a TaskGraph. It never throws and never warns.

Two kinds of dependency are dropped silently while links is assembled:

Dropped	Test
A self-link — `dependency.targetId` equals the owning task's `id`	`targetId === task.id`
A dangling link — `targetId` names an id that is not in `tasks`	`byId.has(targetId)` is `false`

A task carrying both still appears in byId and in order; neither dependency reaches links, incoming or outgoing.

buildTaskGraph([]) returns empty byId, incoming and outgoing maps, links: [], order: [] and cycle: null.

`findPath`

/**
 * A dependency path from `fromId` to `toId`, or null when there is none.
 * Walks successors, so the result reads predecessor-first.
 */
export function findPath(
  tasks: Task[],
  fromId: string,
  toId: string
): string[] | null

Parameter	Type	Required	Meaning
`tasks`	`Task[]`	yes	The flat task list
`fromId`	`string`	yes	Id to walk out from, following `outgoing` links
`toId`	`string`	yes	Id to reach

Breadth-first over successors, so a hit is a shortest path by hop count.

Case	Return
A path exists	`string[]`, predecessor-first, both endpoints included — `['a', 'b', 'c']`
No path	`null`
`fromId === toId`	`[fromId]`, returned before the graph is built, so it holds even for an id that is not in `tasks`
`fromId` is not in `tasks`	`null`
`toId` is not in `tasks`	`null`
`tasks` is empty and the ids differ	`null`

A cycle in the data does not hang the walk: a visited-set stops each id being queued twice.

`canLink`

/**
 * Whether a new predecessor -> successor link can be added without closing a loop.
 *
 * Call this before writing a link into the data: a cycle that never gets created is a
 * cycle the engine never has to work around. `cycle` is the offending chain, ready to
 * put in an error message.
 */
export function canLink(
  tasks: Task[],
  predecessorId: string,
  successorId: string
): { ok: boolean; cycle: string[] | null }

Parameter	Type	Required	Meaning
`tasks`	`Task[]`	yes	The task list as it stands before the new link
`predecessorId`	`string`	yes	The earlier task — the id that would go in `dependencies[].targetId`
`successorId`	`string`	yes	The later task — the one that would own the new dependency

It rejects exactly two things.

Input	Return
`predecessorId === successorId`	`{ ok: false, cycle: [predecessorId, successorId] }`
The successor can already reach the predecessor	`{ ok: false, cycle: [...pathBack, successorId] }` — for the chain `a → b → c`, `canLink(tasks, 'c', 'a')` gives `{ ok: false, cycle: ['a', 'b', 'c', 'a'] }`
Anything else, including a link that already exists and ids that are not in `tasks`	`{ ok: true, cycle: null }`

cycle on a rejection is the chain with the closing hop appended, so its first and last entries are the same id.

`linkKey`

/** Stable identity for a link - used to tag the rendered arrow */
export function linkKey(link: SchedulingLink): string {
  return `${link.predecessorId}>${link.successorId}:${link.type}`;
}

Parameter	Type	Required	Meaning
`link`	`SchedulingLink`	yes	Only `predecessorId`, `successorId` and `type` are read

Returns a string in the literal format `${predecessorId}>${successorId}:${type}` — a > between the two ids, then a : and the two-letter link type. A finish-to-start link from a to b is 'a>b:FS'.

These are the keys computeCriticalPath puts in criticalLinkIds; see Critical path core.

Notes

linkKey ignores lag. Two dependencies between the same pair with the same type and different lags produce the same key.
canLink does not reject a duplicate link. A host that uses it as its only guard can write the same { targetId, type } into dependencies twice, and buildTaskGraph will emit two SchedulingLinks that collide on one linkKey. The chart's own link drag runs a second, duplicate-aware check that is internal and not exported from the package — see Dependencies.
findPath calls buildTaskGraph on every invocation, and canLink calls findPath. Both are O(tasks + links) per call, so validating a batch of links in a loop is quadratic.
The link-geometry helpers next to these functions in the source — linkSourceDate, linkTargetDate, linkDelta, taskStart, taskEnd, shiftTask — are not exported from the package root. They cannot be imported from @jaeungkim/gantt-chart.

TaskGraph

buildTaskGraph

findPath

canLink