DirectedGraph
data-structure-typed / DirectedGraph
Class: DirectedGraph<V, E, VO, EO>
Defined in: data-structures/graph/directed-graph.ts:118
Directed graph implementation.
Remarks
Time O(1), Space O(1)
Examples
// basic DirectedGraph vertex and edge creation
// Create a simple directed graph
const graph = new DirectedGraph<string>();
// Add vertices
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
// Verify vertices exist
console.log(graph.hasVertex('A')); // true;
console.log(graph.hasVertex('B')); // true;
console.log(graph.hasVertex('C')); // true;
console.log(graph.hasVertex('D')); // false;
// Check vertex count
console.log(graph.size); // 3;
// DirectedGraph edge operations
const graph = new DirectedGraph<string>();
// Add vertices
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
// Add directed edges
graph.addEdge('A', 'B', 1);
graph.addEdge('B', 'C', 2);
graph.addEdge('A', 'C', 3);
// Verify edges exist
console.log(graph.hasEdge('A', 'B')); // true;
console.log(graph.hasEdge('B', 'C')); // true;
console.log(graph.hasEdge('C', 'B')); // false; // Graph is directed
// Get neighbors of A
const neighborsA = graph.getNeighbors('A');
console.log(neighborsA[0].key); // 'B';
console.log(neighborsA[1].key); // 'C';
// DirectedGraph dijkstra shortest path for network routing
// Build a weighted directed graph representing network nodes and costs
const network = new DirectedGraph<string>();
// Add network nodes
network.addVertex('Router-A');
network.addVertex('Router-B');
network.addVertex('Router-C');
network.addVertex('Router-D');
network.addVertex('Router-E');
// Add weighted edges (network latency costs)
network.addEdge('Router-A', 'Router-B', 5);
network.addEdge('Router-A', 'Router-C', 10);
network.addEdge('Router-B', 'Router-D', 3);
network.addEdge('Router-C', 'Router-D', 2);
network.addEdge('Router-D', 'Router-E', 4);
network.addEdge('Router-B', 'Router-E', 12);
// Find shortest path from Router-A to Router-E
const { minDist, minPath } = network.dijkstra('Router-A', 'Router-E', true, true) || {
minDist: undefined,
minPath: undefined
};
// Verify shortest path is found
console.log(minDist); // defined;
console.log(minPath); // defined;
// Shortest path should be A -> B -> D -> E with cost 5+3+4=12
// Or A -> C -> D -> E with cost 10+2+4=16
// So the minimum is 12
console.log(minDist); // <= 16;
// Verify path is valid (includes start and end)
console.log(minPath?.[0].key); // 'Router-A';
console.log(minPath?.[minPath.length - 1].key); // 'Router-E';
Extends
AbstractGraph<V,E,VO,EO>
Extended by
Type Parameters
V
V = any
Vertex value type.
E
E = any
Edge value type.
VO
VO extends DirectedVertex<V> = DirectedVertex<V>
Concrete vertex class (extends AbstractVertex
EO
EO extends DirectedEdge<E> = DirectedEdge<E>
Concrete edge class (extends AbstractEdge
Implements
IGraph<V,E,VO,EO>
Constructors
Constructor
new DirectedGraph<V, E, VO, EO>(options?): DirectedGraph<V, E, VO, EO>;
Defined in: data-structures/graph/directed-graph.ts:132
Construct a directed graph with runtime defaults.
Parameters
options?
Partial<GraphOptions<V>>
GraphOptions<V> (e.g. vertexValueInitializer, defaultEdgeWeight).
Returns
DirectedGraph<V, E, VO, EO>
Remarks
Time O(1), Space O(1)
Overrides
Accessors
size
Get Signature
get size(): number;
Defined in: data-structures/graph/abstract-graph.ts:89
Total number of entries.
Remarks
Time O(1), Space O(1)
Returns
number
Entry count.
Inherited from
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:254
Parameters
edge
EO
Returns
boolean
Inherited from
Call Signature
addEdge(
src,
dest,
weight?,
value?): boolean;
Defined in: data-structures/graph/abstract-graph.ts:256
Parameters
src
VertexKey | VO
dest
VertexKey | VO
weight?
number
value?
E
Returns
boolean
Inherited from
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:189
Parameters
vertex
VO
Returns
boolean
Implementation of
IGraph.addVertex
Inherited from
Call Signature
addVertex(key, value?): boolean;
Defined in: data-structures/graph/abstract-graph.ts:191
Parameters
key
VertexKey
value?
V
Returns
boolean
Implementation of
IGraph.addVertex
Inherited from
bellmanFord()
bellmanFord(
src,
scanNegativeCycle?,
getMin?,
genPath?): object;
Defined in: data-structures/graph/abstract-graph.ts:705
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)
Inherited from
clear()
clear(): void;
Defined in: data-structures/graph/directed-graph.ts:904
Remove all vertices and edges.
Returns
void
Remarks
Time O(V + E), Space O(1)
Implementation of
IGraph.clear
Overrides
clone()
clone(): this;
Defined in: data-structures/graph/directed-graph.ts:915
Deep clone as the same concrete class.
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()
createEdge(
src,
dest,
weight?,
value?): EO;
Defined in: data-structures/graph/directed-graph.ts:210
Create a directed edge instance. Does not insert into the graph.
Parameters
src
VertexKey
Source vertex key.
dest
VertexKey
Destination vertex key.
weight?
number
Edge weight; defaults to defaultEdgeWeight.
value?
E
Edge payload.
Returns
EO
Concrete edge instance.
Remarks
Time O(1), Space O(1)
Implementation of
IGraph.createEdge
Overrides
createVertex()
createVertex(key, value?): VO;
Defined in: data-structures/graph/directed-graph.ts:197
Create a directed vertex instance. Does not insert into the graph.
Parameters
key
VertexKey
Vertex identifier.
value?
VO["value"]
Optional payload.
Returns
VO
Concrete vertex instance.
Remarks
Time O(1), Space O(1)
Implementation of
IGraph.createVertex
Overrides
degreeOf()
degreeOf(vertexOrKey): number;
Defined in: data-structures/graph/directed-graph.ts:601
Degree (in + out) of a vertex.
Parameters
vertexOrKey
VertexKey | VO
Vertex or key.
Returns
number
Non-negative integer.
Remarks
Time O(1) avg, Space O(1)
Implementation of
IGraph.degreeOf
Overrides
deleteEdge()
deleteEdge(edgeOrSrcVertexKey, destVertexKey?): EO | undefined;
Defined in: data-structures/graph/directed-graph.ts:371
Delete an edge by instance or by (srcKey, destKey).
Parameters
edgeOrSrcVertexKey
VertexKey | EO
Edge instance or source vertex/key.
destVertexKey?
VertexKey
Optional destination vertex/key when deleting by pair.
Returns
EO | undefined
Removed edge or undefined.
Remarks
Time O(1) avg, Space O(1)
Example
// DirectedGraph deleteEdge and vertex operations
const graph = new DirectedGraph<string>();
// Build a small graph
graph.addVertex('X');
graph.addVertex('Y');
graph.addVertex('Z');
graph.addEdge('X', 'Y', 1);
graph.addEdge('Y', 'Z', 2);
// Delete an edge
graph.deleteEdgeSrcToDest('X', 'Y');
console.log(graph.hasEdge('X', 'Y')); // false;
// Edge in other direction should not exist
console.log(graph.hasEdge('Y', 'X')); // false;
// Other edges should remain
console.log(graph.hasEdge('Y', 'Z')); // true;
// Delete a vertex
graph.deleteVertex('Y');
console.log(graph.hasVertex('Y')); // false;
console.log(graph.size); // 2;
Implementation of
IGraph.deleteEdge
Overrides
deleteEdgeSrcToDest()
deleteEdgeSrcToDest(srcOrKey, destOrKey): EO | undefined;
Defined in: data-structures/graph/directed-graph.ts:285
Delete edge src -> dest if present.
Parameters
srcOrKey
VertexKey | VO
Source vertex or key.
destOrKey
VertexKey | VO
Destination vertex or key.
Returns
EO | undefined
Removed edge or undefined.
Remarks
Time O(1) avg, Space O(1)
deleteVertex()
deleteVertex(vertexOrKey): boolean;
Defined in: data-structures/graph/directed-graph.ts:444
Remove a vertex
Parameters
vertexOrKey
VertexKey | VO
Returns
boolean
Example
// Remove a vertex
const g = new DirectedGraph();
g.addVertex('A');
g.addVertex('B');
g.addEdge('A', 'B');
g.deleteVertex('A');
console.log(g.hasVertex('A')); // false;
console.log(g.hasEdge('A', 'B')); // false;
Implementation of
IGraph.deleteVertex
Overrides
dijkstraWithoutHeap()
dijkstraWithoutHeap(
src,
dest?,
getMinDist?,
genPaths?): DijkstraResult<VO>;
Defined in: data-structures/graph/abstract-graph.ts:484
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)
Inherited from
AbstractGraph.dijkstraWithoutHeap
edgeSet()
edgeSet(): EO[];
Defined in: data-structures/graph/directed-graph.ts:804
Get all edges
Returns
EO[]
Example
// Get all edges
const g = new DirectedGraph();
g.addVertex('A');
g.addVertex('B');
g.addEdge('A', 'B', 3);
console.log(g.edgeSet().length); // 1;
Implementation of
IGraph.edgeSet
Overrides
edgesOf()
edgesOf(vertexOrKey): EO[];
Defined in: data-structures/graph/directed-graph.ts:631
All incident edges of a vertex.
Parameters
vertexOrKey
VertexKey | VO
Vertex or key.
Returns
EO[]
Array of incident edges.
Remarks
Time O(deg_in + deg_out), Space O(deg_in + deg_out)
Implementation of
IGraph.edgesOf
Overrides
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:897
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
Inherited from
filterEntries()
filterEntries(predicate, thisArg?): [VertexKey, V | undefined][];
Defined in: data-structures/graph/abstract-graph.ts:913
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)
Inherited from
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:798
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)
Inherited from
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:309
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)
Inherited from
AbstractGraph.getAllPathsBetween
getCycles()
getCycles(isInclude2Cycle?): VertexKey[][];
Defined in: data-structures/graph/abstract-graph.ts:838
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)
Inherited from
getDestinations()
getDestinations(vertex): VO[];
Defined in: data-structures/graph/directed-graph.ts:649
Direct children reachable by one outgoing edge.
Parameters
vertex
VertexKey | VO | undefined
Vertex or key.
Returns
VO[]
Array of neighbor vertices.
Remarks
Time O(deg_out), Space O(deg_out)
getDFNMap()
getDFNMap(): Map<VO, number>;
Defined in: data-structures/graph/directed-graph.ts:1024
DFN index map computed by tarjan().
Returns
Map<VO, number>
Map from vertex to DFN index.
Remarks
Time O(V), Space O(V)
getEdge()
getEdge(srcOrKey, destOrKey): EO | undefined;
Defined in: data-structures/graph/directed-graph.ts:260
Get the unique edge from src to dest, if present.
Parameters
srcOrKey
VertexKey | VO | undefined
Source vertex or key.
destOrKey
VertexKey | VO | undefined
Destination vertex or key.
Returns
EO | undefined
Edge instance or undefined.
Remarks
Time O(1) avg, Space O(1)
Example
// Get edge between vertices
const g = new DirectedGraph();
g.addVertex('A');
g.addVertex('B');
g.addEdge('A', 'B', 5);
const edge = g.getEdge('A', 'B');
console.log(edge?.weight); // 5;
Implementation of
IGraph.getEdge
Overrides
getEndsOfEdge()
getEndsOfEdge(edge): [VO, VO] | undefined;
Defined in: data-structures/graph/directed-graph.ts:879
Resolve an edge's [src, dest] endpoints to vertex instances.
Parameters
edge
EO
Edge instance.
Returns
[VO, VO] | undefined
[src, dest] or undefined if either endpoint is missing.
Remarks
Time O(1), Space O(1)
Implementation of
IGraph.getEndsOfEdge
Overrides
getLowMap()
getLowMap(): Map<VO, number>;
Defined in: data-structures/graph/directed-graph.ts:1033
LOW link map computed by tarjan().
Returns
Map<VO, number>
Map from vertex to LOW value.
Remarks
Time O(V), Space O(V)
getMinCostBetween()
getMinCostBetween(
v1,
v2,
isWeight?): number | undefined;
Defined in: data-structures/graph/abstract-graph.ts:362
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)
Inherited from
AbstractGraph.getMinCostBetween
getMinPathBetween()
getMinPathBetween(
v1,
v2,
isWeight?,
isDFS?): VO[] | undefined;
Defined in: data-structures/graph/abstract-graph.ts:415
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)
Inherited from
AbstractGraph.getMinPathBetween
getNeighbors()
getNeighbors(vertexOrKey): VO[];
Defined in: data-structures/graph/directed-graph.ts:857
Get outgoing neighbors
Parameters
vertexOrKey
VertexKey | VO
Returns
VO[]
Example
// Get outgoing neighbors
const g = new DirectedGraph();
g.addVertex('A');
g.addVertex('B');
g.addVertex('C');
g.addEdge('A', 'B');
g.addEdge('A', 'C');
const neighbors = g.getNeighbors('A');
console.log(neighbors.map(v => v.key).sort()); // ['B', 'C'];
Implementation of
IGraph.getNeighbors
Overrides
getPathSumWeight()
getPathSumWeight(path): number;
Defined in: data-structures/graph/abstract-graph.ts:346
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
Inherited from
AbstractGraph.getPathSumWeight
getSCCs()
getSCCs(): Map<number, VO[]>;
Defined in: data-structures/graph/directed-graph.ts:1084
Strongly connected components computed by tarjan().
Returns
Map<number, VO[]>
Map from SCC id to vertices.
Remarks
Time O(#SCC + V), Space O(V)
Example
// Get strongly connected components
const g = new DirectedGraph();
g.addVertex(1);
g.addVertex(2);
g.addVertex(3);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 1);
const sccs = g.getSCCs(); // Map<number, VO[]>
console.log(sccs.size); // >= 1;
getVertex()
getVertex(vertexKey): VO | undefined;
Defined in: data-structures/graph/abstract-graph.ts:175
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
Inherited from
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:249
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)
Inherited from
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:185
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
Inherited from
incomingEdgesOf()
incomingEdgesOf(vertexOrKey): EO[];
Defined in: data-structures/graph/directed-graph.ts:533
Incoming edges of a vertex.
Parameters
vertexOrKey
VertexKey | VO
Vertex or key.
Returns
EO[]
Array of incoming edges.
Remarks
Time O(deg_in), Space O(deg_in)
Example
// Get incoming edges
const g = new DirectedGraph();
g.addVertex('A');
g.addVertex('B');
g.addVertex('C');
g.addEdge('A', 'C');
g.addEdge('B', 'C');
console.log(g.incomingEdgesOf('C').length); // 2;
isEmpty()
isEmpty(): boolean;
Defined in: data-structures/graph/directed-graph.ts:896
Whether the graph has no vertices and no edges.
Returns
boolean
Remarks
Time O(1), Space O(1)
Implementation of
IGraph.isEmpty
Overrides
isVertexKey()
isVertexKey(potentialKey): potentialKey is VertexKey;
Defined in: data-structures/graph/abstract-graph.ts:215
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)
Inherited from
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:928
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)
Inherited from
outgoingEdgesOf()
outgoingEdgesOf(vertexOrKey): EO[];
Defined in: data-structures/graph/directed-graph.ts:587
Outgoing edges of a vertex.
Parameters
vertexOrKey
VertexKey | VO
Vertex or key.
Returns
EO[]
Array of outgoing edges.
Remarks
Time O(deg_out), Space O(deg_out)
Example
// Get outgoing edges
const g = new DirectedGraph();
g.addVertex('A');
g.addVertex('B');
g.addVertex('C');
g.addEdge('A', 'B');
g.addEdge('A', 'C');
console.log(g.outgoingEdgesOf('A').length); // 2;
print()
print(options?): void;
Defined in: data-structures/graph/abstract-graph.ts:1183
Print the graph to console.
Parameters
options?
Display settings passed to toVisual.
showWeight?
boolean
Returns
void
Inherited from
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:234
Delete multiple vertices.
Parameters
vertexMap
VertexKey[] | VO[]
Array of vertices or keys.
Returns
boolean
true if any vertex was removed.
Remarks
Time O(sum(deg)), Space O(1)
Inherited from
AbstractGraph.removeManyVertices
setEdgeWeight()
setEdgeWeight(
srcOrKey,
destOrKey,
weight): boolean;
Defined in: data-structures/graph/abstract-graph.ts:291
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)
Inherited from
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
tarjan()
tarjan(): object;
Defined in: data-structures/graph/directed-graph.ts:968
Tarjan's algorithm for strongly connected components.
Returns
object
{ dfnMap, lowMap, SCCs }.
dfnMap
dfnMap: Map<VO, number>;
lowMap
lowMap: Map<VO, number>;
SCCs
SCCs: Map<number, VO[]>;
Remarks
Time O(V + E), Space O(V + E)
Example
// Find strongly connected components
const g = new DirectedGraph();
g.addVertex('A');
g.addVertex('B');
g.addVertex('C');
g.addEdge('A', 'B');
g.addEdge('B', 'C');
g.addEdge('C', 'A');
const { SCCs } = g.tarjan();
// A→B→C→A forms one SCC with 3 members
const sccArrays = [...SCCs.values()];
console.log(sccArrays.some(scc => scc.length === 3)); // true;
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:1143
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.
Inherited from
topologicalSort()
topologicalSort(propertyName?): (VertexKey | VO)[] | undefined;
Defined in: data-structures/graph/directed-graph.ts:726
Topological sort if DAG; returns undefined if a cycle exists.
Parameters
propertyName?
"key" | "vertex"
'key' to map to keys; 'vertex' to keep instances.
Returns
(VertexKey | VO)[] | undefined
Array of keys/vertices, or undefined when cycle is found.
Remarks
Time O(V + E), Space O(V)
Example
// DirectedGraph topologicalSort for task scheduling
const graph = new DirectedGraph<string>();
// Build a DAG (Directed Acyclic Graph) for task dependencies
graph.addVertex('Design');
graph.addVertex('Implement');
graph.addVertex('Test');
graph.addVertex('Deploy');
// Add dependency edges
graph.addEdge('Design', 'Implement', 1); // Design must come before Implement
graph.addEdge('Implement', 'Test', 1); // Implement must come before Test
graph.addEdge('Test', 'Deploy', 1); // Test must come before Deploy
// Topological sort gives valid execution order
const executionOrder = graph.topologicalSort();
console.log(executionOrder); // defined;
console.log(executionOrder); // ['Design', 'Implement', 'Test', 'Deploy'];
// All vertices should be included
console.log(executionOrder?.length); // 4;
toVisual()
toVisual(options?): string;
Defined in: data-structures/graph/abstract-graph.ts:1108
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.
Inherited from
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
fromEntries()
static fromEntries<V>(entries): DirectedGraph<V, undefined, DirectedVertex<V>, DirectedEdge<undefined>>;
Defined in: data-structures/graph/directed-graph.ts:182
Construct a directed graph from [key, value] entries.
Type Parameters
V
V
Vertex value type.
Parameters
entries
Iterable<[VertexKey, V]>
Iterable of [key, value] pairs.
Returns
DirectedGraph<V, undefined, DirectedVertex<V>, DirectedEdge<undefined>>
DirectedGraph with all vertices added.
Remarks
Time O(V), Space O(V)
fromKeys()
static fromKeys<K>(keys): DirectedGraph<K, undefined, DirectedVertex<K>, DirectedEdge<undefined>>;
Defined in: data-structures/graph/directed-graph.ts:167
Construct a directed graph from keys with value initializer v => v.
Type Parameters
K
K extends VertexKey
Vertex key type.
Parameters
keys
Iterable<K>
Iterable of vertex keys.
Returns
DirectedGraph<K, undefined, DirectedVertex<K>, DirectedEdge<undefined>>
DirectedGraph with all keys added.
Remarks
Time O(V), Space O(V)
Protected Members
_edgeConnector
Get Signature
get protected _edgeConnector(): string;
Defined in: data-structures/graph/directed-graph.ts:136
The edge connector string used in visual output. Override in subclasses (e.g., '--' for undirected, '->' for directed).
Returns
string
Overrides
_addEdge()
protected _addEdge(edge): boolean;
Defined in: data-structures/graph/directed-graph.ts:1094
Internal hook to attach a directed edge into adjacency maps.
Parameters
edge
EO
Edge instance.
Returns
boolean
true if inserted; otherwise false.
Remarks
Time O(1) avg, Space O(1)
Overrides
_addVertex()
protected _addVertex(newVertex): boolean;
Defined in: data-structures/graph/abstract-graph.ts:1054
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)
Inherited from
_createInstance()
protected _createInstance(_options?): this;
Defined in: data-structures/graph/abstract-graph.ts:987
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)
Inherited from
_createLike()
protected _createLike(iter?, options?): this;
Defined in: data-structures/graph/abstract-graph.ts:1009
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)
Inherited from
_getIterator()
protected _getIterator(): IterableIterator<[VertexKey, V | undefined]>;
Defined in: data-structures/graph/abstract-graph.ts:958
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)
Inherited from
_getVertex()
protected _getVertex(vertexOrKey): VO | undefined;
Defined in: data-structures/graph/abstract-graph.ts:1068
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)
Inherited from
_getVertexKey()
protected _getVertexKey(vertexOrKey): VertexKey;
Defined in: data-structures/graph/abstract-graph.ts:1079
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)
Inherited from
_snapshotOptions()
protected _snapshotOptions(): Record<string, unknown>;
Defined in: data-structures/graph/abstract-graph.ts:973
Capture configuration needed to reproduce the current graph.
Returns
Record<string, unknown>
Options bag (opaque to callers).
Remarks
Time O(1), Space O(1)
Inherited from
AbstractGraph._snapshotOptions