Class DirectedGraph<V, E, VO, EO>

Directed graph implementation.

Remarks

Time O(1), Space O(1)

Example

examples will be generated by unit test

Type Parameters

V = any
Vertex value type.
E = any
Edge value type.
VO extends DirectedVertex<V> = DirectedVertex<V>
Concrete vertex class (extends AbstractVertex).
EO extends DirectedEdge<E> = DirectedEdge<E>
Concrete edge class (extends AbstractEdge).

Hierarchy (view full)

AbstractGraph<V, E, VO, EO>
- DirectedGraph
  - MapGraph

Implements

IGraph<V, E, VO, EO>

Constructors

constructor

new DirectedGraph<V, E, VO, EO>(options?): DirectedGraph<V, E, VO, EO>
Construct a directed graph with runtime defaults.
Type Parameters
- V = any
- E = any
- VO extends DirectedVertex<V> = DirectedVertex<V>
- EO extends DirectedEdge<E> = DirectedEdge<E>
Parameters
- Optionaloptions: Partial<GraphOptions<V>>
  GraphOptions<V> (e.g. vertexValueInitializer, defaultEdgeWeight).
Returns DirectedGraph<V, E, VO, EO>
Remarks
Time O(1), Space O(1)
Overrides AbstractGraph.constructor
- Defined in data-structures/graph/directed-graph.ts:54

Accessors

size

get size(): number
Total number of entries.

Returns number
Entry count.

Remarks
Time O(1), Space O(1)
Inherited from AbstractGraph.size
- Defined in data-structures/graph/abstract-graph.ts:88

Methods

`Protected`_addEdge

_addEdge(edge): boolean
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 AbstractGraph._addEdge
- Defined in data-structures/graph/directed-graph.ts:563

`Protected`_addVertex

_addVertex(newVertex): boolean
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 AbstractGraph._addVertex
- Defined in data-structures/graph/abstract-graph.ts:1053

`Protected`_createInstance

_createInstance(_options?): this
Create an empty graph instance of the same concrete species.
Parameters
- Optional_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 AbstractGraph._createInstance
- Defined in data-structures/graph/abstract-graph.ts:986

`Protected`_createLike

_createLike(iter?, options?): this
Create a same-species graph populated with entries; preserves edges among kept vertices.
Parameters
- Optionaliter: Iterable<[VertexKey, undefined | V], any, any>
  Optional entries to seed the new graph.
- Optionaloptions: 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 AbstractGraph._createLike
- Defined in data-structures/graph/abstract-graph.ts:1007

`Protected`_getIterator

_getIterator(): IterableIterator<[VertexKey, undefined | V], any, any>
Internal iterator over [key, value] entries in insertion order.

Returns IterableIterator<[VertexKey, undefined | V], any, any>
Iterator of [VertexKey, V | undefined].

Remarks
Time O(V), Space O(1)
Inherited from AbstractGraph._getIterator
- Defined in data-structures/graph/abstract-graph.ts:957

`Protected`_getVertex

_getVertex(vertexOrKey): undefined | VO
Resolve a vertex key or instance to the concrete vertex instance.
Parameters
- vertexOrKey: VertexKey | VO
  Vertex key or existing vertex.
Returns undefined | VO
Vertex instance or undefined.

Remarks
Time O(1), Space O(1)
Inherited from AbstractGraph._getVertex
- Defined in data-structures/graph/abstract-graph.ts:1067

`Protected`_getVertexKey

_getVertexKey(vertexOrKey): VertexKey
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 AbstractGraph._getVertexKey
- Defined in data-structures/graph/abstract-graph.ts:1078

`Protected`_snapshotOptions

_snapshotOptions(): Record<string, unknown>
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
- Defined in data-structures/graph/abstract-graph.ts:972

[iterator]

[iterator](...args): IterableIterator<[VertexKey, undefined | V], any, any>
Default iterator yielding [key, value] entries.
Parameters
- Rest...args: any[]
Returns IterableIterator<[VertexKey, undefined | V], any, any>
Iterator of [K, V].

Remarks
Time O(n) to iterate, Space O(1)
Inherited from AbstractGraph.[iterator]
- Defined in data-structures/base/iterable-entry-base.ts:22

addEdge

