@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, cb)
  • .traverseBfs(srcKey, cb)
  • .clear()
  • Vertex
• 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.

params
name	type
key	number or string
value	object

return
Vertex

runtime
O(1)

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.

params
name	type
key	number or string

return
boolean

runtime
O(1)

Example

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

.verticesCount()

gets the number of vertices in the graph.

return
number

runtime
O(1)

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 a direction from source to destination when added in a directed graph, and a connecting two-way edge when added in a graph.

params
name	type	description
srcKey	number or string	the source vertex key
destKey	number or string	the destination vertex key
weight	number	the weight of the edge

runtime
O(1)

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.

params
name	type	description
srcKey	number or string	the source vertex key
destKey	number or string	the destination vertex key

return
boolean

runtime
O(1)

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.

return
number

runtime
O(1)

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.

params
name	type	description
srcKey	number or string	the source vertex key
destKey	number or string	the destination vertex key

return
number

runtime
O(1)

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 with all its edges from the graph by its key.

params
name	type	description
key	number or string	the vertex key

return
boolean

runtime
Graph	O(K) : K = number of connected edges to the vertex
Directed Graph	O(E) : E = number of edges in the graph

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

params
name	type	description
srcKey	number or string	the source vertex key
destKey	number or string	the destination vertex key

return
boolean

runtime
O(1)

Example

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

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

.removeEdges(key)

removes all connected edges to a vertex by its key.

params
name	type	description
key	number or string	the vertex key

return
number	number of removed edges

runtime
Graph	O(K) : K = number of connected edges to the vertex
Directed Graph	O(E) : E = number of edges in the graph

Example

const dg = new DirectedGraph();
dg.addVertex('v1');
dg.addVertex('v2');
dg.addVertex('v3');
dg.addEdge('v1', 'v2');
dg.addEdge('v2', 'v1'); // this is counted as a direction in directed graph.
dg.addEdge('v1', 'v3');
dg.removeEdges('v1'); // 3

const g = new Graph();
g.addVertex('v1');
g.addVertex('v2');
g.addVertex('v3');
g.addEdge('v1', 'v2');
g.addEdge('v1', 'v3');
g.removeEdges('v1'); // 2

.traverseDfs(srcKey, cb)

traverses the graph using the depth-first recursive search.

params
name	type	description
srcKey	number or string	the starting vertex key
cb	function	the callback that is called with each vertex

runtime
O(V) : V = the number of vertices in the graph

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.

params
name	type	description
srcKey	number or string	the starting vertex key
cb	function	the callback that is called with each vertex

runtime
O(V) : V = the number of vertices in the graph

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

Vertex

.getKey()

returns the vertex key.

return
string or number

.getValue()

returns the vertex associated value.

return
object

Build

grunt build

License

The MIT License. Full License is here

Changelog

[v4.0.0] - 2020-04-08

Added

.removeEdges(key) to remove all conncted edges in graph (directions in directed graph) from a vertex.

Changed

• .removeEdge & .removeVertex now return a boolean to indicated if something was removed.
• .addVertex now returns the addded vertex.

Removed

• vertex none standard function .serialize.

Fixed

• README
• jsdoc