MapGraph

Class: MapGraph<V, E, VO, EO>

Defined in: data-structures/graph/map-graph.ts:95

Directed graph variant carrying geospatial coordinates.

Remarks

Time O(1), Space O(1)

Examples

// City navigation with shortest path
 const map = new MapGraph([0, 0], [10, 10]);

    map.addVertex(new MapVertex('Home', '', 0, 0));
    map.addVertex(new MapVertex('Office', '', 3, 4));
    map.addVertex(new MapVertex('Cafe', '', 1, 2));
    map.addVertex(new MapVertex('Park', '', 2, 1));

    map.addEdge('Home', 'Cafe', 2.2);
    map.addEdge('Cafe', 'Office', 3.5);
    map.addEdge('Home', 'Park', 2.0);
    map.addEdge('Park', 'Office', 4.0);
    map.addEdge('Home', 'Office', 7.0);

    // Find shortest path
    const result = map.dijkstra('Home', 'Office', true, true);
    console.log(result?.minDist); // 5.7; // Home → Cafe → Office
    console.log(result?.minPath.map(v => v.key)); // ['Home', 'Cafe', 'Office'];

// Delivery route optimization
 const routes = new MapGraph([0, 0], [10, 10]);

    routes.addVertex(new MapVertex('Warehouse', '', 0, 0));
    routes.addVertex(new MapVertex('Customer A', '', 2, 3));
    routes.addVertex(new MapVertex('Customer B', '', 5, 1));
    routes.addVertex(new MapVertex('Customer C', '', 3, 5));

    routes.addEdge('Warehouse', 'Customer A', 3.6);
    routes.addEdge('Warehouse', 'Customer B', 5.1);
    routes.addEdge('Customer A', 'Customer C', 2.2);
    routes.addEdge('Customer A', 'Customer B', 3.6);
    routes.addEdge('Customer B', 'Customer C', 4.5);

    // Check outgoing neighbors of Customer A
    const neighbors = routes.getNeighbors('Customer A');
    console.log(neighbors.map(n => n.key).sort()); // ['Customer B', 'Customer C'];

    // Shortest path from Warehouse to Customer C
    const path = routes.getMinPathBetween('Warehouse', 'Customer C', true);
    console.log(path?.map(v => v.key)); // ['Warehouse', 'Customer A', 'Customer C'];

// Campus map with building connections
 const campus = new MapGraph([0, 0], [5, 5]);

    campus.addVertex(new MapVertex('Library', '', 0, 0));
    campus.addVertex(new MapVertex('Lab', '', 1, 1));
    campus.addVertex(new MapVertex('Cafeteria', '', 2, 0));

    campus.addEdge('Library', 'Lab', 5);
    campus.addEdge('Lab', 'Cafeteria', 3);
    campus.addEdge('Library', 'Cafeteria', 10);

    console.log(campus.hasVertex('Library')); // true;
    console.log(campus.hasVertex('Gym')); // false;

    // Direct distance vs shortest path
    const direct = campus.dijkstra('Library', 'Cafeteria', true, true);
    console.log(direct?.minDist); // 8;

Extends

DirectedGraph<V, E, VO, EO>

Type Parameters

V

V = any

Vertex value type.

E

E = any

Edge value type.

VO

VO extends MapVertex<V> = MapVertex<V>

Concrete vertex class (MapVertex).

EO

EO extends MapEdge<E> = MapEdge<E>

Concrete edge class (MapEdge).

Constructors

Constructor

new MapGraph<V, E, VO, EO>(originCoord, bottomRight?): MapGraph<V, E, VO, EO>;

Defined in: data-structures/graph/map-graph.ts:107

Construct a MapGraph.

Parameters

originCoord

MapGraphCoordinate

Origin coordinate [lat, long] used as default.

bottomRight?

MapGraphCoordinate

Optional bottom-right coordinate for bounding boxes.

Returns