addEdge(edge): boolean
Parameters
- edge: EO
Returns boolean
Inherited from AbstractGraph.addEdge
- Defined in data-structures/graph/abstract-graph.ts:253
addEdge(src, dest, weight?, value?): boolean
Parameters
- src: VertexKey | VO
- dest: VertexKey | VO
- Optionalweight: number
- Optionalvalue: E
Returns boolean
Inherited from AbstractGraph.addEdge
- Defined in data-structures/graph/abstract-graph.ts:255

addVertex

addVertex(vertex): boolean
Parameters
- vertex: VO
Returns boolean
Implementation of IGraph.addVertex
Inherited from AbstractGraph.addVertex
- Defined in data-structures/graph/abstract-graph.ts:188
addVertex(key, value?): boolean
Parameters
- key: VertexKey
- Optionalvalue: V
Returns boolean
Implementation of IGraph.addVertex
Inherited from AbstractGraph.addVertex
- Defined in data-structures/graph/abstract-graph.ts:190

bellmanFord

bellmanFord(src, scanNegativeCycle?, getMin?, genPath?): {
    distMap: Map<VO, number>;
    hasNegativeCycle: undefined | boolean;
    min: number;
    minPath: VO[];
    paths: VO[][];
    preMap: Map<VO, VO>;
}
Bellman-Ford single-source shortest paths with option to scan negative cycles.
Parameters
- src: VertexKey | VO
  Source vertex or key.
- OptionalscanNegativeCycle: boolean
  If true, also detect negative cycles.
- OptionalgetMin: boolean
  If true, compute global minimum distance.
- OptionalgenPath: boolean
  If true, generate path arrays via predecessor map.
Returns {
    distMap: Map<VO, number>;
    hasNegativeCycle: undefined | boolean;
    min: number;
    minPath: VO[];
    paths: VO[][];
    preMap: Map<VO, VO>;
}
Result bag including distances, predecessors, and optional cycle flag.
- distMap: Map<VO, number>
- hasNegativeCycle: undefined | boolean
- min: number
- minPath: VO[]
- paths: VO[][]
- preMap: Map<VO, VO>
Remarks
Time O(V * E), Space O(V + E)
Inherited from AbstractGraph.bellmanFord
- Defined in data-structures/graph/abstract-graph.ts:704

clear

clear(): void
Remove all vertices and edges.

Returns void
Remarks
Time O(V + E), Space O(1)
Implementation of IGraph.clear
Overrides AbstractGraph.clear
- Defined in data-structures/graph/directed-graph.ts:459

clone

clone(): this
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 AbstractGraph.clone
- Defined in data-structures/graph/directed-graph.ts:470

createEdge

createEdge(src, dest, weight?, value?): EO
Create a directed edge instance. Does not insert into the graph.
Parameters
- src: VertexKey
  Source vertex key.
- dest: VertexKey
  Destination vertex key.
- Optionalweight: number
  Edge weight; defaults to defaultEdgeWeight.
- Optionalvalue: E
  Edge payload.
Returns EO
Concrete edge instance.

Remarks
Time O(1), Space O(1)
Implementation of IGraph.createEdge
Overrides AbstractGraph.createEdge
- Defined in data-structures/graph/directed-graph.ts:128

createVertex

createVertex(key, value?): VO
Create a directed vertex instance. Does not insert into the graph.
Parameters
- key: VertexKey
  Vertex identifier.
- Optionalvalue: VO["value"]
  Optional payload.
Returns VO
Concrete vertex instance.

Remarks
Time O(1), Space O(1)
Implementation of IGraph.createVertex
Overrides AbstractGraph.createVertex
- Defined in data-structures/graph/directed-graph.ts:115

degreeOf

degreeOf(vertexOrKey): number
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 AbstractGraph.degreeOf
- Defined in data-structures/graph/directed-graph.ts:298

deleteEdge

deleteEdge(edgeOrSrcVertexKey, destVertexKey?): undefined | EO
Delete an edge by instance or by (srcKey, destKey).
Parameters
- edgeOrSrcVertexKey: VertexKey | EO
  Edge instance or source vertex/key.
- OptionaldestVertexKey: VertexKey
  Optional destination vertex/key when deleting by pair.
Returns undefined | EO
Removed edge or undefined.

Remarks
Time O(1) avg, Space O(1)
Implementation of IGraph.deleteEdge
Overrides AbstractGraph.deleteEdge
- Defined in data-structures/graph/directed-graph.ts:191

deleteEdgeSrcToDest

deleteEdgeSrcToDest(srcOrKey, destOrKey): undefined | EO
Delete edge src -> dest if present.
Parameters
- srcOrKey: VertexKey | VO
  Source vertex or key.
