MapGraph

data-structure-typed

---

data-structure-typed / MapGraph

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

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

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:108

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:89

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:254

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:256

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:189

Parameters

vertex

VO

Returns

boolean

Inherited from

DirectedGraph.addVertex

Call Signature

addVertex(key, value?): boolean;

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

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: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

DirectedGraph.bellmanFord

---

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)

Inherited from

DirectedGraph.clear

---

clone()

clone(): this;

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

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:153

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:135

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

Inherited from

DirectedGraph.degreeOf

---

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;

Inherited from

DirectedGraph.deleteEdge

---

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)

Inherited from

DirectedGraph.deleteEdgeSrcToDest

---

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;

Inherited from

DirectedGraph.deleteVertex

---

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

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

Inherited from

DirectedGraph.edgeSet

---

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)

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

Inherited from

DirectedGraph.filter

---

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

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: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

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: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

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

DirectedGraph.getCycles

---

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)

Inherited from

DirectedGraph.getDestinations

---

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)

Inherited from

DirectedGraph.getDFNMap

---

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;

Inherited from

DirectedGraph.getEdge

---

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)

Inherited from

DirectedGraph.getEndsOfEdge

---

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)

Inherited from

DirectedGraph.getLowMap

---

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

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

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

Inherited from

DirectedGraph.getNeighbors

---

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

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

Inherited from

DirectedGraph.getSCCs

---

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)

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: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

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

Inherited from

DirectedGraph.hasVertex

---

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;

Inherited from

DirectedGraph.incomingEdgesOf

---

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)

Inherited from

DirectedGraph.isEmpty

---

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

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: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

DirectedGraph.map

---

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;

Inherited from

DirectedGraph.outgoingEdgesOf

---

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

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: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

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

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: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;

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: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

DirectedGraph.toDot

---

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;

Inherited from

DirectedGraph.topologicalSort

---

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

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

Inherited from

DirectedGraph.fromEntries

---

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)

Inherited from

DirectedGraph.fromKeys

---

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

Inherited from

DirectedGraph._edgeConnector

---

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

Inherited from

DirectedGraph._addEdge

---

_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

DirectedGraph._addVertex

---

_createInstance()

protected _createInstance(options?): this;

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

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: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

DirectedGraph._createLike

---

_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

DirectedGraph._getIterator

---

_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

DirectedGraph._getVertex

---

_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

DirectedGraph._getVertexKey

---

_snapshotOptions()

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

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

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

---