MapGraph<V, E, VO, EO>

Remarks

Time O(1), Space O(1)

Overrides

DirectedGraph.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.

Inherited from

DirectedGraph.size

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

DirectedGraph.[iterator]

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

Inherited from

DirectedGraph.addEdge

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

Inherited from

DirectedGraph.addEdge

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

Inherited from

DirectedGraph.addVertex

Call Signature

addVertex(key, value?): boolean;

Defined in: data-structures/graph/abstract-graph.ts:195

Parameters

key

VertexKey

value?

V

Returns

boolean

Inherited from

DirectedGraph.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)

Inherited from

DirectedGraph.bellmanFord

clear()

clear(): void;

Defined in: data-structures/graph/directed-graph.ts:634

Remove all vertices and edges.

Returns

void

Remarks

Time O(V + E), Space O(1)

Inherited from

DirectedGraph.clear

clone()

clone(): this;

Defined in: data-structures/graph/map-graph.ts:159

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)

Overrides

DirectedGraph.clone

createEdge()

createEdge(
   src, 
   dest, 
   weight?, 
   value?): EO;

Defined in: data-structures/graph/map-graph.ts:150

Create a map edge (directed) with optional weight/value.

Parameters

src

VertexKey

Source key.

dest

VertexKey

Destination key.

weight?

number

Edge weight.

value?

E

Edge payload.

Returns

EO

MapEdge instance.

Remarks

Time O(1), Space O(1)

Overrides

DirectedGraph.createEdge

createVertex()

createVertex(
   key, 
   value?, 
   lat?, 
   long?): VO;

Defined in: data-structures/graph/map-graph.ts:132

Create a map vertex with optional coordinates.

Parameters

key

VertexKey

Vertex identifier.

value?

V

Optional payload.

lat?

number = ...

Latitude (defaults to originCoord[0]).

long?

number = ...

Longitude (defaults to originCoord[1]).

Returns

VO

MapVertex instance.

Remarks

Time O(1), Space O(1)

Overrides

DirectedGraph.createVertex

degreeOf()

degreeOf(vertexOrKey): number;

Defined in: data-structures/graph/directed-graph.ts:434

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)

Inherited from

DirectedGraph.degreeOf

deleteEdge()

deleteEdge(edgeOrSrcVertexKey, destVertexKey?): EO | undefined;

Defined in: data-structures/graph/directed-graph.ts:305

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;

Inherited from

DirectedGraph.deleteEdge

deleteEdgeSrcToDest()

deleteEdgeSrcToDest(srcOrKey, destOrKey): EO | undefined;

Defined in: data-structures/graph/directed-graph.ts:255

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)

Inherited from

DirectedGraph.deleteEdgeSrcToDest

deleteVertex()

deleteVertex(vertexOrKey): boolean;

Defined in: data-structures/graph/directed-graph.ts:344

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;

Inherited from

DirectedGraph.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)

Inherited from

DirectedGraph.dijkstraWithoutHeap

edgeSet()

edgeSet(): EO[];

Defined in: data-structures/graph/directed-graph.ts:567

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;

Inherited from

DirectedGraph.edgeSet

edgesOf()

edgesOf(vertexOrKey): EO[];

Defined in: data-structures/graph/directed-graph.ts:464

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)

Inherited from

DirectedGraph.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

DirectedGraph.entries

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

DirectedGraph.every

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)

Inherited from

DirectedGraph.filter

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)

Inherited from

DirectedGraph.filterEntries

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

DirectedGraph.find

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)

Inherited from

DirectedGraph.floydWarshall

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

DirectedGraph.forEach

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

DirectedGraph.get

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)

Inherited from

DirectedGraph.getAllPathsBetween

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)

Inherited from

DirectedGraph.getCycles

getDestinations()

getDestinations(vertex): VO[];

Defined in: data-structures/graph/directed-graph.ts:482

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)

Inherited from

DirectedGraph.getDestinations

