Class UndirectedGraph<V, E, VO, EO>

Undirected graph implementation.

Remarks

Time O(1), Space O(1)

Example

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

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

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

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

Example

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

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

    // Add undirected edges (both directions automatically)
    graph.addEdge('A', 'B', 1);
    graph.addEdge('B', 'C', 2);
    graph.addEdge('A', 'C', 3);

    // Verify edges exist in both directions
    console.log(graph.hasEdge('A', 'B')); // true;
    console.log(graph.hasEdge('B', 'A')); // true; // Bidirectional!

    console.log(graph.hasEdge('C', 'B')); // true;
    console.log(graph.hasEdge('B', 'C')); // true; // Bidirectional!

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

Example

// UndirectedGraph deleteEdge and vertex operations
 const graph = new UndirectedGraph<string>();

    // Build a simple undirected graph
    graph.addVertex('X');
    graph.addVertex('Y');
    graph.addVertex('Z');
    graph.addEdge('X', 'Y', 1);
    graph.addEdge('Y', 'Z', 2);
    graph.addEdge('X', 'Z', 3);

    // Delete an edge
    graph.deleteEdge('X', 'Y');
    console.log(graph.hasEdge('X', 'Y')); // false;

    // Bidirectional deletion confirmed
    console.log(graph.hasEdge('Y', 'X')); // false;

    // Other edges should remain
    console.log(graph.hasEdge('Y', 'Z')); // true;
    console.log(graph.hasEdge('Z', 'Y')); // true;

    // Delete a vertex
    graph.deleteVertex('Y');
    console.log(graph.hasVertex('Y')); // false;
    console.log(graph.size); // 2;

Example

// UndirectedGraph connectivity and neighbors
 const graph = new UndirectedGraph<string>();

    // Build a friendship network
    const people = ['Alice', 'Bob', 'Charlie', 'Diana', 'Eve'];
    for (const person of people) {
      graph.addVertex(person);
    }

    // Add friendships (undirected edges)
    graph.addEdge('Alice', 'Bob', 1);
    graph.addEdge('Alice', 'Charlie', 1);
    graph.addEdge('Bob', 'Diana', 1);
    graph.addEdge('Charlie', 'Eve', 1);
    graph.addEdge('Diana', 'Eve', 1);

    // Get friends of each person
    const aliceFriends = graph.getNeighbors('Alice');
    console.log(aliceFriends[0].key); // 'Bob';
    console.log(aliceFriends[1].key); // 'Charlie';
    console.log(aliceFriends.length); // 2;

    const dianaFriends = graph.getNeighbors('Diana');
    console.log(dianaFriends[0].key); // 'Bob';
    console.log(dianaFriends[1].key); // 'Eve';
    console.log(dianaFriends.length); // 2;

    // Verify bidirectional friendship
    const bobFriends = graph.getNeighbors('Bob');
    console.log(bobFriends[0].key); // 'Alice'; // Alice -> Bob -> Alice ✓
    console.log(bobFriends[1].key); // 'Diana';

Example