- destOrKey: VertexKey | VO
  Destination vertex or key.
Returns undefined | EO
Removed edge or undefined.

Remarks
Time O(1) avg, Space O(1)
- Defined in data-structures/graph/directed-graph.ts:164

deleteVertex

deleteVertex(vertexOrKey): boolean
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
Overrides AbstractGraph.deleteVertex
- Defined in data-structures/graph/directed-graph.ts:221

dijkstraWithoutHeap

dijkstraWithoutHeap(src, dest?, getMinDist?, genPaths?): DijkstraResult<VO>
Dijkstra without heap (array-based selection).
Parameters
- src: VertexKey | VO
  Source vertex or key.
- dest: undefined | 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
- Defined in data-structures/graph/abstract-graph.ts:483

edgeSet

edgeSet(): EO[]
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
Overrides AbstractGraph.edgeSet
- Defined in data-structures/graph/directed-graph.ts:404

edgesOf

edgesOf(vertexOrKey): EO[]
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 AbstractGraph.edgesOf
- Defined in data-structures/graph/directed-graph.ts:328

entries

entries(): IterableIterator<[VertexKey, undefined | V], any, any>
Iterate over [key, value] pairs (may yield undefined values).

Returns IterableIterator<[VertexKey, undefined | V], any, any>
Iterator of [K, V | undefined].

Remarks
Time O(n), Space O(1)
Inherited from AbstractGraph.entries
- Defined in data-structures/base/iterable-entry-base.ts:31

every

every(predicate, thisArg?): boolean
Test whether all entries satisfy the predicate.
Parameters
- predicate: EntryCallback<VertexKey, undefined | V, boolean>
  (key, value, index, self) => boolean.
- OptionalthisArg: any
  Optional this for callback.
Returns boolean
true if all pass; otherwise false.

Remarks
Time O(n), Space O(1)
Inherited from AbstractGraph.every
- Defined in data-structures/base/iterable-entry-base.ts:66

filter

filter(predicate, thisArg?): this
Induced-subgraph filter: keep vertices where predicate(key, value) is true, and only keep edges whose endpoints both survive.
Parameters
- predicate: EntryCallback<VertexKey, undefined | V, boolean>
  (key, value, index, self) => boolean.
- OptionalthisArg: any
  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 AbstractGraph.filter
- Defined in data-structures/graph/abstract-graph.ts:896

filterEntries

filterEntries(predicate, thisArg?): [VertexKey, undefined | V][]
Preserve the old behavior: return filtered entries as an array.
Parameters
- predicate: EntryCallback<VertexKey, undefined | V, boolean>
- OptionalthisArg: any
Returns [VertexKey, undefined | V][]
Remarks
Time O(V), Space O(V)
Inherited from AbstractGraph.filterEntries
- Defined in data-structures/graph/abstract-graph.ts:912

find

find(callbackfn, thisArg?): undefined | [VertexKey, undefined | V]
Find the first entry that matches a predicate.
Parameters
- callbackfn: EntryCallback<VertexKey, undefined | V, boolean>
  (key, value, index, self) => boolean.
- OptionalthisArg: any
  Optional this for callback.
Returns undefined | [VertexKey, undefined | V]
Matching [key, value] or undefined.

Remarks
Time O(n), Space O(1)
Inherited from AbstractGraph.find
- Defined in data-structures/base/iterable-entry-base.ts:114

floydWarshall

floydWarshall(): {
costs: number[][];
predecessor: (undefined | VO)[][];
}
Floyd–Warshall all-pairs shortest paths.

Returns {
costs: number[][];
predecessor: (undefined | VO)[][];
}
{ costs, predecessor } matrices.
- costs: number[][]
- predecessor: (undefined | VO)[][]
Remarks
Time O(V^3), Space O(V^2)
Inherited from AbstractGraph.floydWarshall
- Defined in data-structures/graph/abstract-graph.ts:797

forEach

forEach(callbackfn, thisArg?): void
Visit each entry, left-to-right.
Parameters
- callbackfn: EntryCallback<VertexKey, undefined | V, void>
  (key, value, index, self) => void.
- OptionalthisArg: any
  Optional this for callback.
Returns void
Remarks
Time O(n), Space O(1)
Inherited from AbstractGraph.forEach
- Defined in data-structures/base/iterable-entry-base.ts:99

get

get(key): undefined | V
Get the value under a key.
Parameters
- key: VertexKey
  Key to look up.
