Package Exports

@datastructures-js/graph

This package does not declare an exports field, so the exports above have been automatically detected and optimized by JSPM instead. If any package subpath is missing, it is recommended to post an issue to the original package (@datastructures-js/graph) to support the "exports" field. If that is not possible, create a JSPM override to customize the exports field for this package.

Readme

@datastructures-js/graph

graph

Install
API
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	key: {number} or {string} the vertex 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.

Eample

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.

Eample

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