getDFNMap()

getDFNMap(): Map<VO, number>;

Defined in: data-structures/graph/directed-graph.ts:713

DFN index map computed by tarjan().

Returns

Map<VO, number>

Map from vertex to DFN index.

Remarks

Time O(V), Space O(V)

Inherited from

DirectedGraph.getDFNMap

getEdge()

getEdge(srcOrKey, destOrKey): EO | undefined;

Defined in: data-structures/graph/directed-graph.ts:233

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;

Inherited from

DirectedGraph.getEdge

getEndsOfEdge()

getEndsOfEdge(edge): [VO, VO] | undefined;

Defined in: data-structures/graph/directed-graph.ts:609

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)

Inherited from

DirectedGraph.getEndsOfEdge

getLowMap()

getLowMap(): Map<VO, number>;

Defined in: data-structures/graph/directed-graph.ts:722

LOW link map computed by tarjan().

Returns

Map<VO, number>

Map from vertex to LOW value.

Remarks

Time O(V), Space O(V)

Inherited from

DirectedGraph.getLowMap

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)

Inherited from

DirectedGraph.getMinCostBetween

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)

Inherited from

DirectedGraph.getMinPathBetween

getNeighbors()

getNeighbors(vertexOrKey): VO[];

Defined in: data-structures/graph/directed-graph.ts:588

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'];

Inherited from

DirectedGraph.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

Inherited from

DirectedGraph.getPathSumWeight

getSCCs()

getSCCs(): Map<number, VO[]>;

Defined in: data-structures/graph/directed-graph.ts:742

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;

Inherited from

DirectedGraph.getSCCs

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)

Inherited from

DirectedGraph.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

DirectedGraph.has

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)

Inherited from

DirectedGraph.hasEdge

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

DirectedGraph.hasValue

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)

Inherited from

DirectedGraph.hasVertex

incomingEdgesOf()

incomingEdgesOf(vertexOrKey): EO[];

Defined in: data-structures/graph/directed-graph.ts:397

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;

Inherited from

DirectedGraph.incomingEdgesOf

isEmpty()

isEmpty(): boolean;

Defined in: data-structures/graph/directed-graph.ts:626

Whether the graph has no vertices and no edges.

Returns

boolean

Remarks

Time O(1), Space O(1)

Inherited from

DirectedGraph.isEmpty

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)

Inherited from

DirectedGraph.isVertexKey

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

DirectedGraph.keys

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)

Inherited from

DirectedGraph.map

outgoingEdgesOf()

outgoingEdgesOf(vertexOrKey): EO[];

Defined in: data-structures/graph/directed-graph.ts:420

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;

Inherited from

DirectedGraph.outgoingEdgesOf

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

Inherited from

DirectedGraph.print

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

DirectedGraph.reduce

removeManyVertices()

removeManyVertices(vertexMap): boolean;

Defined in: data-structures/graph/abstract-graph.ts:238

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

DirectedGraph.removeManyVertices

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)

Inherited from

DirectedGraph.setEdgeWeight

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

DirectedGraph.some

tarjan()

tarjan(): object;

Defined in: data-structures/graph/directed-graph.ts:667

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;

Inherited from

DirectedGraph.tarjan

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

DirectedGraph.toArray

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.

Inherited from

DirectedGraph.toDot

topologicalSort()

topologicalSort(propertyName?): (VertexKey | VO)[] | undefined;

Defined in: data-structures/graph/directed-graph.ts:525

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;

Inherited from

DirectedGraph.topologicalSort

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.

Inherited from

DirectedGraph.toVisual

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

DirectedGraph.values

fromEntries()

static fromEntries<V>(entries): DirectedGraph<V, undefined, DirectedVertex<V>, DirectedEdge<undefined>>;

Defined in: data-structures/graph/directed-graph.ts:183

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)

Inherited from

DirectedGraph.fromEntries

fromKeys()