Returns undefined | V
Value or undefined.

Remarks
Time O(n) generic, Space O(1)
Inherited from AbstractGraph.get
- Defined in data-structures/base/iterable-entry-base.ts:156

getAllPathsBetween

getAllPathsBetween(v1, v2, limit?): VO[][]
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
- Defined in data-structures/graph/abstract-graph.ts:308

getCycles

getCycles(isInclude2Cycle?): VertexKey[][]
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 AbstractGraph.getCycles
- Defined in data-structures/graph/abstract-graph.ts:837

getDestinations

getDestinations(vertex): VO[]
Direct children reachable by one outgoing edge.
Parameters
- vertex: undefined | VertexKey | VO
  Vertex or key.
Returns VO[]
Array of neighbor vertices.

Remarks
Time O(deg_out), Space O(deg_out)
- Defined in data-structures/graph/directed-graph.ts:346

getDFNMap

getDFNMap(): Map<VO, number>
DFN index map computed by tarjan().

Returns Map<VO, number>
Map from vertex to DFN index.

Remarks
Time O(V), Space O(V)
- Defined in data-structures/graph/directed-graph.ts:535

getEdge

getEdge(srcOrKey, destOrKey): undefined | EO
Get the unique edge from src to dest, if present.
Parameters
- srcOrKey: undefined | VertexKey | VO
  Source vertex or key.
- destOrKey: undefined | VertexKey | VO
  Destination vertex or key.
Returns undefined | EO
Edge instance or undefined.

Remarks
Time O(1) avg, Space O(1)
Implementation of IGraph.getEdge
Overrides AbstractGraph.getEdge
- Defined in data-structures/graph/directed-graph.ts:139

getEndsOfEdge

getEndsOfEdge(edge): undefined | [VO, VO]
Resolve an edge's [src, dest] endpoints to vertex instances.
Parameters
- edge: EO
  Edge instance.
Returns undefined | [VO, VO]
[src, dest] or undefined if either endpoint is missing.

Remarks
Time O(1), Space O(1)
Implementation of IGraph.getEndsOfEdge
Overrides AbstractGraph.getEndsOfEdge
- Defined in data-structures/graph/directed-graph.ts:434

getLowMap

getLowMap(): Map<VO, number>
LOW link map computed by tarjan().

Returns Map<VO, number>
Map from vertex to LOW value.

Remarks
Time O(V), Space O(V)
- Defined in data-structures/graph/directed-graph.ts:544

getMinCostBetween

getMinCostBetween(v1, v2, isWeight?): undefined | number
Minimum hops/weight between two vertices.
Parameters
- v1: VertexKey | VO
  Source vertex or key.
- v2: VertexKey | VO
  Destination vertex or key.
- OptionalisWeight: boolean
  If true, compare by path weight; otherwise by hop count.
Returns undefined | number
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
- Defined in data-structures/graph/abstract-graph.ts:361

getMinPathBetween

getMinPathBetween(v1, v2, isWeight?, isDFS?): undefined | VO[]
Minimum path (as vertex sequence) between two vertices.
Parameters
- v1: VertexKey | VO
  Source vertex or key.
- v2: VertexKey | VO
  Destination vertex or key.
- OptionalisWeight: 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 undefined | VO[]
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
- Defined in data-structures/graph/abstract-graph.ts:414

getNeighbors

getNeighbors(vertexOrKey): VO[]
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
Overrides AbstractGraph.getNeighbors
- Defined in data-structures/graph/directed-graph.ts:412

getPathSumWeight

getPathSumWeight(path): number
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
- Defined in data-structures/graph/abstract-graph.ts:345

getSCCs

getSCCs(): Map<number, VO[]>
Strongly connected components computed by tarjan().

Returns Map<number, VO[]>
Map from SCC id to vertices.

