Class DirectedGraph<V, E, VO, EO>

Directed graph implementation.

Remarks

Time O(1), Space O(1)

Example

// basic DirectedGraph vertex and edge creation
 // Create a simple directed graph
    const graph = new DirectedGraph<string>();

    // Add vertices
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');

    // Verify vertices exist
    console.log(graph.hasVertex('A')); // true;
    console.log(graph.hasVertex('B')); // true;
    console.log(graph.hasVertex('C')); // true;
    console.log(graph.hasVertex('D')); // false;

    // Check vertex count
    console.log(graph.size); // 3;

Example

// DirectedGraph edge operations
 const graph = new DirectedGraph<string>();

    // Add vertices
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');

    // Add directed edges
    graph.addEdge('A', 'B', 1);
    graph.addEdge('B', 'C', 2);
    graph.addEdge('A', 'C', 3);

    // Verify edges exist
    console.log(graph.hasEdge('A', 'B')); // true;
    console.log(graph.hasEdge('B', 'C')); // true;
    console.log(graph.hasEdge('C', 'B')); // false; // Graph is directed

    // Get neighbors of A
    const neighborsA = graph.getNeighbors('A');
    console.log(neighborsA[0].key); // 'B';
    console.log(neighborsA[1].key); // 'C';

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;

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;

Example

// DirectedGraph dijkstra shortest path for network routing
 // Build a weighted directed graph representing network nodes and costs
    const network = new DirectedGraph<string>();

    // Add network nodes
    network.addVertex('Router-A');
    network.addVertex('Router-B');
    network.addVertex('Router-C');
    network.addVertex('Router-D');
    network.addVertex('Router-E');

    // Add weighted edges (network latency costs)
    network.addEdge('Router-A', 'Router-B', 5);
    network.addEdge('Router-A', 'Router-C', 10);
    network.addEdge('Router-B', 'Router-D', 3);
    network.addEdge('Router-C', 'Router-D', 2);
    network.addEdge('Router-D', 'Router-E', 4);
    network.addEdge('Router-B', 'Router-E', 12);

    // Find shortest path from Router-A to Router-E
    const { minDist, minPath } = network.dijkstra('Router-A', 'Router-E', true, true) || {
      minDist: undefined,
      minPath: undefined
    };

    // Verify shortest path is found
    console.log(minDist); // defined;
    console.log(minPath); // defined;

    // Shortest path should be A -> B -> D -> E with cost 5+3+4=12
    // Or A -> C -> D -> E with cost 10+2+4=16
    // So the minimum is 12
    console.log(minDist); // <= 16;

    // Verify path is valid (includes start and end)
    console.log(minPath?.[0].key); // 'Router-A';
    console.log(minPath?.[minPath.length - 1].key); // 'Router-E';

Type Parameters

Hierarchy (view full)

Implements

Constructors

constructor

Accessors

size

Methods

_addEdge _addVertex _createInstance _createLike _getIterator _getVertex _getVertexKey _snapshotOptions [iterator] addEdge addVertex bellmanFord clear clone createEdge createVertex degreeOf deleteEdge deleteEdgeSrcToDest deleteVertex dijkstraWithoutHeap edgeSet edgesOf entries every filter filterEntries find floydWarshall forEach get getAllPathsBetween getCycles getDestinations getDFNMap getEdge getEndsOfEdge getLowMap getMinCostBetween getMinPathBetween getNeighbors getPathSumWeight getSCCs getVertex has hasEdge hasValue hasVertex incomingEdgesOf isEmpty isVertexKey keys map outgoingEdgesOf print reduce removeManyVertices setEdgeWeight some tarjan toArray topologicalSort toVisual values fromEntries fromKeys

Constructors

constructor

Accessors

size

Methods

Protected_addEdge

Protected_addVertex

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)

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)

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)

Protected_getVertex

Protected_getVertexKey

Protected_snapshotOptions

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

addEdge

addVertex

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)

clear

clone

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)

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)

degreeOf

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)

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)

deleteVertex

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)

edgeSet

edgesOf

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)

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)

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)

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)

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)

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)

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)

get

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)

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)

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)

getDFNMap

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)

getEndsOfEdge

getLowMap

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)

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)

getNeighbors

getPathSumWeight

getSCCs

getVertex

has

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)

hasValue

hasVertex

incomingEdgesOf

isEmpty

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)

keys

map

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)

print

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)

removeManyVertices

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)

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)

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)

toArray

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)

toVisual

values

StaticfromEntries

StaticfromKeys

Settings

Member Visibility

On This Page

Constructors
Accessors
Methods