Skip to main content

​
Class: Graph<T>

Defined in: graph.ts:118 Weighted Graph with Adjacency List representation Supports both directed and undirected graphs with weighted edges. Implements common graph algorithms including BFS, DFS, Dijkstra’s shortest path, A* search, and topological sort. Time Complexity:
  • addVertex: O(1)
  • addEdge: O(1)
  • removeVertex: O(V + E)
  • removeEdge: O(E)
  • BFS/DFS: O(V + E)
  • Dijkstra/A*: O((V + E) log V) with priority queue
Space Complexity: O(V + E)

​
Example

const graph = new Graph<string>();
graph.addVertex('A').addVertex('B').addVertex('C');
graph.addEdge('A', 'B', 1);
graph.addEdge('A', 'C', 4);
const path = graph.findShortestPath('A', 'C');

​
Type Parameters

​
T

T Type of vertex identifiers

​
Constructors

​
Constructor

new Graph<T>(options?): Graph<T>
Defined in: graph.ts:127 Creates a new Graph

​
Parameters

options?
GraphOptions = {} Configuration options

​
Returns

Graph<T>

​
Throws

Error if options validation fails

​
Accessors

​
edgeCount

​
Get Signature

get edgeCount(): number
Defined in: graph.ts:147 Returns the total number of edges in the graph
Returns
number

​
vertexCount

​
Get Signature

get vertexCount(): number
Defined in: graph.ts:140 Returns the number of vertices in the graph
Returns
number

​
Methods

​
addEdge()

addEdge(source, target, weight?, metadata?): this
Defined in: graph.ts:197 Adds an edge between two vertices

​
Parameters

source
T
target
T
weight?
number = 1
metadata?
Record<string, unknown>

​
Returns

this This graph for chaining

​
addVertex()

addVertex(vertex, metadata?): this
Defined in: graph.ts:175 Adds a vertex to the graph

​
Parameters

vertex
T
metadata?
Record<string, unknown>

​
Returns

this This graph for chaining

​
addVertices()

addVertices(vertices): this
Defined in: graph.ts:186 Adds multiple vertices at once

​
Parameters

vertices
T[]

​
Returns

this This graph for chaining

​
astar()

astar(start, end, h): &#123; cost: number; path: T[]; &#125; | null
Defined in: graph.ts:434 Finds the shortest path using A* search with a heuristic function

​
Parameters

start
T Starting vertex
end
T Ending vertex
h
(a, b) => number Heuristic function estimating cost from a vertex to end

​
Returns

&#123; cost: number; path: T[]; &#125; | null Path and cost, or null if no path exists

​
bfs()

bfs(start): TraversalResult<T>
Defined in: graph.ts:288 Breadth-First Search traversal

​
Parameters

start
T Starting vertex

​
Returns

TraversalResult<T> Traversal result with vertices, parents, and distances

​
clear()

clear(): void
Defined in: graph.ts:625 Clears all vertices and edges

​
Returns

void

​
dfs()

dfs(start): TraversalResult<T>
Defined in: graph.ts:329 Depth-First Search traversal

​
Parameters

start
T Starting vertex

​
Returns

TraversalResult<T> Traversal result with vertices and parents

​
findAllPaths()

findAllPaths(start, end, maxDepth?): T[][]
Defined in: graph.ts:478 Finds all paths between two vertices (limited by max depth)

​
Parameters

start
T Starting vertex
end
T Ending vertex
maxDepth?
number = 10 Maximum path depth (default: 10)

​
Returns

T[][] Array of all paths found

​
findShortestPath()

findShortestPath(start, end): PathResult<T>
Defined in: graph.ts:365 Finds the shortest path between two vertices using Dijkstra’s algorithm

​
Parameters

start
T Starting vertex
end
T Ending vertex

​
Returns

PathResult<T> Path result with vertices and total distance

​
getConnectedComponents()

getConnectedComponents(): T[][]
Defined in: graph.ts:594 Gets connected components in an undirected graph

​
Returns

T[][] Array of connected components (each component is an array of vertices)

​
getNeighbors()

getNeighbors(vertex): Edge<T>[]
Defined in: graph.ts:264 Gets all neighbors of a vertex

​
Parameters

vertex
T

​
Returns

Edge<T>[]

​
getVertexMetadata()

getVertexMetadata(vertex): Record<string, unknown> | undefined
Defined in: graph.ts:278 Gets vertex metadata

​
Parameters

vertex
T

​
Returns

Record<string, unknown> | undefined

​
getVertices()

getVertices(): T[]
Defined in: graph.ts:271 Gets all vertices in the graph

​
Returns

T[]

​
hasCycle()

hasCycle(): boolean
Defined in: graph.ts:560 Detects if the graph contains a cycle

​
Returns

boolean

​
hasEdge()

hasEdge(source, target): boolean
Defined in: graph.ts:165 Checks if an edge exists between two vertices

​
Parameters

source
T
target
T

​
Returns

boolean

​
hasVertex()

hasVertex(vertex): boolean
Defined in: graph.ts:158 Checks if the graph has a vertex

​
Parameters

vertex
T

​
Returns

boolean

​
removeEdge()

removeEdge(source, target): boolean
Defined in: graph.ts:244 Removes an edge between two vertices

​
Parameters

source
T
target
T

​
Returns

boolean True if edge was removed

​
removeVertex()

removeVertex(vertex): boolean
Defined in: graph.ts:229 Removes a vertex and all its edges

​
Parameters

vertex
T

​
Returns

boolean True if vertex was removed

​
toAdjacencyMatrix()

toAdjacencyMatrix(): object
Defined in: graph.ts:632 Converts graph to adjacency matrix representation

​
Returns

object
matrix
matrix: number[][]
vertices
vertices: T[]

​
topologicalSort()

topologicalSort(): T[] | null
Defined in: graph.ts:516 Performs topological sort on a directed acyclic graph (DAG)

​
Returns

T[] | null Topologically sorted vertices or null if cycle detected

​
Throws

Error if called on an undirected graph