// UndirectedGraph for social network connectivity analysis
 interface Person {
      id: number;
      name: string;
      location: string;
    }

    // UndirectedGraph is perfect for modeling symmetric relationships
    // (friendships, collaborations, partnerships)
    const socialNetwork = new UndirectedGraph<number, Person>();

    // Add people as vertices
    const people: [number, Person][] = [
      [1, { id: 1, name: 'Alice', location: 'New York' }],
      [2, { id: 2, name: 'Bob', location: 'San Francisco' }],
      [3, { id: 3, name: 'Charlie', location: 'Boston' }],
      [4, { id: 4, name: 'Diana', location: 'New York' }],
      [5, { id: 5, name: 'Eve', location: 'Seattle' }]
    ];

    for (const [id] of people) {
      socialNetwork.addVertex(id);
    }

    // Add friendships (automatically bidirectional)
    socialNetwork.addEdge(1, 2, 1); // Alice <-> Bob
    socialNetwork.addEdge(1, 3, 1); // Alice <-> Charlie
    socialNetwork.addEdge(2, 4, 1); // Bob <-> Diana
    socialNetwork.addEdge(3, 5, 1); // Charlie <-> Eve
    socialNetwork.addEdge(4, 5, 1); // Diana <-> Eve

    console.log(socialNetwork.size); // 5;

    // Find direct connections for Alice
    const aliceConnections = socialNetwork.getNeighbors(1);
    console.log(aliceConnections[0].key); // 2;
    console.log(aliceConnections[1].key); // 3;
    console.log(aliceConnections.length); // 2;

    // Verify bidirectional connections
    console.log(socialNetwork.hasEdge(1, 2)); // true;
    console.log(socialNetwork.hasEdge(2, 1)); // true; // Friendship works both ways!

    // Remove a person from network
    socialNetwork.deleteVertex(2); // Bob leaves
    console.log(socialNetwork.hasVertex(2)); // false;
    console.log(socialNetwork.size); // 4;

    // Alice loses Bob as a friend
    const updatedAliceConnections = socialNetwork.getNeighbors(1);
    console.log(updatedAliceConnections[0].key); // 3;
    console.log(updatedAliceConnections[1]); // undefined;

    // Diana loses Bob as a friend
    const dianaConnections = socialNetwork.getNeighbors(4);
    console.log(dianaConnections[0].key); // 5;
    console.log(dianaConnections[1]); // undefined;

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 deleteEdgeBetween deleteVertex dijkstraWithoutHeap edgeSet edgesOf entries every filter filterEntries find floydWarshall forEach get getAllPathsBetween getBridges getCutVertices getCycles getDFNMap getEdge getEndsOfEdge getLowMap getMinCostBetween getMinPathBetween getNeighbors getPathSumWeight getVertex has hasEdge hasValue hasVertex isEmpty isVertexKey keys map print reduce removeManyVertices setEdgeWeight some tarjan toArray 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(v1, v2, weight?, value?): EO

  • Create an undirected edge instance. Does not insert into the graph.

    Parameters

    • v1: VertexKey

      One endpoint key.

    • v2: VertexKey

      The other endpoint key.

    • Optionalweight: number

      Edge weight; defaults to defaultEdgeWeight.

    • Optionalvalue: EO["value"]

      Edge payload.

    Returns EO

    Concrete edge instance.

    Remarks

    Time O(1), Space O(1)

createVertex

  • createVertex(key, value?): VO

  • Create an undirected 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(edgeOrOneSideVertexKey, otherSideVertexKey?): undefined | EO

  • Delete an edge by instance or by a pair of keys.

    Parameters

    • edgeOrOneSideVertexKey: VertexKey | EO

      Edge instance or one endpoint vertex/key.

    • OptionalotherSideVertexKey: VertexKey

      Required second endpoint when deleting by pair.

    Returns undefined | EO

    Removed edge or undefined.

    Remarks

    Time O(1) avg, Space O(1)

deleteEdgeBetween

  • deleteEdgeBetween(v1, v2): undefined | EO

  • Delete a single undirected edge between two vertices.

    Parameters

    • v1: VertexKey | VO

      One vertex or key.

    • v2: VertexKey | VO

      The other 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)

getBridges

getCutVertices

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)

getDFNMap

getEdge

  • getEdge(v1, v2): undefined | EO

  • Get an undirected edge between two vertices, if present.

    Parameters

    • v1: undefined | VertexKey | VO

      One vertex or key.

    • v2: undefined | VertexKey | VO

      The other 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

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

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

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(): {
        bridges: EO[];
        cutVertices: VO[];
        dfnMap: Map<VO, number>;
        lowMap: Map<VO, number>;
    }

  • Tarjan-based bridge and articulation point detection.

    Returns {
        bridges: EO[];
        cutVertices: VO[];
        dfnMap: Map<VO, number>;
        lowMap: Map<VO, number>;
    }

    { dfnMap, lowMap, bridges, cutVertices }.

    • bridges: EO[]
    • cutVertices: VO[]
    • dfnMap: Map<VO, number>
    • lowMap: Map<VO, number>

    Remarks

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

toArray

toVisual

values

StaticfromEntries

StaticfromKeys

Settings

Member Visibility

On This Page

Constructors
Accessors
Methods