static fromKeys<K>(keys): DirectedGraph<K, undefined, DirectedVertex<K>, DirectedEdge<undefined>>;

Defined in: data-structures/graph/directed-graph.ts:166

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)

Inherited from

DirectedGraph.fromKeys

Protected Members

_edgeConnector

Get Signature

get protected _edgeConnector(): string;

Defined in: data-structures/graph/directed-graph.ts:155

The edge connector string used in visual output. Override in subclasses (e.g., '--' for undirected, '->' for directed).

Returns

string

Inherited from

DirectedGraph._edgeConnector

_addEdge()

protected _addEdge(edge): boolean;

Defined in: data-structures/graph/directed-graph.ts:752

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)

Inherited from

DirectedGraph._addEdge

_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)

Inherited from

DirectedGraph._addVertex

_createInstance()

protected _createInstance(options?): this;

Defined in: data-structures/graph/map-graph.ts:178

Re-create a same-species MapGraph instance from snapshot options.

Parameters

options?

Partial<Record<string, unknown>>

Snapshot options providing originCoord/bottomRight.

Returns

this

Empty MapGraph instance of this type.

Remarks

Time O(1), Space O(1)

Overrides

DirectedGraph._createInstance

_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)

Inherited from

DirectedGraph._createLike

_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)

Inherited from

DirectedGraph._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)

Inherited from

DirectedGraph._getVertex

_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)

Inherited from

DirectedGraph._getVertexKey

_snapshotOptions()

protected _snapshotOptions(): Record<string, unknown>;

Defined in: data-structures/graph/map-graph.ts:168

Include originCoord and bottomRight so clone()/filter() preserve geospatial settings.

Returns

Record<string, unknown>

Options bag extending super snapshot.

Remarks

Time O(1), Space O(1)

Overrides

DirectedGraph._snapshotOptions

Class: MapGraph<V, E, VO, EO>

Remarks​

Examples​

Extends​

Type Parameters​

V​

E​

VO​

EO​

Constructors​

Constructor​

Parameters​

originCoord​

bottomRight?​

Returns​

Remarks​

Overrides​

Accessors​

size​

Get Signature​

Remarks​

Returns​

Inherited from​

Methods​

[iterator]()​

Parameters​

args​

Returns​

Remarks​

Inherited from​

addEdge()​

Param​

Param​

Param​

Param​

Remarks​

Call Signature​

Parameters​

edge​

Returns​

Inherited from​

Call Signature​

Parameters​

src​

dest​

weight?​

value?​

Returns​

Inherited from​

addVertex()​

Param​

Param​

Remarks​

Call Signature​

Parameters​

vertex​

Returns​

Inherited from​

Call Signature​

Parameters​

key​

value?​

Returns​

Inherited from​

bellmanFord()​

Parameters​

src​

scanNegativeCycle?​

getMin?​

genPath?​

Returns​

distMap​

hasNegativeCycle​

min​

minPath​

paths​

preMap​

Remarks​

Inherited from​

clear()​

Remarks

Examples

Extends

Type Parameters

V

E

VO

EO

Constructors

Constructor

Parameters

originCoord

bottomRight?

Returns

Remarks

Overrides

Accessors

size

Get Signature

Remarks

Returns

Inherited from

Methods

[iterator]()

Parameters

args

Returns

Remarks

Inherited from

addEdge()

Param

Param

Param

Param

Remarks

Call Signature

Parameters

edge

Returns

Inherited from

Call Signature

Parameters

src

dest

weight?

value?

Returns

Inherited from

addVertex()

Param

Param

Remarks

Call Signature

Parameters

vertex

Returns

Inherited from

Call Signature

Parameters

key

value?

Returns

Inherited from

bellmanFord()

Parameters

src

scanNegativeCycle?

getMin?

genPath?

Returns

distMap

hasNegativeCycle

min

minPath

paths

preMap

Remarks

Inherited from

clear()

Returns