Remarks
Time O(#SCC + V), Space O(V)
- Defined in data-structures/graph/directed-graph.ts:553

getVertex

getVertex(vertexKey): undefined | VO
Get vertex instance by key.
Parameters
- vertexKey: VertexKey
  Vertex key.
Returns undefined | VO
Vertex instance or undefined.

Remarks
Time O(1), Space O(1)
Implementation of IGraph.getVertex
Inherited from AbstractGraph.getVertex
- Defined in data-structures/graph/abstract-graph.ts:174

has

has(key): boolean
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 AbstractGraph.has
- Defined in data-structures/base/iterable-entry-base.ts:129

hasEdge

hasEdge(v1, v2): boolean
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 AbstractGraph.hasEdge
- Defined in data-structures/graph/abstract-graph.ts:248

hasValue

hasValue(value): boolean
Whether there exists an entry with the given value.
Parameters
- value: undefined | V
  Value to test.
Returns boolean
true if found; otherwise false.

Remarks
Time O(n), Space O(1)
Inherited from AbstractGraph.hasValue
- Defined in data-structures/base/iterable-entry-base.ts:143

hasVertex

hasVertex(vertexOrKey): boolean
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 AbstractGraph.hasVertex
- Defined in data-structures/graph/abstract-graph.ts:184

incomingEdgesOf

incomingEdgesOf(vertexOrKey): EO[]
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)
- Defined in data-structures/graph/directed-graph.ts:270

isEmpty

isEmpty(): boolean
Whether the graph has no vertices and no edges.

Returns boolean
Remarks
Time O(1), Space O(1)
Implementation of IGraph.isEmpty
Overrides AbstractGraph.isEmpty
- Defined in data-structures/graph/directed-graph.ts:451

isVertexKey

isVertexKey(potentialKey): potentialKey is VertexKey
Type guard: check if a value is a valid vertex key.
Parameters
- potentialKey: any
  Value to test.
Returns potentialKey is VertexKey
true if string/number; else false.

Remarks
Time O(1), Space O(1)
Inherited from AbstractGraph.isVertexKey
- Defined in data-structures/graph/abstract-graph.ts:214

keys

keys(): IterableIterator<VertexKey, any, any>
Iterate over keys only.

Returns IterableIterator<VertexKey, any, any>
Iterator of keys.

Remarks
Time O(n), Space O(1)
Inherited from AbstractGraph.keys
- Defined in data-structures/base/iterable-entry-base.ts:42

map

map<T>(callback, thisArg?): T[]
Map entries using an implementation-specific strategy.
Type Parameters
- T
Parameters
- callback: EntryCallback<VertexKey, undefined | V, T>
- OptionalthisArg: any
Returns T[]
Remarks
Time O(n), Space O(n)
Inherited from AbstractGraph.map
- Defined in data-structures/graph/abstract-graph.ts:927

outgoingEdgesOf

outgoingEdgesOf(vertexOrKey): EO[]
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)
- Defined in data-structures/graph/directed-graph.ts:284

print

print(): void
Print a human-friendly representation to the console.

Returns void
Remarks
Time O(n), Space O(n)
Inherited from AbstractGraph.print
- Defined in data-structures/base/iterable-entry-base.ts:194

reduce

reduce<U>(callbackfn, initialValue): U
Reduce entries into a single accumulator.
Type Parameters
- U
Parameters
- callbackfn: ReduceEntryCallback<VertexKey, undefined | V, U>
  (acc, value, key, index, self) => acc.
- initialValue: U
  Initial accumulator.
Returns U
Final accumulator.

Remarks
Time O(n), Space O(1)
Inherited from AbstractGraph.reduce
- Defined in data-structures/base/iterable-entry-base.ts:171

removeManyVertices

removeManyVertices(vertexMap): boolean
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
- Defined in data-structures/graph/abstract-graph.ts:233

setEdgeWeight

setEdgeWeight(srcOrKey, destOrKey, weight): boolean
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 AbstractGraph.setEdgeWeight
- Defined in data-structures/graph/abstract-graph.ts:290

some

some(predicate, thisArg?): boolean
Test whether any entry satisfies the predicate.
Parameters
- predicate: EntryCallback<VertexKey, undefined | V, boolean>
  (key, value, index, self) => boolean.
- OptionalthisArg: any
  Optional this for callback.
Returns boolean
true if any passes; otherwise false.

Remarks
Time O(n), Space O(1)
Inherited from AbstractGraph.some
- Defined in data-structures/base/iterable-entry-base.ts:83

tarjan

tarjan(): {
    dfnMap: Map<VO, number>;
    lowMap: Map<VO, number>;
    SCCs: Map<number, VO[]>;
}
Tarjan's algorithm for strongly connected components.

Returns {
    dfnMap: Map<VO, number>;
    lowMap: Map<VO, number>;
    SCCs: Map<number, VO[]>;
}
{ dfnMap, lowMap, SCCs }.
- dfnMap: Map<VO, number>
- lowMap: Map<VO, number>
- SCCs: Map<number, VO[]>
Remarks
Time O(V + E), Space O(V + E)
- Defined in data-structures/graph/directed-graph.ts:479

