AbstractGraph
data-structure-typed / AbstractGraph
Abstract Class: AbstractGraph<V, E, VO, EO>
Defined in: data-structures/graph/abstract-graph.ts:51
Abstract graph over vertices and edges.
Remarks
Time O(1), Space O(1)
Example
examples will be generated by unit test
Extends
IterableEntryBase<VertexKey,V|undefined>
Extended by
Type Parameters
V
V = any
Vertex value type.
E
E = any
Edge value type.
VO
VO extends AbstractVertex<V> = AbstractVertex<V>
Concrete vertex subclass (extends AbstractVertex
EO
EO extends AbstractEdge<E> = AbstractEdge<E>
Concrete edge subclass (extends AbstractEdge
Implements
IGraph<V,E,VO,EO>
Constructors
Constructor
new AbstractGraph<V, E, VO, EO>(options?): AbstractGraph<V, E, VO, EO>;
Defined in: data-structures/graph/abstract-graph.ts:65
Construct a graph with runtime defaults.
Parameters
options?
Partial<Record<string, unknown>>
GraphOptions<V> in options.graph (e.g. vertexValueInitializer, defaultEdgeWeight).
Returns
AbstractGraph<V, E, VO, EO>
Remarks
Time O(1), Space O(1)
Overrides
IterableEntryBase<VertexKey, V | undefined>.constructor
Accessors
size
Get Signature
get size(): number;
Defined in: data-structures/graph/abstract-graph.ts:85
Total number of entries.
Remarks
Time O(1), Space O(1)
Returns
number
Entry count.
Overrides
Methods
[iterator]()
iterator: IterableIterator<[VertexKey, V | undefined]>;
Defined in: data-structures/base/iterable-entry-base.ts:22
Default iterator yielding [key, value] entries.
Parameters
args
...unknown[]
Returns
IterableIterator<[VertexKey, V | undefined]>
Iterator of [K, V].
Remarks
Time O(n) to iterate, Space O(1)
Inherited from
addEdge()
Add an edge by instance or by (src, dest, weight?, value?).
Param
Edge instance or source vertex/key.
Param
Destination vertex/key (when adding by pair).
Param
Edge weight.
Param
Edge payload.
Remarks
Time O(1) avg, Space O(1)
Call Signature
addEdge(edge): boolean;
Defined in: data-structures/graph/abstract-graph.ts:258
Parameters
edge
EO
Returns
boolean
Call Signature
addEdge(
src,
dest,
weight?,
value?): boolean;
Defined in: data-structures/graph/abstract-graph.ts:260
Parameters
src
VertexKey | VO
dest
VertexKey | VO
weight?
number
value?
E
Returns
boolean
addVertex()
Add a vertex by key/value or by pre-built vertex.
Param
Vertex key or existing vertex instance.
Param
Optional payload.
Remarks
Time O(1) avg, Space O(1)
Call Signature
addVertex(vertex): boolean;
Defined in: data-structures/graph/abstract-graph.ts:193
Parameters
vertex
VO
Returns
boolean
Implementation of
IGraph.addVertex
Call Signature
addVertex(key, value?): boolean;
Defined in: data-structures/graph/abstract-graph.ts:195
Parameters
key
VertexKey
value?
V
Returns
boolean
Implementation of
IGraph.addVertex
bellmanFord()
bellmanFord(
src,
scanNegativeCycle?,
getMin?,
genPath?): object;
Defined in: data-structures/graph/abstract-graph.ts:677
Bellman-Ford single-source shortest paths with option to scan negative cycles.
Parameters
src
VertexKey | VO
Source vertex or key.
scanNegativeCycle?
boolean
If true, also detect negative cycles.
getMin?
boolean
If true, compute global minimum distance.
genPath?
boolean
If true, generate path arrays via predecessor map.
Returns
object
Result bag including distances, predecessors, and optional cycle flag.
distMap
distMap: Map<VO, number>;
hasNegativeCycle
hasNegativeCycle: boolean | undefined;
min
min: number;
minPath
minPath: VO[];
paths
paths: VO[][];
preMap
preMap: Map<VO, VO>;
Remarks
Time O(V * E), Space O(V + E)
clear()
abstract clear(): void;
Defined in: data-structures/base/iterable-entry-base.ts:218
Remove all entries.
Returns
void
Remarks
Time O(n) typical, Space O(1)
Implementation of
IGraph.clear
Inherited from
clone()
clone(): this;
Defined in: data-structures/graph/abstract-graph.ts:899
Create a deep clone of the graph with the same species.
Returns
this
A new graph of the same concrete class (this type).
Remarks
Time O(V + E), Space O(V + E)
Implementation of
IGraph.clone
Overrides
createEdge()
abstract createEdge(
srcOrV1,
destOrV2,
weight?,
value?): EO;
Defined in: data-structures/graph/abstract-graph.ts:115
Create a new edge instance (implementation specific).
Parameters
srcOrV1
VertexKey
Source/endpoint A key.
destOrV2
VertexKey
Destination/endpoint B key.
weight?
number
Edge weight (defaults may apply).
value?
E
Edge payload.
Returns
EO
Concrete edge instance.
Remarks
Time O(1), Space O(1)
Implementation of
IGraph.createEdge
createVertex()
abstract createVertex(key, value?): VO;
Defined in: data-structures/graph/abstract-graph.ts:104
Create a new vertex instance (implementation specific).
Parameters
key
VertexKey
Vertex identifier.
value?
V
Optional payload.
Returns
VO
Concrete vertex instance.
Remarks
Time O(1), Space O(1)
Implementation of
IGraph.createVertex
degreeOf()
abstract degreeOf(vertexOrKey): number;
Defined in: data-structures/graph/abstract-graph.ts:140
Degree of a vertex in this graph model.
Parameters
vertexOrKey
VertexKey | VO
Vertex or key.
Returns
number
Non-negative integer degree.
Remarks
Time O(1) avg, Space O(1)
Implementation of
IGraph.degreeOf
deleteEdge()
abstract deleteEdge(edge): EO | undefined;
Defined in: data-structures/graph/abstract-graph.ts:123
Delete an edge by instance.
Parameters
edge
EO
Edge instance.
Returns
EO | undefined
Removed edge or undefined.
Remarks
Time O(1) avg, Space O(1)
Implementation of
IGraph.deleteEdge
deleteVertex()
abstract deleteVertex(vertexOrKey): boolean;
Defined in: data-structures/graph/abstract-graph.ts:230
Delete a vertex and its incident edges.
Parameters
vertexOrKey
VertexKey | VO
Vertex or key.
Returns
boolean
true if removed; otherwise false.
Remarks
Time O(deg), Space O(1)
Implementation of
IGraph.deleteVertex
dijkstraWithoutHeap()
dijkstraWithoutHeap(
src,
dest?,
getMinDist?,
genPaths?): DijkstraResult<VO>;
Defined in: data-structures/graph/abstract-graph.ts:478
Dijkstra without heap (array-based selection).
Parameters
src
VertexKey | VO
Source vertex or key.
dest?
VertexKey | VO | undefined
Optional destination for early stop.
getMinDist?
boolean = false
If true, compute global minimum distance.
genPaths?
boolean = false
If true, also generate path arrays.
Returns
DijkstraResult<VO>
Result bag or undefined if source missing.
Remarks
Time O(V^2 + E), Space O(V + E)
edgeSet()
abstract edgeSet(): EO[];
Defined in: data-structures/graph/abstract-graph.ts:147
All edges in the graph (unique, order not guaranteed).
Returns
EO[]
Array of edges.
Remarks
Time O(E), Space O(E)
Implementation of
IGraph.edgeSet
edgesOf()
abstract edgesOf(vertexOrKey): EO[];
Defined in: data-structures/graph/abstract-graph.ts:155
Incident edges of a vertex.
Parameters
vertexOrKey
VertexKey | VO
Vertex or key.
Returns
EO[]
Array of incident edges.
Remarks
Time O(deg), Space O(deg)
Implementation of
IGraph.edgesOf
entries()
entries(): IterableIterator<[VertexKey, V | undefined]>;
Defined in: data-structures/base/iterable-entry-base.ts:31
Iterate over [key, value] pairs (may yield undefined values).
Returns
IterableIterator<[VertexKey, V | undefined]>
Iterator of [K, V | undefined].
Remarks
Time O(n), Space O(1)
Inherited from
every()
every(predicate, thisArg?): boolean;
Defined in: data-structures/base/iterable-entry-base.ts:66
Test whether all entries satisfy the predicate.
Parameters
predicate
EntryCallback<VertexKey, V | undefined, boolean>
(key, value, index, self) => boolean.
thisArg?
unknown
Optional this for callback.
Returns
boolean
true if all pass; otherwise false.
Remarks
Time O(n), Space O(1)
Inherited from
filter()
filter(predicate, thisArg?): this;
Defined in: data-structures/graph/abstract-graph.ts:847
Induced-subgraph filter: keep vertices where predicate(key, value) is true,
and only keep edges whose endpoints both survive.
Parameters
predicate
EntryCallback<VertexKey, V | undefined, boolean>
(key, value, index, self) => boolean.
thisArg?
unknown
Optional this for callback.
Returns
this
A new graph of the same concrete class (this type).
Remarks
Time O(V + E), Space O(V + E)
Implementation of
IGraph.filter
Overrides
filterEntries()
filterEntries(predicate, thisArg?): [VertexKey, V | undefined][];
Defined in: data-structures/graph/abstract-graph.ts:863
Preserve the old behavior: return filtered entries as an array.
Parameters
predicate
EntryCallback<VertexKey, V | undefined, boolean>
thisArg?
unknown
Returns
[VertexKey, V | undefined][]
Remarks
Time O(V), Space O(V)
find()
find(callbackfn, thisArg?): [VertexKey, V | undefined] | undefined;
Defined in: data-structures/base/iterable-entry-base.ts:114
Find the first entry that matches a predicate.
Parameters
callbackfn
EntryCallback<VertexKey, V | undefined, boolean>
(key, value, index, self) => boolean.
thisArg?
unknown
Optional this for callback.
Returns
[VertexKey, V | undefined] | undefined
Matching [key, value] or undefined.
Remarks
Time O(n), Space O(1)
Inherited from
floydWarshall()
floydWarshall(): object;
Defined in: data-structures/graph/abstract-graph.ts:760
Floyd–Warshall all-pairs shortest paths.
Returns
object
{ costs, predecessor } matrices.
costs
costs: number[][];
predecessor
predecessor: (VO | undefined)[][];
Remarks
Time O(V^3), Space O(V^2)
forEach()
forEach(callbackfn, thisArg?): void;
Defined in: data-structures/base/iterable-entry-base.ts:99
Visit each entry, left-to-right.
Parameters
callbackfn
EntryCallback<VertexKey, V | undefined, void>
(key, value, index, self) => void.
thisArg?
unknown
Optional this for callback.
Returns
void
Remarks
Time O(n), Space O(1)
Inherited from
get()
get(key): V | undefined;
Defined in: data-structures/base/iterable-entry-base.ts:156
Get the value under a key.
Parameters
key
VertexKey
Key to look up.
Returns
V | undefined
Value or undefined.
Remarks
Time O(n) generic, Space O(1)
Inherited from
getAllPathsBetween()
getAllPathsBetween(
v1,
v2,
limit?): VO[][];
Defined in: data-structures/graph/abstract-graph.ts:316
Enumerate simple paths up to a limit.
Parameters
v1
VertexKey | VO
Source vertex or key.
v2
VertexKey | VO
Destination vertex or key.
limit?
number = 1000
Maximum number of paths to collect.
Returns
VO[][]
Array of paths (each path is an array of vertices).
Remarks
Time O(paths) worst-case exponential, Space O(V + paths)
getCycles()
getCycles(isInclude2Cycle?): VertexKey[][];
Defined in: data-structures/graph/abstract-graph.ts:796
Enumerate simple cycles (may be expensive).
Parameters
isInclude2Cycle?
boolean = false
If true, include 2-cycles when graph semantics allow.
Returns
VertexKey[][]
Array of cycles (each as array of vertex keys).
Remarks
Time exponential in worst-case, Space O(V + E)
getEdge()
abstract getEdge(srcOrKey, destOrKey): EO | undefined;
Defined in: data-structures/graph/abstract-graph.ts:132
Get an edge between two vertices if present.
Parameters
srcOrKey
VertexKey | VO
Source/endpoint A vertex or key.
destOrKey
VertexKey | VO
Destination/endpoint B vertex or key.
Returns
EO | undefined
Edge instance or undefined.
Remarks
Time O(1) avg, Space O(1)
Implementation of
IGraph.getEdge
getEndsOfEdge()
abstract getEndsOfEdge(edge): [VO, VO] | undefined;
Defined in: data-structures/graph/abstract-graph.ts:171
Resolve endpoints of an edge to vertex instances.
Parameters
edge
EO
Edge instance.
Returns
[VO, VO] | undefined
[v1, v2] or undefined if missing.
Remarks
Time O(1), Space O(1)
Implementation of
IGraph.getEndsOfEdge
getMinCostBetween()
getMinCostBetween(
v1,
v2,
isWeight?): number | undefined;
Defined in: data-structures/graph/abstract-graph.ts:364
Minimum hops/weight between two vertices.
Parameters
v1
VertexKey | VO
Source vertex or key.
v2
VertexKey | VO
Destination vertex or key.
isWeight?
boolean
If true, compare by path weight; otherwise by hop count.
Returns
number | undefined
Minimum cost or undefined if missing/unreachable.
Remarks
Time O((V + E) log V) weighted / O(V + E) unweighted, Space O(V + E)
getMinPathBetween()
getMinPathBetween(
v1,
v2,
isWeight?,
isDFS?): VO[] | undefined;
Defined in: data-structures/graph/abstract-graph.ts:414
Minimum path (as vertex sequence) between two vertices.
Parameters
v1
VertexKey | VO
Source vertex or key.
v2
VertexKey | VO
Destination vertex or key.
isWeight?
boolean
If true, compare by path weight; otherwise by hop count.
isDFS?
boolean = false
For weighted mode only: if true, brute-force all paths; if false, use Dijkstra.
Returns
VO[] | undefined
Vertex sequence, or undefined/empty when unreachable depending on branch.
Remarks
Time O((V + E) log V) weighted / O(V + E) unweighted, Space O(V + E)
getNeighbors()
abstract getNeighbors(vertexOrKey): VO[];
Defined in: data-structures/graph/abstract-graph.ts:163
One-step neighbors of a vertex.
Parameters
vertexOrKey
VertexKey | VO
Vertex or key.
Returns
VO[]
Array of neighbor vertices.
Remarks
Time O(deg), Space O(deg)
Implementation of
IGraph.getNeighbors
getPathSumWeight()
getPathSumWeight(path): number;
Defined in: data-structures/graph/abstract-graph.ts:348
Sum the weights along a vertex path.
Parameters
path
VO[]
Sequence of vertices.
Returns
number
Path weight sum (0 if empty or edge missing).
Remarks
Time O(L), Space O(1) where L is path length
getVertex()
getVertex(vertexKey): VO | undefined;
Defined in: data-structures/graph/abstract-graph.ts:179
Get vertex instance by key.
Parameters
vertexKey
VertexKey
Vertex key.
Returns
VO | undefined
Vertex instance or undefined.
Remarks
Time O(1), Space O(1)
Implementation of
IGraph.getVertex
has()
has(key): boolean;
Defined in: data-structures/base/iterable-entry-base.ts:129
Whether the given key exists.
Parameters
key
VertexKey
Key to test.
Returns
boolean
true if found; otherwise false.
Remarks
Time O(n) generic, Space O(1)
Inherited from
hasEdge()
hasEdge(v1, v2): boolean;
Defined in: data-structures/graph/abstract-graph.ts:253
Whether an edge exists between two vertices.
Parameters
v1
VertexKey | VO
Endpoint A vertex or key.
v2
VertexKey | VO
Endpoint B vertex or key.
Returns
boolean
true if present; otherwise false.
Remarks
Time O(1) avg, Space O(1)
hasValue()
hasValue(value): boolean;
Defined in: data-structures/base/iterable-entry-base.ts:143
Whether there exists an entry with the given value.
Parameters
value
V | undefined
Value to test.
Returns
boolean
true if found; otherwise false.
Remarks
Time O(n), Space O(1)
Inherited from
hasVertex()
hasVertex(vertexOrKey): boolean;
Defined in: data-structures/graph/abstract-graph.ts:189
Whether a vertex exists.
Parameters
vertexOrKey
VertexKey | VO
Vertex or key.
Returns
boolean
true if present, otherwise false.
Remarks
Time O(1) avg, Space O(1)
Implementation of
IGraph.hasVertex
isEmpty()
abstract isEmpty(): boolean;
Defined in: data-structures/base/iterable-entry-base.ts:212
Whether there are no entries.
Returns
boolean
true if empty; false otherwise.
Remarks
Time O(1) typical, Space O(1)
Implementation of
IGraph.isEmpty
Inherited from
isVertexKey()
isVertexKey(potentialKey): potentialKey is VertexKey;
Defined in: data-structures/graph/abstract-graph.ts:219
Type guard: check if a value is a valid vertex key.
Parameters
potentialKey
unknown
Value to test.
Returns
potentialKey is VertexKey
true if string/number; else false.
Remarks
Time O(1), Space O(1)
keys()
keys(): IterableIterator<VertexKey>;
Defined in: data-structures/base/iterable-entry-base.ts:42
Iterate over keys only.
Returns
IterableIterator<VertexKey>
Iterator of keys.
Remarks
Time O(n), Space O(1)
Inherited from
map()
map<T>(callback, thisArg?): T[];
Defined in: data-structures/graph/abstract-graph.ts:878
Map entries using an implementation-specific strategy.
Type Parameters
T
T
Parameters
callback
EntryCallback<VertexKey, V | undefined, T>
thisArg?
unknown
Returns
T[]
Remarks
Time O(n), Space O(n)
Overrides
print()
print(options?): void;
Defined in: data-structures/graph/abstract-graph.ts:984
Print the graph to console.
Parameters
options?
Display settings passed to toVisual.
showWeight?
boolean
Returns
void
Overrides
reduce()
reduce<U>(callbackfn, initialValue): U;
Defined in: data-structures/base/iterable-entry-base.ts:171
Reduce entries into a single accumulator.
Type Parameters
U
U
Parameters
callbackfn
ReduceEntryCallback<VertexKey, V | undefined, U>
(acc, value, key, index, self) => acc.
initialValue
U
Initial accumulator.
Returns
U
Final accumulator.
Remarks
Time O(n), Space O(1)
Inherited from
removeManyVertices()
removeManyVertices(vertexMap): boolean;
Defined in: data-structures/graph/abstract-graph.ts:238
Delete multiple vertices.
Parameters
vertexMap
VO[] | VertexKey[]
Array of vertices or keys.
Returns
boolean
true if any vertex was removed.
Remarks
Time O(sum(deg)), Space O(1)
setEdgeWeight()
setEdgeWeight(
srcOrKey,
destOrKey,
weight): boolean;
Defined in: data-structures/graph/abstract-graph.ts:298
Set the weight of an existing edge.
Parameters
srcOrKey
VertexKey | VO
Source vertex or key.
destOrKey
VertexKey | VO
Destination vertex or key.
weight
number
New weight.
Returns
boolean
true if updated; otherwise false.
Remarks
Time O(1) avg, Space O(1)
some()
some(predicate, thisArg?): boolean;
Defined in: data-structures/base/iterable-entry-base.ts:83
Test whether any entry satisfies the predicate.
Parameters
predicate
EntryCallback<VertexKey, V | undefined, boolean>
(key, value, index, self) => boolean.
thisArg?
unknown
Optional this for callback.
Returns
boolean
true if any passes; otherwise false.
Remarks
Time O(n), Space O(1)
Inherited from
toArray()
toArray(): [VertexKey, V | undefined][];
Defined in: data-structures/base/iterable-entry-base.ts:186
Converts data structure to [key, value] pairs.
Returns
[VertexKey, V | undefined][]
Array of entries.
Remarks
Time O(n), Space O(n)
Inherited from
toDot()
toDot(options?): string;
Defined in: data-structures/graph/abstract-graph.ts:952
Generate DOT language representation for Graphviz.
Parameters
options?
Optional display settings.
name?
string
Graph name (default: 'G').
showWeight?
boolean
Whether to label edges with weight (default: true).
Returns
string
DOT format string.
toVisual()
toVisual(options?): string;
Defined in: data-structures/graph/abstract-graph.ts:920
Generate a text-based visual representation of the graph.
Adjacency list format:
Graph (5 vertices, 6 edges):
A -> B (1), C (2)
B -> D (3)
C -> (no outgoing edges)
D -> A (1)
E (isolated)
Parameters
options?
Optional display settings.
showWeight?
boolean
Whether to show edge weights (default: true).
Returns
string
The visual string.
Overrides
values()
values(): IterableIterator<V | undefined>;
Defined in: data-structures/base/iterable-entry-base.ts:53
Iterate over values only.
Returns
IterableIterator<V | undefined>
Iterator of values.
Remarks
Time O(n), Space O(1)
Inherited from
Protected Members
_edgeConnector
Get Signature
get protected _edgeConnector(): string;
Defined in: data-structures/graph/abstract-graph.ts:93
The edge connector string used in visual output. Override in subclasses (e.g., '--' for undirected, '->' for directed).
Returns
string
_addEdge()
abstract protected _addEdge(edge): boolean;
Defined in: data-structures/graph/abstract-graph.ts:1081
Internal hook to attach an edge into adjacency structures.
Parameters
edge
EO
Edge instance.
Returns
boolean
true if inserted; otherwise false.
Remarks
Time O(1) avg, Space O(1)
_addVertex()
protected _addVertex(newVertex): boolean;
Defined in: data-structures/graph/abstract-graph.ts:1089
Insert a pre-built vertex into the graph.
Parameters
newVertex
VO
Concrete vertex instance.
Returns
boolean
true if inserted; false if key already exists.
Remarks
Time O(1) avg, Space O(1)
_createInstance()
protected _createInstance(_options?): this;
Defined in: data-structures/graph/abstract-graph.ts:1022
Create an empty graph instance of the same concrete species.
Parameters
_options?
Partial<Record<string, unknown>>
Snapshot options from _snapshotOptions().
Returns
this
A new empty graph instance of this type.
Remarks
Time O(1), Space O(1)
_createLike()
protected _createLike(iter?, options?): this;
Defined in: data-structures/graph/abstract-graph.ts:1044
Create a same-species graph populated with entries; preserves edges among kept vertices.
Parameters
iter?
Iterable<[VertexKey, V | undefined], any, any>
Optional entries to seed the new graph.
options?
Partial<Record<string, unknown>>
Snapshot options.
Returns
this
A new graph of this type.
Remarks
Time O(V + E), Space O(V + E)
_getIterator()
protected _getIterator(): IterableIterator<[VertexKey, V | undefined]>;
Defined in: data-structures/graph/abstract-graph.ts:993
Internal iterator over [key, value] entries in insertion order.
Returns
IterableIterator<[VertexKey, V | undefined]>
Iterator of [VertexKey, V | undefined].
Remarks
Time O(V), Space O(1)
Overrides
IterableEntryBase._getIterator
_getVertex()
protected _getVertex(vertexOrKey): VO | undefined;
Defined in: data-structures/graph/abstract-graph.ts:1103
Resolve a vertex key or instance to the concrete vertex instance.
Parameters
vertexOrKey
VertexKey | VO
Vertex key or existing vertex.
Returns
VO | undefined
Vertex instance or undefined.
Remarks
Time O(1), Space O(1)
_getVertexKey()
protected _getVertexKey(vertexOrKey): VertexKey;
Defined in: data-structures/graph/abstract-graph.ts:1114
Resolve a vertex key from a key or vertex instance.
Parameters
vertexOrKey
VertexKey | VO
Vertex key or existing vertex.
Returns
VertexKey
The vertex key.
Remarks
Time O(1), Space O(1)
_snapshotOptions()
protected _snapshotOptions(): Record<string, unknown>;
Defined in: data-structures/graph/abstract-graph.ts:1008
Capture configuration needed to reproduce the current graph.
Returns
Record<string, unknown>
Options bag (opaque to callers).
Remarks
Time O(1), Space O(1)