@datastructures-js/graph

@datastructures-js/graph

Table of Contents

• Install
• API
  • require
  • import
  • Creating a Graph
  • .addVertex(key, value)
  • .hasVertex(key)
  • .verticesCount()
  • .addEdge(srcKey, destKey, weight)
  • .hasEdge(srcKey, destKey)
  • .edgesCount()
  • .getWeight(srcKey, destKey)
  • .removeVertex(key)
  • .removeEdge(key)
  • .traverseDfs(srcKey)
  • .traverseBfs(srcKey)
  • .clear()
• Build
• License

install

npm install --save @datastructures-js/graph

API

require

const { Graph, DirectedGraph } = require('@datastructures-js/graph');

import

import { Graph, DirectedGraph } from '@datastructures-js/graph';

create a graph

creates an empty graph

Example

const directedGraph = new DirectedGraph();

const graph = new Graph();

.addVertex(key, value)

adds a vertex to the graph.

runtime	params
O(1)	key: {number} or {string} value: {object}

Example

directedGraph.addVertex('v1', 1);
directedGraph.addVertex('v1', 1);
directedGraph.addVertex('v2', 2);
directedGraph.addVertex('v3', 3);
directedGraph.addVertex('v4', 4);
directedGraph.addVertex('v5', 5);

graph.addVertex('v1', true);
graph.addVertex('v2', true);
graph.addVertex('v3', true);
graph.addVertex('v4', true);
graph.addVertex('v5', true);

.hasVertex(key)

checks if the graph has a vertex by its key.

runtime	params
O(1)	key: {number} or {string}

Example

console.log(directedGraph.hasVertex('v7')); // false
console.log(graph.hasVertex('v1')); // true

.verticesCount()

gets the number of vertices in the graph.

runtime	return
O(1)	{number}

Example

console.log(directedGraph.verticesCount()); // 5
console.log(graph.verticesCount()); // 5

.addEdge(srcKey, destKey, weight)

adds an edge with a weight between two existings vertices. Default weight is 1 if not defined. The edge is directed when added in a directed graph, and two-ways when added in a graph.

runtime	params
O(1)	srcKey: {number} or {string} the source vertex key destKey: {number} or {string} the destination vertex key weight: {number} the weight of the edge

Example

directedGraph.addEdge('v1', 'v2', 2);
directedGraph.addEdge('v1', 'v3', 3);
directedGraph.addEdge('v1', 'v4', 1);
directedGraph.addEdge('v2', 'v4', 1);
directedGraph.addEdge('v3', 'v5', 2);
directedGraph.addEdge('v4', 'v3', 1);
directedGraph.addEdge('v4', 'v5', 4);

graph.addEdge('v1', 'v2', 2);
graph.addEdge('v2', 'v3', 3);
graph.addEdge('v1', 'v3', 6);
graph.addEdge('v2', 'v4', 1);
graph.addEdge('v4', 'v3', 1);
graph.addEdge('v4', 'v5', 4);
graph.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.

runtime	params
O(1)	srcKey: {number} or {string} the source vertex key destKey: {number} or {string} the destination vertex key

Example

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

.edgesCount()

gets the number of edges in the graph.

runtime	return
O(1)	{number}

Example

console.log(directedGraph.edgesCount()); // 7
console.log(graph.edgesCount()); // 7

.getWeight(srcKey, destKey)

gets the edge's weight between two vertices in the graph. If there is no direct edge between the two vertices, it returns null. It also returns 0 if the source key is equal to destination key.

runtime	return
O(1)	{number} or {null}

Example

console.log(directedGraph.getWeight('v1', 'v2')); // 2
console.log(directedGraph.getWeight('v2', 'v1')); // null
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')); // null

.removeVertex(key)

removes a vertex and all its edges from the graph

runtime	params
Directed Graph: O(E) : E = number of edges in the graph	key: {number} or {string} the vertex key
Graph: O(K) : K ∈ E = number of connected edges to key

Example

directedGraph.removeVertex('v5');
console.log(directedGraph.verticesCount()); // 4
console.log(directedGraph.edgesCount()); // 5

graph.removeVertex('v5');
console.log(graph.verticesCount()); // 4
console.log(graph.edgesCount()); // 5

.removeEdge(srcKey, destKey)

removes an edge between two existing vertices

runtime	params
O(1)	key: {number} or {string} the vertex key

Example

directedGraph.removeEdge('v1', 'v3');
console.log(directedGraph.edgesCount()); // 4

graph.removeEdge('v2', 'v3');
console.log(graph.edgesCount()); // 4

.traverseDfs(srcKey, cb)

traverses the graph using the depth-first recursive search.

runtime	params
O(V) : V = number of vertices in the graph	srcKey: {number} or {string} the starting vertex key cb: {function(Vertex)} the callback that is called with the traversed vertex object.

Example

directedGraph.traverseDfs('v1', (v) => console.log(`${v.getKey()}:${v.getValue()}`));
/*
v1:1
v2:2
v4:4
v3:3
*/

graph.traverseDfs('v1', (v) => console.log(v.serialize()));
/*
{ key: 'v1', value: true }
{ key: 'v2', value: true }
{ key: 'v4', value: true }
{ key: 'v3', value: true }
*/

.traverseBfs(srcKey, cb)

traverses the graph using the breadth-first search with a queue.

runtime	params
O(V) : V = number of vertices in the graph	srcKey: {number} or {string} the starting vertex key cb: {function(Vertex)} the callback that is called with the traversed vertex object.

Example

directedGraph.traverseBfs('v1', (v) => console.log(`${v.getKey()}:${v.getValue()}`));
/*
v1:1
v2:2
v4:4
v3:3
*/

graph.traverseBfs('v1', (v) => console.log(v.serialize()));
/*
{ key: 'v1', value: true }
{ key: 'v2', value: true }
{ key: 'v3', value: true }
{ key: 'v4', value: true }
*/

.clear()

clears all vertices and edges in the graph.

runtime
O(1)

Example

directedGraph.clear();
console.log(directedGraph.verticesCount()); // 0
console.log(directedGraph.edgesCount()); // 0

graph.clear();
console.log(graph.verticesCount()); // 0
console.log(graph.edgesCount()); // 0

Build

grunt build

License

The MIT License. Full License is here