@datastructures-js/graph
Advanced tools
Graph & Directed Graph implementation in javascript.
npm install --save @datastructures-js/graph
const { Graph, DirectedGraph } = require('@datastructures-js/graph');
import { Graph, DirectedGraph } from '@datastructures-js/graph';
Creates a new graph
const directedGraph = new DirectedGraph();
const graph = new Graph();
// 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>();
Adds a vertex to the graph.
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);
Checks if the graph has a vertex by its key.
console.log(directedGraph.hasVertex('v7')); // false
console.log(graph.hasVertex('v1')); // true
Returns the value associated with a vertex key.
console.log(directedGraph.getVertexValue('v5')); // 5
console.log(graph.getVertexValue('v1')); // true
Gets the number of vertices in the graph.
console.log(directedGraph.getVerticesCount()); // 5
console.log(graph.getVerticesCount()); // 5
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.
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);
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.
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
Gets the number of edges in the graph.
console.log(directedGraph.getEdgesCount()); // 7
console.log(graph.getEdgesCount()); // 7
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.
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
Returns a list of keys of vertices connected to a given vertex.
console.log(directedGraph.getConnectedVertices('v4')); // ['v3', 'v5']
console.log(graph.getConnectedVertices('v1')); // ['v2', 'v3']
Returns an object of keys of vertices connected to a given vertex with the edges weight.
console.log(directedGraph.getConnectedEdges('v4')); // { v3: 1, v5: 4 }
console.log(graph.getConnectedEdges('v1')); // { v2: 2, v3: 6 }
Removes a vertex with all its edges from 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
Removes an edge between two existing vertices
directedGraph.removeEdge('v1', 'v3'); // true
console.log(directedGraph.getEdgesCount()); // 4
graph.removeEdge('v2', 'v3'); // true
console.log(graph.getEdgesCount()); // 4
Removes all connected edges to a vertex and returns the number of removed edges.
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
Traverses the graph from a starting vertex using the depth-first recursive search. it also accepts an optional third param as a callback to abort traversal when it returns true.
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
*/
let counter = 0;
graph.traverseDfs('v1', (key, value) => {
console.log(`${key}: ${value}`);
counter += 1;
}, () => counter > 1);
/*
v1: true
v2: true
*/
Traverses the graph from a starting vertex using the breadth-first search with a queue. it also accepts an optional third param as a callback to abort traversal when it returns true.
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
*/
let counter = 0;
graph.traverseBfs('v1', (key, value) => {
console.log(`${key}: ${value}`);
counter += 1;
}, () => counter > 1);
/*
v1: true
v2: true
*/
Clears all vertices and edges in the graph.
directedGraph.clear();
console.log(directedGraph.getVerticesCount()); // 0
console.log(directedGraph.getEdgesCount()); // 0
graph.clear();
console.log(graph.getVerticesCount()); // 0
console.log(graph.getEdgesCount()); // 0
grunt build
The MIT License. Full License is here
[v5.3.0] - 2022-11-07
getVertexValue(key) returns vertex value.FAQs
graph & directed graph implementation in javascript
The npm package @datastructures-js/graph receives a total of 5,826 weekly downloads. As such, @datastructures-js/graph popularity was classified as popular.
We found that @datastructures-js/graph demonstrated a not healthy version release cadence and project activity because the last version was released a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
Research
The Socket Research Team breaks down a malicious wrapper package that uses obfuscation to harvest credentials and exfiltrate sensitive data.
Research
Security News
Attackers used a malicious npm package typosquatting a popular ESLint plugin to steal sensitive data, execute commands, and exploit developer systems.
Security News
The Ultralytics' PyPI Package was compromised four times in one weekend through GitHub Actions cache poisoning and failure to rotate previously compromised API tokens.