Skip to main content

Class: DirectedAcyclicGraph<T>

Defined in: utilities/directed-acyclic-graph.ts:11

A directed acyclic graph (DAG) of unique nodes (by reference equality) connected by "must run before" edges.

  • addEdge(from, to) declares that from must be ordered before to.
  • topologicalSort() returns every node in an order that respects every edge; nodes with no ordering constraint between them keep their relative insertion order (a stable sort).
  • Adding an edge that would create a cycle throws instead of silently producing an unusable graph.

Type Parameters​

T​

T

Constructors​

Constructor​

new DirectedAcyclicGraph<T>(nodeLabel?): DirectedAcyclicGraph<T>

Defined in: utilities/directed-acyclic-graph.ts:24

Create a new, empty DirectedAcyclicGraph.

Parameters​

nodeLabel?​

(node) => string

Formats a node for error messages (e.g. when a cycle or a reference to an unknown node is detected). Defaults to String(node).

Returns​

DirectedAcyclicGraph<T>

Accessors​

size​

Get Signature​

get size(): number

Defined in: utilities/directed-acyclic-graph.ts:34

Number of nodes in the graph.

Returns​

number

Methods​

addEdge()​

addEdge(from, to): void

Defined in: utilities/directed-acyclic-graph.ts:62

Declares that from must be ordered before to. Adding the same edge twice is a no-op.

Parameters​

from​

T

The node that must come first. Must already be in the graph.

to​

T

The node that must come after from. Must already be in the graph.

Returns​

void

Throws​

An error if either node hasn't been added yet, if from and to are the same node, or if the edge would create a cycle.

addNode()​

addNode(node): void

Defined in: utilities/directed-acyclic-graph.ts:42

Adds a node to the graph. Adding a node that's already present is a no-op.

Parameters​

node​

T

The node to add (unique by reference).

Returns​

void

has()​

has(node): boolean

Defined in: utilities/directed-acyclic-graph.ts:117

Parameters​

node​

T

The node to check.

Returns​

boolean

Whether node has been added to the graph.

removeNode()​

removeNode(node): void

Defined in: utilities/directed-acyclic-graph.ts:98

Removes a node and every edge connected to it. Removing a node that isn't in the graph is a no-op.

Parameters​

node​

T

The node to remove.

Returns​

void

topologicalSort()​

topologicalSort(): T[]

Defined in: utilities/directed-acyclic-graph.ts:125

Returns​

T[]

Every node in an order that respects every declared edge, with nodes that have no ordering constraint between them kept in insertion order.