Package Exports

@datastructures-js/graph
@datastructures-js/graph/index.js

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 & Directed Graph implementation in javascript.

Install
require
import
API
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