README
@datastructures-js/graph
Graph & Directed Graph implementation in javascript.
Contents
- Install
- require
- import
- API
- constructor
- .addVertex(key, value)
- .hasVertex(key)
- .getVerticesCount()
- .addEdge(srcKey, destKey, weight)
- .hasEdge(srcKey, destKey)
- .getEdgesCount()
- .getWeight(srcKey, destKey)
- .removeVertex(key)
- .removeEdge(srcKey, destKey)
- .removeEdges(key)
- .traverseDfs(srcKey, cb)
- .traverseBfs(srcKey, cb)
- .clear()
- Build
- License
install
npm install --save @datastructures-js/graph
require
const { Graph, DirectedGraph } = require('@datastructures-js/graph');
import
import { Graph, DirectedGraph } from '@datastructures-js/graph';
API
constructor
Creates a new graph
JS
const directedGraph = new DirectedGraph();
const graph = new Graph();
TS
// DirectedGraph<T extends number|string, U = undefined>
const directedGraph = new DirectedGraph<number, { id: string, someProp: any }>();
// Graph<T extends number|string, U = undefined>
const graph = new Graph<string, number>();
.addVertex(key, value)
Adds a vertex to the graph.
params | return | runtime |
---|---|---|
key: T (number | string)
value: U |
Graph<T, U> | DirectedGraph<T, U> | O(1) |
directedGraph
.addVertex('v1', 1)
.addVertex('v2', 2)
.addVertex('v3', 3)
.addVertex('v4', 4)
.addVertex('v5', 5);
graph
.addVertex('v1', true)
.addVertex('v2', true)
.addVertex('v3', true)
.addVertex('v4', true)
.addVertex('v5', true);
.hasVertex(key)
Checks if the graph has a vertex by its key.
params | return | runtime |
---|---|---|
key: T (number | string) | boolean | O(1) |
console.log(directedGraph.hasVertex('v7')); // false
console.log(graph.hasVertex('v1')); // true
.getVerticesCount()
Gets the number of vertices in the graph.
return | runtime |
---|---|
number | O(1) |
console.log(directedGraph.getVerticesCount()); // 5
console.log(graph.getVerticesCount()); // 5
.addEdge(srcKey, destKey, weight)
Adds a weighted edge between two existings vertices. Default weight is 1 if not defined. The single edge is a direction from source to destination in a directed graph, and a two-way connection in a graph.
params | return | runtime |
---|---|---|
srcKey: T (number | string)
destKey: T (number | string) weight: number |
Graph<T, U> | DirectedGraph<T, U> | O(1) |
directedGraph
.addEdge('v1', 'v2', 2)
.addEdge('v1', 'v3', 3)
.addEdge('v1', 'v4', 1)
.addEdge('v2', 'v4', 1)
.addEdge('v3', 'v5', 2)
.addEdge('v4', 'v3', 1)
.addEdge('v4', 'v5', 4);
graph
.addEdge('v1', 'v2', 2)
.addEdge('v2', 'v3', 3)
.addEdge('v1', 'v3', 6)
.addEdge('v2', 'v4', 1)
.addEdge('v4', 'v3', 1)
.addEdge('v4', 'v5', 4)
.addEdge('v3', 'v5', 2);
.hasEdge(srcKey, destKey)
Checks if the graph has an edge between two existing vertices. In directed graph, it returns true only if there is a direction from source to destination.
params | return | runtime |
---|---|---|
srcKey: T (number | string)
destKey: T (number | string) |
boolean | O(1) |
console.log(directedGraph.hasEdge('v1', 'v2')); // true
console.log(directedGraph.hasEdge('v2', 'v1')); // false
console.log(graph.hasEdge('v1', 'v2')); // true
console.log(graph.hasEdge('v2', 'v1')); // true
.getEdgesCount()
Gets the number of edges in the graph.
return | runtime |
---|---|
number | O(1) |
console.log(directedGraph.getEdgesCount()); // 7
console.log(graph.getEdgesCount()); // 7
.getWeight(srcKey, destKey)
Gets the edge's weight between two vertices. If there is no direct edge between the two vertices, it returns Infinity
. It also returns 0 if the source key is equal to destination key.
params | return | runtime |
---|---|---|
srcKey: T (number | string)
destKey: T (number | string) |
number | O(1) |
console.log(directedGraph.getWeight('v1', 'v2')); // 2
console.log(directedGraph.getWeight('v2', 'v1')); // Infinity
console.log(directedGraph.getWeight('v1', 'v1')); // 0
console.log(graph.getWeight('v1', 'v2')); // 2
console.log(graph.getWeight('v2', 'v1')); // 2
console.log(graph.getWeight('v1', 'v1')); // 0
console.log(graph.getWeight('v1', 'v4')); // Infinity
.removeVertex(key)
Removes a vertex with all its edges from the graph.
params | return | runtime |
---|---|---|
key: T (number | string) | boolean |
Graph: O(K) : K = number of connected edges to the vertex
DirectedGraph: O(E) : E = number of edges in the graph |
directedGraph.removeVertex('v5');
console.log(directedGraph.getVerticesCount()); // 4
console.log(directedGraph.getEdgesCount()); // 5
graph.removeVertex('v5');
console.log(graph.getVerticesCount()); // 4
console.log(graph.getEdgesCount()); // 5
.removeEdge(srcKey, destKey)
Removes an edge between two existing vertices
params | return | runtime |
---|---|---|
srcKey: T (number | string)
destKey: T (number | string) |
boolean | O(1) |
directedGraph.removeEdge('v1', 'v3'); // true
console.log(directedGraph.getEdgesCount()); // 4
graph.removeEdge('v2', 'v3'); // true
console.log(graph.getEdgesCount()); // 4
.removeEdges(key)
Removes all connected edges to a vertex and returns the number of removed edges.
params | return | runtime |
---|---|---|
key: T (number | string) | number |
Graph: O(K) : K = number of connected edges to the vertex
DirectedGraph: O(E) : E = number of edges in the graph |
const dg = new DirectedGraph()
.addVertex('v1')
.addVertex('v2')
.addVertex('v3')
.addEdge('v1', 'v2')
.addEdge('v2', 'v1')
.addEdge('v1', 'v3')
.removeEdges('v1'); // 3
const g = new Graph()
.addVertex('v1')
.addVertex('v2')
.addVertex('v3')
.addEdge('v1', 'v2')
.addEdge('v1', 'v3')
.removeEdges('v1'); // 2
.traverseDfs(srcKey, cb)
Traverses the graph using the depth-first recursive search.
params | runtime |
---|---|
srcKey: T (number | string)
cb: (key: T, value: U) => void |
O(V) : V = number of vertices in the graph |
directedGraph.traverseDfs('v1', (key, value) => console.log(`${key}: ${value}`));
/*
v1: 1
v2: 2
v4: 4
v3: 3
*/
graph.traverseDfs('v1', (key, value) => console.log(`${key}: ${value}`));
/*
v1: true
v2: true
v4: true
v3: true
*/
.traverseBfs(srcKey, cb)
Traverses the graph using the breadth-first search with a queue.
params | runtime |
---|---|
srcKey: T (number | string)
cb: (key: T, value: U) => void |
O(V) : V = number of vertices in the graph |
directedGraph.traverseBfs('v1', (key, value) => console.log(`${key}: ${value}`));
/*
v1: 1
v2: 2
v4: 4
v3: 3
*/
graph.traverseBfs('v1', (key, value) => console.log(`${key}: ${value}`));
/*
v1: true
v2: true
v3: true
v4: true
*/
.clear()
Clears all vertices and edges in the graph.
runtime |
---|
O(1) |
directedGraph.clear();
console.log(directedGraph.getVerticesCount()); // 0
console.log(directedGraph.getEdgesCount()); // 0
graph.clear();
console.log(graph.getVerticesCount()); // 0
console.log(graph.getEdgesCount()); // 0
Build
grunt build
License
The MIT License. Full License is here