DirectedGraph
Defined in: packages/data/src/graph/directed-graph.ts:30
A directed graph held as two sparse adjacency lists, one per direction.
Keeping both is what makes inNeighbors/inDegree O(1) rather than a scan
of every node’s out-edges; the cost is a second Map entry per edge. Labels
live on the out-adjacency and are mirrored into the in-adjacency.
addEdge(a, b) adds a → b only. a → b and b → a are distinct edges
that may carry different labels, and edgeCount() counts each.
neighbors/degree are inherited from IGraph and resolve the directed way
round: neighbors is the out-neighbors — what a traversal follows —
while degree is inDegree + outDegree, the graph-theoretic degree. Use
outNeighbors/outDegree explicitly wherever that distinction matters to a
reader.
Time complexity: O(1) for every node and edge operation; O(degree) to delete a node. Space is O(nodes + 2·edges).
Nodes are compared by SameValueZero, native Map semantics.
Type Parameters
Section titled “Type Parameters”N
The node type.
E extends DefinedValue | void = void
The edge label type. void for an unlabeled graph, in which case
addEdge’s third argument may be omitted.
Implements
Section titled “Implements”IDirectedGraph<N,E>
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new DirectedGraph<
N,E>(nodes?):DirectedGraph<N,E>
Defined in: packages/data/src/graph/directed-graph.ts:38
Parameters
Section titled “Parameters”nodes?
Section titled “nodes?”Iterable<N, any, any>
Returns
Section titled “Returns”DirectedGraph<N, E>
Methods
Section titled “Methods”addEdge()
Section titled “addEdge()”addEdge(
from,to,label):void
Defined in: packages/data/src/graph/directed-graph.ts:113
Adds the directed edge from → to, creating either endpoint if it is
unknown. Re-adding an existing edge replaces its label. O(1).
Parameters
Section titled “Parameters”N
N
E
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”addNode()
Section titled “addNode()”addNode(
node):void
Defined in: packages/data/src/graph/directed-graph.ts:55
O(1). A node already present keeps its edges.
Parameters
Section titled “Parameters”N
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”addNodes()
Section titled “addNodes()”addNodes(
nodes):void
Defined in: packages/data/src/graph/directed-graph.ts:63
O(m) in the number of nodes.
Parameters
Section titled “Parameters”Iterable<N>
Returns
Section titled “Returns”void
Implementation of
Section titled “Implementation of”degree()
Section titled “degree()”degree(
node):number
Defined in: packages/data/src/graph/directed-graph.ts:172
inDegree + outDegree. A self-loop contributes to both. O(1).
Parameters
Section titled “Parameters”N
Returns
Section titled “Returns”number
Implementation of
Section titled “Implementation of”deleteEdge()
Section titled “deleteEdge()”deleteEdge(
from,to):boolean
Defined in: packages/data/src/graph/directed-graph.ts:128
O(1). Directed: this does not touch to → from.
Parameters
Section titled “Parameters”N
N
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”deleteNode()
Section titled “deleteNode()”deleteNode(
node):boolean
Defined in: packages/data/src/graph/directed-graph.ts:70
Removes node and every edge into or out of it. O(degree).
Parameters
Section titled “Parameters”N
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”edgeCount()
Section titled “edgeCount()”edgeCount():
number
Defined in: packages/data/src/graph/directed-graph.ts:50
O(1). a → b and b → a count as two.
Returns
Section titled “Returns”number
Implementation of
Section titled “Implementation of”edgeLabel()
Section titled “edgeLabel()”edgeLabel(
from,to):E|undefined
Defined in: packages/data/src/graph/directed-graph.ts:153
O(1).
Parameters
Section titled “Parameters”N
N
Returns
Section titled “Returns”E | undefined
The label of from → to, or undefined when there is no such
edge.
Implementation of
Section titled “Implementation of”edges()
Section titled “edges()”edges():
IterableIterator<readonly [N,N,E]>
Defined in: packages/data/src/graph/directed-graph.ts:158
Every directed edge, grouped by source.
Returns
Section titled “Returns”IterableIterator<readonly [N, N, E]>
Implementation of
Section titled “Implementation of”hasEdge()
Section titled “hasEdge()”hasEdge(
from,to):boolean
Defined in: packages/data/src/graph/directed-graph.ts:143
O(1). Directed: hasEdge(a, b) says nothing about b → a.
Parameters
Section titled “Parameters”N
N
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”hasNode()
Section titled “hasNode()”hasNode(
node):boolean
Defined in: packages/data/src/graph/directed-graph.ts:100
O(1).
Parameters
Section titled “Parameters”N
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”inDegree()
Section titled “inDegree()”inDegree(
node):number
Defined in: packages/data/src/graph/directed-graph.ts:195
O(1).
Parameters
Section titled “Parameters”N
Returns
Section titled “Returns”number
Implementation of
Section titled “Implementation of”inNeighbors()
Section titled “inNeighbors()”inNeighbors(
node):IterableIterator<N>
Defined in: packages/data/src/graph/directed-graph.ts:177
Nodes with an edge into node. Empty for an unknown node.
Parameters
Section titled “Parameters”N
Returns
Section titled “Returns”IterableIterator<N>
Implementation of
Section titled “Implementation of”neighbors()
Section titled “neighbors()”neighbors(
node):IterableIterator<N>
Defined in: packages/data/src/graph/directed-graph.ts:167
The out-neighbors — what a traversal follows. See the class note.
Parameters
Section titled “Parameters”N
Returns
Section titled “Returns”IterableIterator<N>
Implementation of
Section titled “Implementation of”nodeCount()
Section titled “nodeCount()”nodeCount():
number
Defined in: packages/data/src/graph/directed-graph.ts:45
O(1).
Returns
Section titled “Returns”number
Implementation of
Section titled “Implementation of”nodes()
Section titled “nodes()”nodes():
IterableIterator<N>
Defined in: packages/data/src/graph/directed-graph.ts:105
In first-insertion order.
Returns
Section titled “Returns”IterableIterator<N>
Implementation of
Section titled “Implementation of”outDegree()
Section titled “outDegree()”outDegree(
node):number
Defined in: packages/data/src/graph/directed-graph.ts:200
O(1).
Parameters
Section titled “Parameters”N
Returns
Section titled “Returns”number
Implementation of
Section titled “Implementation of”outNeighbors()
Section titled “outNeighbors()”outNeighbors(
node):IterableIterator<N>
Defined in: packages/data/src/graph/directed-graph.ts:186
Nodes node has an edge to. Empty for an unknown node.
Parameters
Section titled “Parameters”N
Returns
Section titled “Returns”IterableIterator<N>