Graph
Defined in: packages/data/src/graph/graph.ts:32
An undirected graph held as a sparse adjacency list.
The backing is Map<N, Map<N, E>> — an adjacency list, as the sparse case
this package favours wants, rather than an adjacency matrix that would cost
O(n²) regardless of how few edges exist. The inner Map rather than a set is
what carries the edge label and keeps hasEdge/edgeLabel O(1).
An edge is stored under both endpoints, so addEdge(a, b) makes b a
neighbor of a and a a neighbor of b; edgeCount() still counts it
once. A self-loop is stored once and counts once toward degree.
Edge weights are just labels here. The ordering a weighted algorithm needs
belongs to that algorithm (@ac-kit/algo), not to the representation — which
is why this package carries no numeric dependency.
Time complexity: O(1) for every node and edge operation; O(degree) to delete a node, since each neighbor’s own adjacency has to drop it. Space is O(nodes
- 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”IGraph<N,E>
Constructors
Section titled “Constructors”Constructor
Section titled “Constructor”new Graph<
N,E>(nodes?):Graph<N,E>
Defined in: packages/data/src/graph/graph.ts:39
Parameters
Section titled “Parameters”nodes?
Section titled “nodes?”Iterable<N, any, any>
Returns
Section titled “Returns”Graph<N, E>
Methods
Section titled “Methods”addEdge()
Section titled “addEdge()”addEdge(
from,to,label):void
Defined in: packages/data/src/graph/graph.ts:105
Adds an undirected edge, creating either endpoint if it is unknown. Re-adding an existing edge replaces its label rather than duplicating it. 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/graph.ts:56
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/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/graph.ts:177
The number of adjacent nodes; a self-loop counts once. 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/graph.ts:120
O(1).
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/graph.ts:70
Removes node and every edge touching 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/graph.ts:51
Each undirected edge once, not twice. O(1).
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/graph.ts:146
O(1).
Parameters
Section titled “Parameters”N
N
Returns
Section titled “Returns”E | undefined
The label, or undefined when there is no such edge. An unlabeled
graph (E = void) returns undefined either way — ask hasEdge
instead.
Implementation of
Section titled “Implementation of”edges()
Section titled “edges()”edges():
IterableIterator<readonly [N,N,E]>
Defined in: packages/data/src/graph/graph.ts:151
Each undirected edge once, oriented as first encountered.
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/graph.ts:135
O(1). Symmetric: the edge is undirected.
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/graph.ts:91
O(1).
Parameters
Section titled “Parameters”N
Returns
Section titled “Returns”boolean
Implementation of
Section titled “Implementation of”neighbors()
Section titled “neighbors()”neighbors(
node):IterableIterator<N>
Defined in: packages/data/src/graph/graph.ts:168
Empty for an unknown node.
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/graph.ts:46
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/graph.ts:96
In first-insertion order.
Returns
Section titled “Returns”IterableIterator<N>