Research
Security News
Malicious npm Package Targets Solana Developers and Hijacks Funds
A malicious npm package targets Solana developers, rerouting funds in 2% of transactions to a hardcoded address.
js-graph-algorithms
Advanced tools
Package implements data structures and algorithms for processing various types of graphs
Package provides javascript implementation of algorithms for graph processing
npm install js-graph-algorithms
The sample code below shows how to create a undirected and unweighted graph (Link: HTML DEMO):
var jsgraphs = require('js-graph-algorithms');
var g = new jsgraphs.Graph(6); // 6 is the number vertices in the graph
g.addEdge(0, 5); // add undirected edge connecting vertex 0 to vertex 5
g.addEdge(2, 4);
g.addEdge(2, 3);
g.addEdge(1, 2);
g.addEdge(0, 1);
g.addEdge(3, 4);
g.addEdge(3, 5);
g.addEdge(0, 2);
g.node(2).label = 'Hello'; // assigned 'Hello' as label for node 2
g.edge(0, 2).label = 'World'; // edge between 0 and 2
console.log(g.V); // display 6, which is the number of vertices in g
console.log(g.adj(0)); // display [5, 1, 2], which is the adjacent list to vertex 0
The sample code below shows how to create a direted and unweighted graph (Link: HTML DEMO):
var jsgraphs = require('js-graph-algorithms');
var g = new jsgraphs.DiGraph(13); // 13 is the number vertices in the graph
g.addEdge(4, 2); // add directed edge from 4 to 2
g.addEdge(2, 3);
g.addEdge(3, 2);
g.addEdge(6, 0);
g.addEdge(0, 1);
g.addEdge(2, 0);
g.addEdge(11, 12);
g.addEdge(12, 9);
g.addEdge(9, 10);
g.addEdge(9, 11);
g.addEdge(7, 9);
g.addEdge(10, 12);
g.addEdge(11, 4);
g.addEdge(4, 3);
g.addEdge(3, 5);
g.addEdge(6, 8);
g.addEdge(8, 6);
g.addEdge(5, 4);
g.addEdge(0, 5);
g.addEdge(6, 4);
g.addEdge(6, 9);
g.addEdge(7, 6);
g.node(2).label = 'Hello'; // assign 'Hello' as label for node 2
g.edge(0, 5).label = 'World'; // edge from 0 to 5
console.log(g.V); // display 13, which is the number of vertices in g
console.log(g.adj(0)); // display the adjacency list which are vertices directed from vertex 0
The sample code below shows show to create undirected weighted graph (Link: HTML DEMO):
var jsgraphs = require('js-graph-algorithms');
var g = new jsgraphs.WeightedGraph(8); // 8 is the number vertices in the graph
g.addEdge(new jsgraphs.Edge(0, 7, 0.16));
g.addEdge(new jsgraphs.Edge(2, 3, 0.17));
g.addEdge(new jsgraphs.Edge(1, 7, 0.19));
g.addEdge(new jsgraphs.Edge(0, 2, 0.26));
g.addEdge(new jsgraphs.Edge(5, 7, 0.28));
g.addEdge(new jsgraphs.Edge(1, 3, 0.29));
g.addEdge(new jsgraphs.Edge(1, 5, 0.32));
g.addEdge(new jsgraphs.Edge(2, 7, 0.34));
g.addEdge(new jsgraphs.Edge(4, 5, 0.35));
g.addEdge(new jsgraphs.Edge(1, 2, 0.36));
g.addEdge(new jsgraphs.Edge(4, 7, 0.37));
g.addEdge(new jsgraphs.Edge(0, 4, 0.38));
g.addEdge(new jsgraphs.Edge(6, 2, 0.4));
g.addEdge(new jsgraphs.Edge(3, 6, 0.52));
g.addEdge(new jsgraphs.Edge(6, 0, 0.58));
g.addEdge(new jsgraphs.Edge(6, 4, 0.93));
g.node(2).label = 'Hello'; // assign 'Hello' as label for node 2
g.edge(4, 5).label = 'World'; // edge between node 4 and 5
console.log(g.V); // display 13, which is the number of vertices in g
console.log(g.adj(0)); // display the adjacency list which are undirected edges connected to vertex 0
The sample code below shows show to create directed weighted graph (Link: HTML DEMO):
var jsgraphs = require('js-graph-algorithms');
var g = new jsgraphs.WeightedDiGraph(8); // 8 is the number vertices in the graph
g.addEdge(new jsgraphs.Edge(0, 7, 0.16));
g.addEdge(new jsgraphs.Edge(2, 3, 0.17));
g.addEdge(new jsgraphs.Edge(1, 7, 0.19));
g.addEdge(new jsgraphs.Edge(0, 2, 0.26));
g.addEdge(new jsgraphs.Edge(5, 7, 0.28));
g.addEdge(new jsgraphs.Edge(1, 3, 0.29));
g.addEdge(new jsgraphs.Edge(1, 5, 0.32));
g.addEdge(new jsgraphs.Edge(2, 7, 0.34));
g.addEdge(new jsgraphs.Edge(4, 5, 0.35));
g.addEdge(new jsgraphs.Edge(1, 2, 0.36));
g.addEdge(new jsgraphs.Edge(4, 7, 0.37));
g.addEdge(new jsgraphs.Edge(0, 4, 0.38));
g.addEdge(new jsgraphs.Edge(6, 2, 0.4));
g.addEdge(new jsgraphs.Edge(3, 6, 0.52));
g.addEdge(new jsgraphs.Edge(6, 0, 0.58));
g.addEdge(new jsgraphs.Edge(6, 4, 0.93));
g.node(2).label = 'Hello';
g.edge(4, 5).label = 'World'; // edge from node 4 to node 5
console.log(g.V); // display 13, which is the number of vertices in g
console.log(g.adj(0)); // display the adjacency list which are directed edges from vertex 0
The sample code below show how to perform depth first search of an undirected graph (Link: HTML DEMO):
var jsgraphs = require('js-graph-algorithms');
var g = new jsgraphs.Graph(6);
g.addEdge(0, 5);
g.addEdge(2, 4);
g.addEdge(2, 3);
g.addEdge(1, 2);
g.addEdge(0, 1);
g.addEdge(3, 4);
g.addEdge(3, 5);
g.addEdge(0, 2);
var s = 0;
var dfs = new jsgraphs.DepthFirstSearch(g, s);
for(var v=0; v < g.V; ++v) {
if(dfs.hasPathTo(v)) {
console.log(s + " is connected to " + v);
console.log("path: " + dfs.pathTo(v));
} else {
console.log('No path from ' + s + ' to ' + v);
}
}
The sample code below show how to obtain the number of connected components in an undirected graph (Link: HTML DEMO):
var jsgraphs = require('js-graph-algorithms');
var g = new jsgraphs.Graph(13);
g.addEdge(0, 5);
g.addEdge(4, 3);
g.addEdge(0, 1);
g.addEdge(9, 12);
g.addEdge(6, 4);
g.addEdge(5, 4);
g.addEdge(0, 2);
g.addEdge(11, 12);
g.addEdge(9,10);
g.addEdge(0, 6);
g.addEdge(7, 8);
g.addEdge(9, 11);
g.addEdge(5, 3);
var cc = new jsgraphs.ConnectedComponents(g);
console.log(cc.componentCount()); // display 3
for (var v = 0; v < g.V; ++v) {
console.log('id[' + v + ']: ' + cc.componentId(v));
}
The sample code below show how to obtain the reverse post order of a topological sort in a directed acyclic graph (Link: HTML DEMO):
var jsgraphs = require('js-graph-algorithms');
var dag = new jsgraphs.DiGraph(7); // must be directed acyclic graph
dag.addEdge(0, 5);
dag.addEdge(0, 2);
dag.addEdge(0, 1);
dag.addEdge(3, 6);
dag.addEdge(3, 5);
dag.addEdge(3, 4);
dag.addEdge(5, 4);
dag.addEdge(6, 4);
dag.addEdge(6, 0);
dag.addEdge(3, 2);
dag.addEdge(1, 4);
var ts = new jsgraphs.TopologicalSort(dag);
var order = ts.order();
console.log(order); // display array which is the topological sort order
The sample code below show how to obtain the strongly connected components from a directed graph (Link: HTML DEMO):
var jsgraphs = require('js-graph-algorithms');
var graph = new jsgraphs.DiGraph(13);
graph.addEdge(4, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 2);
graph.addEdge(6, 0);
graph.addEdge(0, 1);
graph.addEdge(2, 0);
graph.addEdge(11, 12);
graph.addEdge(12, 9);
graph.addEdge(9, 10);
graph.addEdge(9, 11);
graph.addEdge(8, 9);
graph.addEdge(10, 12);
graph.addEdge(11, 4);
graph.addEdge(4, 3);
graph.addEdge(3, 5);
graph.addEdge(7, 8);
graph.addEdge(8, 7);
graph.addEdge(5, 4);
graph.addEdge(0, 5);
graph.addEdge(6, 4);
graph.addEdge(6, 9);
graph.addEdge(7, 6);
var scc = new jsgraphs.StronglyConnectedComponents(graph);
console.log(scc.componentCount()); // display 5
for (var v = 0; v < graph.V; ++v) {
console.log('id[' + v + ']: ' + scc.componentId(v));
}
The sample code below show how to obtain the minimum spanning tree from a weighted graph using Kruskal algorithm (Link: HTML DEMO):
var jsgraphs = require('js-graph-algorithms');
var g = new jsgraphs.WeightedGraph(8);
g.addEdge(new jsgraphs.Edge(0, 7, 0.16));
g.addEdge(new jsgraphs.Edge(2, 3, 0.17));
g.addEdge(new jsgraphs.Edge(1, 7, 0.19));
g.addEdge(new jsgraphs.Edge(0, 2, 0.26));
g.addEdge(new jsgraphs.Edge(5, 7, 0.28));
g.addEdge(new jsgraphs.Edge(1, 3, 0.29));
g.addEdge(new jsgraphs.Edge(1, 5, 0.32));
g.addEdge(new jsgraphs.Edge(2, 7, 0.34));
g.addEdge(new jsgraphs.Edge(4, 5, 0.35));
g.addEdge(new jsgraphs.Edge(1, 2, 0.36));
g.addEdge(new jsgraphs.Edge(4, 7, 0.37));
g.addEdge(new jsgraphs.Edge(0, 4, 0.38));
g.addEdge(new jsgraphs.Edge(6, 2, 0.4));
g.addEdge(new jsgraphs.Edge(3, 6, 0.52));
g.addEdge(new jsgraphs.Edge(6, 0, 0.58));
g.addEdge(new jsgraphs.Edge(6, 4, 0.93));
var kruskal = new jsgraphs.KruskalMST(g);
var mst = kruskal.mst;
for(var i=0; i < mst.length; ++i) {
var e = mst[i];
var v = e.either();
var w = e.other(v);
console.log('(' + v + ', ' + w + '): ' + e.weight);
}
The sample code below show how to obtain the minimum spanning tree from a weighted graph using Lazy Prim algorithm (Link: HTML DEMO):
var jsgraphs = require('js-graph-algorithms');
var g = new jsgraphs.WeightedGraph(8);
g.addEdge(new jsgraphs.Edge(0, 7, 0.16));
g.addEdge(new jsgraphs.Edge(2, 3, 0.17));
g.addEdge(new jsgraphs.Edge(1, 7, 0.19));
g.addEdge(new jsgraphs.Edge(0, 2, 0.26));
g.addEdge(new jsgraphs.Edge(5, 7, 0.28));
g.addEdge(new jsgraphs.Edge(1, 3, 0.29));
g.addEdge(new jsgraphs.Edge(1, 5, 0.32));
g.addEdge(new jsgraphs.Edge(2, 7, 0.34));
g.addEdge(new jsgraphs.Edge(4, 5, 0.35));
g.addEdge(new jsgraphs.Edge(1, 2, 0.36));
g.addEdge(new jsgraphs.Edge(4, 7, 0.37));
g.addEdge(new jsgraphs.Edge(0, 4, 0.38));
g.addEdge(new jsgraphs.Edge(6, 2, 0.4));
g.addEdge(new jsgraphs.Edge(3, 6, 0.52));
g.addEdge(new jsgraphs.Edge(6, 0, 0.58));
g.addEdge(new jsgraphs.Edge(6, 4, 0.93));
var prim = new jsgraphs.LazyPrimMST(g);
var mst = prim.mst;
for(var i=0; i < mst.length; ++i) {
var e = mst[i];
var v = e.either();
var w = e.other(v);
console.log('(' + v + ', ' + w + '): ' + e.weight);
}
The sample code below show how to obtain the minimum spanning tree from a weighted graph using Eager Prim algorithm (Link: HTML DEMO):
var jsgraphs = require('js-graph-algorithms');
var g = new jsgraphs.WeightedGraph(8);
g.addEdge(new jsgraphs.Edge(0, 7, 0.16));
g.addEdge(new jsgraphs.Edge(2, 3, 0.17));
g.addEdge(new jsgraphs.Edge(1, 7, 0.19));
g.addEdge(new jsgraphs.Edge(0, 2, 0.26));
g.addEdge(new jsgraphs.Edge(5, 7, 0.28));
g.addEdge(new jsgraphs.Edge(1, 3, 0.29));
g.addEdge(new jsgraphs.Edge(1, 5, 0.32));
g.addEdge(new jsgraphs.Edge(2, 7, 0.34));
g.addEdge(new jsgraphs.Edge(4, 5, 0.35));
g.addEdge(new jsgraphs.Edge(1, 2, 0.36));
g.addEdge(new jsgraphs.Edge(4, 7, 0.37));
g.addEdge(new jsgraphs.Edge(0, 4, 0.38));
g.addEdge(new jsgraphs.Edge(6, 2, 0.4));
g.addEdge(new jsgraphs.Edge(3, 6, 0.52));
g.addEdge(new jsgraphs.Edge(6, 0, 0.58));
g.addEdge(new jsgraphs.Edge(6, 4, 0.93));
var prim = new jsgraphs.EagerPrimMST(g);
var mst = prim.mst;
for(var i=0; i < mst.length; ++i) {
var e = mst[i];
var v = e.either();
var w = e.other(v);
console.log('(' + v + ', ' + w + '): ' + e.weight);
}
The sample code below show how to obtain the shortest paths from a starting point 0 on a weighted directed graph using Dijkstra (Link: HTML DEMO):
var jsgraphs = require('js-graph-algorithms');
var g = new jsgraphs.WeightedDiGraph(8);
g.addEdge(new jsgraphs.Edge(0, 1, 5.0));
g.addEdge(new jsgraphs.Edge(0, 4, 9.0));
g.addEdge(new jsgraphs.Edge(0, 7, 8.0));
g.addEdge(new jsgraphs.Edge(1, 2, 12.0));
g.addEdge(new jsgraphs.Edge(1, 3, 15.0));
g.addEdge(new jsgraphs.Edge(1, 7, 4.0));
g.addEdge(new jsgraphs.Edge(2, 3, 3.0));
g.addEdge(new jsgraphs.Edge(2, 6, 11.0));
g.addEdge(new jsgraphs.Edge(3, 6, 9.0));
g.addEdge(new jsgraphs.Edge(4, 5, 5.0));
g.addEdge(new jsgraphs.Edge(4, 6, 20.0));
g.addEdge(new jsgraphs.Edge(4, 7, 5.0));
g.addEdge(new jsgraphs.Edge(5, 2, 1.0));
g.addEdge(new jsgraphs.Edge(5, 6, 13.0));
g.addEdge(new jsgraphs.Edge(7, 5, 6.0));
g.addEdge(new jsgraphs.Edge(7, 2, 7.0));
var dijkstra = new jsgraphs.Dijkstra(g, 0);
for(var v = 1; v < g.V; ++v){
if(dijkstra.hasPathTo(v)){
var path = dijkstra.pathTo(v);
console.log('=====path from 0 to ' + v + ' start==========');
for(var i = 0; i < path.length; ++i) {
var e = path[i];
console.log(e.from() + ' => ' + e.to() + ': ' + e.weight);
}
console.log('=====path from 0 to ' + v + ' end==========');
console.log('=====distance: ' + dijkstra.distanceTo(v) + '=========');
}
}
The sample code below show how to obtain the shortest paths from a starting point 0 on a weighted directed graph using Bellman-Ford:
var jsgraphs = require('js-graph-algorithms');
var g = new jsgraphs.WeightedDiGraph(8);
g.addEdge(new jsgraphs.Edge(0, 1, 5.0));
g.addEdge(new jsgraphs.Edge(0, 4, 9.0));
g.addEdge(new jsgraphs.Edge(0, 7, 8.0));
g.addEdge(new jsgraphs.Edge(1, 2, 12.0));
g.addEdge(new jsgraphs.Edge(1, 3, 15.0));
g.addEdge(new jsgraphs.Edge(1, 7, 4.0));
g.addEdge(new jsgraphs.Edge(2, 3, 3.0));
g.addEdge(new jsgraphs.Edge(2, 6, 11.0));
g.addEdge(new jsgraphs.Edge(3, 6, 9.0));
g.addEdge(new jsgraphs.Edge(4, 5, 5.0));
g.addEdge(new jsgraphs.Edge(4, 6, 20.0));
g.addEdge(new jsgraphs.Edge(4, 7, 5.0));
g.addEdge(new jsgraphs.Edge(5, 2, 1.0));
g.addEdge(new jsgraphs.Edge(5, 6, 13.0));
g.addEdge(new jsgraphs.Edge(7, 5, 6.0));
g.addEdge(new jsgraphs.Edge(7, 2, 7.0));
var bf = new jsgraphs.BellmanFord(g, 0);
for(var v = 1; v < g.V; ++v){
if(bf.hasPathTo(v)){
var path = bf.pathTo(v);
console.log('=====path from 0 to ' + v + ' start==========');
for(var i = 0; i < path.length; ++i) {
var e = path[i];
console.log(e.from() + ' => ' + e.to() + ': ' + e.weight);
}
console.log('=====path from 0 to ' + v + ' end==========');
console.log('=====distance: ' + bf.distanceTo(v) + '=========');
}
}
The sample code below show how to obtain the shortest paths from a starting point 0 on a weighted directed acylic graph using Topological Sort:
var jsgraphs = require('js-graph-algorithms');
var g = new jsgraphs.WeightedDiGraph(8);
g.addEdge(new jsgraphs.Edge(0, 1, 5.0));
g.addEdge(new jsgraphs.Edge(0, 4, 9.0));
g.addEdge(new jsgraphs.Edge(0, 7, 8.0));
g.addEdge(new jsgraphs.Edge(1, 2, 12.0));
g.addEdge(new jsgraphs.Edge(1, 3, 15.0));
g.addEdge(new jsgraphs.Edge(1, 7, 4.0));
g.addEdge(new jsgraphs.Edge(2, 3, 3.0));
g.addEdge(new jsgraphs.Edge(2, 6, 11.0));
g.addEdge(new jsgraphs.Edge(3, 6, 9.0));
g.addEdge(new jsgraphs.Edge(4, 5, 5.0));
g.addEdge(new jsgraphs.Edge(4, 6, 20.0));
g.addEdge(new jsgraphs.Edge(4, 7, 5.0));
g.addEdge(new jsgraphs.Edge(5, 2, 1.0));
g.addEdge(new jsgraphs.Edge(5, 6, 13.0));
g.addEdge(new jsgraphs.Edge(7, 5, 6.0));
g.addEdge(new jsgraphs.Edge(7, 2, 7.0));
var bf = new jsgraphs.TopologicalSortShortestPaths(g, 0);
for(var v = 1; v < g.V; ++v){
if(bf.hasPathTo(v)){
var path = bf.pathTo(v);
console.log('=====path from 0 to ' + v + ' start==========');
for(var i = 0; i < path.length; ++i) {
var e = path[i];
console.log(e.from() + ' => ' + e.to() + ': ' + e.weight);
}
console.log('=====path from 0 to ' + v + ' end==========');
console.log('=====distance: ' + bf.distanceTo(v) + '=========');
}
}
The sample code below show how to obtain the MaxFlow-MinCut of a directed weighted graph using ford-fulkerson algorithm (Link: HTML DEMO):
var jsgraphs = require('js-graph-algorithms');
var g = new jsgraphs.FlowNetwork(8);
g.addEdge(new jsgraphs.FlowEdge(0, 1, 10));
g.addEdge(new jsgraphs.FlowEdge(0, 2, 5));
g.addEdge(new jsgraphs.FlowEdge(0, 3, 15));
g.addEdge(new jsgraphs.FlowEdge(1, 4, 9));
g.addEdge(new jsgraphs.FlowEdge(1, 5, 15));
g.addEdge(new jsgraphs.FlowEdge(1, 2, 4));
g.addEdge(new jsgraphs.FlowEdge(2, 5, 8));
g.addEdge(new jsgraphs.FlowEdge(2, 3, 4));
g.addEdge(new jsgraphs.FlowEdge(3, 6, 16));
g.addEdge(new jsgraphs.FlowEdge(4, 5, 15));
g.addEdge(new jsgraphs.FlowEdge(4, 7, 10));
g.addEdge(new jsgraphs.FlowEdge(5, 7, 10));
g.addEdge(new jsgraphs.FlowEdge(5, 6, 15));
g.addEdge(new jsgraphs.FlowEdge(6, 2, 6));
g.addEdge(new jsgraphs.FlowEdge(6, 7, 10));
g.node(2).label = 'Hello';
g.edge(0, 1).label = 'World';
var source = 0;
var target = 7;
var ff = new jsgraphs.FordFulkerson(g, source, target);
console.log('max-flow: ' + ff.value);
var minCut = ff.minCut(g);
for(var i = 0; i < minCut.length; ++i) {
var e = minCut[i];
console.log('min-cut: (' + e.from() + ", " + e.to() + ')');
}
FAQs
Package implements data structures and algorithms for processing various types of graphs
The npm package js-graph-algorithms receives a total of 35,290 weekly downloads. As such, js-graph-algorithms popularity was classified as popular.
We found that js-graph-algorithms 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.
Research
Security News
A malicious npm package targets Solana developers, rerouting funds in 2% of transactions to a hardcoded address.
Security News
Research
Socket researchers have discovered malicious npm packages targeting crypto developers, stealing credentials and wallet data using spyware delivered through typosquats of popular cryptographic libraries.
Security News
Socket's package search now displays weekly downloads for npm packages, helping developers quickly assess popularity and make more informed decisions.