Skip to main content

UndirectedGraph

data-structure-typed

data-structure-typed / UndirectedGraph

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

Defined in: data-structures/graph/undirected-graph.ts:137

Undirected graph implementation.

Remarks​

Time O(1), Space O(1)

Examples​

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

Extends​

Type Parameters​

V​

V = any

Vertex value type.

E​

E = any

Edge value type.

VO​

VO extends UndirectedVertex<V> = UndirectedVertex<V>

Concrete vertex class (extends AbstractVertex).

EO​

EO extends UndirectedEdge<E> = UndirectedEdge<E>

Concrete edge class (extends AbstractEdge).

Implements​

  • IGraph<V, E, VO, EO>

Constructors​

Constructor​

new UndirectedGraph<V, E, VO, EO>(options?): UndirectedGraph<V, E, VO, EO>;

Defined in: data-structures/graph/undirected-graph.ts:151

Construct an undirected graph with runtime defaults.

Parameters​

options?​

Partial<GraphOptions<V>>

GraphOptions<V> (e.g. vertexValueInitializer, defaultEdgeWeight).

Returns​

UndirectedGraph<V, E, VO, EO>

Remarks​

Time O(1), Space O(1)

Overrides​

AbstractGraph.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​

AbstractGraph.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​

AbstractGraph.[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​

AbstractGraph.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​

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

Implementation of​
IGraph.addVertex
Inherited from​

AbstractGraph.addVertex

Call Signature​

addVertex(key, value?): boolean;

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

Parameters​
key​

VertexKey

value?​

V

Returns​

boolean

Implementation of​
IGraph.addVertex
Inherited from​

AbstractGraph.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​

AbstractGraph.bellmanFord

clear()​

clear(): void;

Defined in: data-structures/graph/undirected-graph.ts:512

Remove all vertices and edges.

Returns​

void

Remarks​

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

Implementation of​

IGraph.clear

Overrides​

AbstractGraph.clear

clone()​

clone(): this;

Defined in: data-structures/graph/undirected-graph.ts:522

Deep clone as the same concrete class.

Returns​

this

A new graph of the same concrete class (this type).

Remarks​

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

Implementation of​

IGraph.clone

Overrides​

AbstractGraph.clone

createEdge()​

createEdge(
   v1, 
   v2, 
   weight?, 
   value?): EO;

Defined in: data-structures/graph/undirected-graph.ts:223

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

Parameters​

v1​

VertexKey

One endpoint key.

v2​

VertexKey

The other endpoint key.

weight?​

number

Edge weight; defaults to defaultEdgeWeight.

value?​

EO["value"]

Edge payload.

Returns​

EO

Concrete edge instance.

Remarks​

Time O(1), Space O(1)

Implementation of​

IGraph.createEdge

Overrides​

AbstractGraph.createEdge

createVertex()​

createVertex(key, value?): VO;

Defined in: data-structures/graph/undirected-graph.ts:210

Create an undirected vertex instance. Does not insert into the graph.

Parameters​

key​

VertexKey

Vertex identifier.

value?​

VO["value"]

Optional payload.

Returns​

VO

Concrete vertex instance.

Remarks​

Time O(1), Space O(1)

Implementation of​

IGraph.createVertex

Overrides​

AbstractGraph.createVertex

degreeOf()​

degreeOf(vertexOrKey): number;

Defined in: data-structures/graph/undirected-graph.ts:385

Degree of a vertex (# of incident undirected edges).

Parameters​

vertexOrKey​

VertexKey | VO

Vertex or key.

Returns​

number

Non-negative integer.

Remarks​

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

Implementation of​

IGraph.degreeOf

Overrides​

AbstractGraph.degreeOf

deleteEdge()​

deleteEdge(edgeOrOneSideVertexKey, otherSideVertexKey?): EO | undefined;

Defined in: data-structures/graph/undirected-graph.ts:312

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

Parameters​

edgeOrOneSideVertexKey​

VertexKey | EO

Edge instance or one endpoint vertex/key.

otherSideVertexKey?​

VertexKey

Required second endpoint when deleting by pair.

Returns​

EO | undefined

Removed edge or undefined.

Remarks​

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

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;

Implementation of​

IGraph.deleteEdge

Overrides​

AbstractGraph.deleteEdge

deleteEdgeBetween()​

deleteEdgeBetween(v1, v2): EO | undefined;

Defined in: data-structures/graph/undirected-graph.ts:260

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​

EO | undefined

Removed edge or undefined.

Remarks​

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

deleteVertex()​

deleteVertex(vertexOrKey): boolean;

Defined in: data-structures/graph/undirected-graph.ts:346

Delete a vertex and remove it from all neighbor lists.

Parameters​

vertexOrKey​

VertexKey | VO

Vertex or key.

Returns​

boolean

true if removed; otherwise false.

Remarks​

Time O(deg), Space O(1)

Example​

// Remove vertex and edges
 const g = new UndirectedGraph();
    g.addVertex('A');
    g.addVertex('B');
    g.addEdge('A', 'B');
    g.deleteVertex('A');
    console.log(g.hasVertex('A')); // false;

Implementation of​

IGraph.deleteVertex

Overrides​

AbstractGraph.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​

AbstractGraph.dijkstraWithoutHeap

edgeSet()​

edgeSet(): EO[];

Defined in: data-structures/graph/undirected-graph.ts:421

Unique set of undirected edges across endpoints.

Returns​

EO[]

Array of edges.

Remarks​

Time O(E), Space O(E)

Example​

// Get all edges
 const g = new UndirectedGraph();
    g.addVertex('A');
    g.addVertex('B');
    g.addEdge('A', 'B');
    console.log(g.edgeSet().length); // 1;

Implementation of​

IGraph.edgeSet

Overrides​

AbstractGraph.edgeSet

edgesOf()​

edgesOf(vertexOrKey): EO[];

Defined in: data-structures/graph/undirected-graph.ts:400

Incident undirected edges of a vertex.

Parameters​

vertexOrKey​

VertexKey | VO

Vertex or key.

Returns​

EO[]

Array of incident edges.

Remarks​

Time O(deg), Space O(deg)

Implementation of​

IGraph.edgesOf

Overrides​

AbstractGraph.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​

AbstractGraph.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​

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

Implementation of​

IGraph.filter

Inherited from​

AbstractGraph.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​

AbstractGraph.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​

AbstractGraph.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​

AbstractGraph.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​

AbstractGraph.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​

AbstractGraph.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​

AbstractGraph.getAllPathsBetween

getBiconnectedComponents()​

getBiconnectedComponents(): EO[][];

Defined in: data-structures/graph/undirected-graph.ts:597

Find biconnected components using edge-stack Tarjan variant. A biconnected component is a maximal biconnected subgraph.

Returns​

EO[][]

Array of edge arrays, each representing a biconnected component.

Remarks​

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

getBridges()​

getBridges(): EO[];

Defined in: data-structures/graph/undirected-graph.ts:703

Get bridges discovered by tarjan().

Returns​

EO[]

Array of edges that are bridges.

Remarks​

Time O(B), Space O(1)

Example​

// Find bridge edges
 const g = new UndirectedGraph();
    g.addVertex('A');
    g.addVertex('B');
    g.addVertex('C');
    g.addEdge('A', 'B');
    g.addEdge('B', 'C');
    const bridges = g.getBridges();
    console.log(bridges.length); // 2;

getCutVertices()​

getCutVertices(): VO[];

Defined in: data-structures/graph/undirected-graph.ts:723

Get articulation points discovered by tarjan().

Returns​

VO[]

Array of cut vertices.

Remarks​

Time O(C), Space O(1)

Example​

// Find articulation points
 const g = new UndirectedGraph();
    g.addVertex('A');
    g.addVertex('B');
    g.addVertex('C');
    g.addEdge('A', 'B');
    g.addEdge('B', 'C');
    const cuts = g.getCutVertices();
    console.log(cuts.length); // 1;
    console.log(cuts[0].key); // 'B';

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​

AbstractGraph.getCycles

getDFNMap()​

getDFNMap(): Map<VO, number>;

Defined in: data-structures/graph/undirected-graph.ts:732

DFN index map computed by tarjan().

Returns​

Map<VO, number>

Map from vertex to DFN index.

Remarks​

Time O(V), Space O(V)

getEdge()​

getEdge(v1, v2): EO | undefined;

Defined in: data-structures/graph/undirected-graph.ts:241

Get an undirected edge between two vertices, if present.

Parameters​

v1​

VertexKey | VO | undefined

One vertex or key.

v2​

VertexKey | VO | undefined

The other 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 UndirectedGraph();
    g.addVertex('A');
    g.addVertex('B');
    g.addEdge('A', 'B', 7);
    console.log(g.getEdge('A', 'B')?.weight); // 7;

Implementation of​

IGraph.getEdge

Overrides​

AbstractGraph.getEdge

getEndsOfEdge()​

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

Defined in: data-structures/graph/undirected-graph.ts:487

Resolve an edge's two endpoints to vertex instances.

Parameters​

edge​

EO

Edge instance.

Returns​

[VO, VO] | undefined

[v1, v2] or undefined if either endpoint is missing.

Remarks​

Time O(1), Space O(1)

Implementation of​

IGraph.getEndsOfEdge

Overrides​

AbstractGraph.getEndsOfEdge

getLowMap()​

getLowMap(): Map<VO, number>;

Defined in: data-structures/graph/undirected-graph.ts:741

LOW link map computed by tarjan().

Returns​

Map<VO, number>

Map from vertex to LOW value.

Remarks​

Time O(V), Space O(V)

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​

AbstractGraph.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​

AbstractGraph.getMinPathBetween

getNeighbors()​

getNeighbors(vertexOrKey): VO[];

Defined in: data-structures/graph/undirected-graph.ts:466

UndirectedGraph connectivity and neighbors

Parameters​

vertexOrKey​

VertexKey | VO

Returns​

VO[]

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

Implementation of​

IGraph.getNeighbors

Overrides​

AbstractGraph.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​

AbstractGraph.getPathSumWeight

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)

Implementation of​

IGraph.getVertex

Inherited from​

AbstractGraph.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​

AbstractGraph.has

hasCycle()​

hasCycle(): boolean;

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

Detect whether the graph contains a cycle. Uses DFS with parent tracking.

Returns​

boolean

true if a cycle exists, false otherwise.

Remarks​

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

Example​

// Detect cycle
 const g = new UndirectedGraph();
    g.addVertex('A');
    g.addVertex('B');
    g.addVertex('C');
    g.addEdge('A', 'B');
    g.addEdge('B', 'C');
    console.log(g.hasCycle()); // false;
    g.addEdge('C', 'A');
    console.log(g.hasCycle()); // true;

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​

AbstractGraph.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​

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

Implementation of​

IGraph.hasVertex

Inherited from​

AbstractGraph.hasVertex

isEmpty()​

isEmpty(): boolean;

Defined in: data-structures/graph/undirected-graph.ts:504

Whether the graph has no vertices and no edges.

Returns​

boolean

Remarks​

Time O(1), Space O(1)

Implementation of​

IGraph.isEmpty

Overrides​

AbstractGraph.isEmpty

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​

AbstractGraph.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​

AbstractGraph.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​

AbstractGraph.map

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​

AbstractGraph.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​

AbstractGraph.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​

AbstractGraph.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​

AbstractGraph.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​

AbstractGraph.some

tarjan()​

tarjan(): object;

Defined in: data-structures/graph/undirected-graph.ts:541

Tarjan-based bridge and articulation point detection.

Returns​

object

{ dfnMap, lowMap, bridges, cutVertices }.

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

Remarks​

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

Example​

// Find articulation points and bridges
 const g = new UndirectedGraph();
    g.addVertex('A');
    g.addVertex('B');
    g.addVertex('C');
    g.addEdge('A', 'B');
    g.addEdge('B', 'C');
    const result = g.tarjan();
    console.log(result); // defined;

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​

AbstractGraph.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​

AbstractGraph.toDot

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​

AbstractGraph.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​

AbstractGraph.values

fromEntries()​

static fromEntries<V>(entries): UndirectedGraph<V, undefined, UndirectedVertex<V>, UndirectedEdge<undefined>>;

Defined in: data-structures/graph/undirected-graph.ts:192

Construct an undirected graph from [key, value] entries.

Type Parameters​

V​

V

Vertex value type.

Parameters​

entries​

Iterable<[VertexKey, V]>

Iterable of [key, value] pairs.

Returns​

UndirectedGraph<V, undefined, UndirectedVertex<V>, UndirectedEdge<undefined>>

UndirectedGraph with all vertices added.

Remarks​

Time O(V), Space O(V)

fromKeys()​

static fromKeys<K>(keys): UndirectedGraph<K, undefined, UndirectedVertex<K>, UndirectedEdge<undefined>>;

Defined in: data-structures/graph/undirected-graph.ts:172

Construct an undirected 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​

UndirectedGraph<K, undefined, UndirectedVertex<K>, UndirectedEdge<undefined>>

UndirectedGraph with all keys added.

Remarks​

Time O(V), Space O(V)

Protected Members​

_edgeConnector​

Get Signature​

get protected _edgeConnector(): string;

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

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

Returns​

string

Inherited from​

AbstractGraph._edgeConnector

_addEdge()​

protected _addEdge(edge): boolean;

Defined in: data-structures/graph/undirected-graph.ts:751

Internal hook to attach an undirected edge into adjacency maps.

Parameters​

edge​

EO

Edge instance.

Returns​

boolean

true if both endpoints exist; otherwise false.

Remarks​

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

Overrides​

AbstractGraph._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​

AbstractGraph._addVertex

_createInstance()​

protected _createInstance(_options?): this;

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

Create an empty graph instance of the same concrete species.

Parameters​

_options?​

Partial<Record<string, unknown>>

Snapshot options from _snapshotOptions().

Returns​

this

A new empty graph instance of this type.

Remarks​

Time O(1), Space O(1)

Inherited from​

AbstractGraph._createInstance

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

AbstractGraph._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​

AbstractGraph._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​

AbstractGraph._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​

AbstractGraph._getVertexKey

_snapshotOptions()​

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

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

Capture configuration needed to reproduce the current graph.

Returns​

Record<string, unknown>

Options bag (opaque to callers).

Remarks​

Time O(1), Space O(1)

Inherited from​

AbstractGraph._snapshotOptions