@datastructures-js/graph

@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

Changelog

[v5.1.2] - 2022-02-11

Fixed

• getWeight type definition.