topologicalSort

topologicalSort(propertyName?): undefined | (VertexKey | VO)[]
Topological sort if DAG; returns undefined if a cycle exists.
Parameters
- OptionalpropertyName: "key" | "vertex"
  'key' to map to keys; 'vertex' to keep instances.
Returns undefined | (VertexKey | VO)[]
Array of keys/vertices, or undefined when cycle is found.

Remarks
Time O(V + E), Space O(V)
- Defined in data-structures/graph/directed-graph.ts:367

toVisual

toVisual(): string | [VertexKey, undefined | V][]
Visualize the iterable as an array of [key, value] pairs (or a custom string).

Returns string | [VertexKey, undefined | V][]
Array of entries (default) or a string.

Remarks
Time O(n), Space O(n)
Inherited from AbstractGraph.toVisual
- Defined in data-structures/base/iterable-entry-base.ts:186

values

values(): IterableIterator<undefined | V, any, any>
Iterate over values only.

Returns IterableIterator<undefined | V, any, any>
Iterator of values.

Remarks
Time O(n), Space O(1)
Inherited from AbstractGraph.values
- Defined in data-structures/base/iterable-entry-base.ts:53

`Static`fromEntries

fromEntries<V>(entries): DirectedGraph<V, any, DirectedVertex<V>, DirectedEdge<any>>
Construct a directed graph from [key, value] entries.
Type Parameters
- V
  Vertex value type.
Parameters
- entries: Iterable<[VertexKey, V], any, any>
  Iterable of [key, value] pairs.
Returns DirectedGraph<V, any, DirectedVertex<V>, DirectedEdge<any>>
DirectedGraph with all vertices added.

Remarks
Time O(V), Space O(V)
- Defined in data-structures/graph/directed-graph.ts:100

`Static`fromKeys

fromKeys<K>(keys): DirectedGraph<K, any, DirectedVertex<K>, DirectedEdge<any>>
Construct a directed graph from keys with value initializer v => v.
Type Parameters
- K extends VertexKey
  Vertex key type.
Parameters
- keys: Iterable<K, any, any>
  Iterable of vertex keys.
Returns DirectedGraph<K, any, DirectedVertex<K>, DirectedEdge<any>>
DirectedGraph with all keys added.

Remarks
Time O(V), Space O(V)
- Defined in data-structures/graph/directed-graph.ts:85

Class DirectedGraph<V, E, VO, EO>

Remarks

Example

Type Parameters

Hierarchy (view full)

Implements

Index

Constructors

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns DirectedGraph<V, E, VO, EO>

Remarks

Accessors

size

Returns number

Remarks

Methods

Protected_addEdge

Parameters

Returns boolean

Remarks

Protected_addVertex

Parameters

Returns boolean

Remarks

Protected_createInstance

Parameters

Returns this

Remarks

Protected_createLike

Parameters

Returns this

Remarks

Protected_getIterator

Returns IterableIterator<[VertexKey, undefined | V], any, any>

Remarks

Protected_getVertex

Parameters

Returns undefined | VO

Remarks

Protected_getVertexKey

Parameters

Returns VertexKey

Remarks

Protected_snapshotOptions

Returns Record<string, unknown>

Remarks

[iterator]

Parameters

Returns IterableIterator<[VertexKey, undefined | V], any, any>

Remarks

addEdge

Parameters

Returns boolean

Parameters

Returns boolean

addVertex

Parameters

Returns boolean

Parameters

Returns boolean

bellmanFord

Parameters

Returns { distMap: Map<VO, number>; hasNegativeCycle: undefined | boolean; min: number; minPath: VO[]; paths: VO[][]; preMap: Map<VO, VO>; }

distMap: Map<VO, number>

hasNegativeCycle: undefined | boolean

min: number

minPath: VO[]

paths: VO[][]

preMap: Map<VO, VO>

Remarks

clear

Returns void

Remarks

clone

Returns this

`Protected`_addEdge

`Protected`_addVertex

`Protected`_createInstance

`Protected`_createLike

`Protected`_getIterator

`Protected`_getVertex

`Protected`_getVertexKey

`Protected`_snapshotOptions

Returns {
distMap: Map<VO, number>;
hasNegativeCycle: undefined | boolean;
min: number;
minPath: VO[];
paths: VO[][];
preMap: Map<VO, VO>;
}

Returns {
costs: number[][];
predecessor: (undefined | VO)[][];
}