Package implements data structures and algorithms for processing various types of graphs
npm install js-graph-algorithms 
* Depth First Search (Link: HTML DEMO)
* Breadth First Search
* Connected Components for undirected graph (Link: HTML DEMO)
* Topoloical Sort (Link: HTML DEMO)
* Strongly Connected Components for directed graph (Link: HTML DEMO)
* Minimum Spanning Tree for weighted graph (Kruskal, Prim Lazy, Prim Eager) (Link: HTML DEMO)
* Shortest Paths (Dijkstra, Bellman-Ford, Topological Sort on DAG) (Link: HTML DEMO)
* MaxFlow-MinCut (Ford-Fulkerson) (Link: HTML DEMO)
``bash`
npm install js-graph-algorithms
The sample code below shows how to create a undirected and unweighted graph (Link: HTML DEMO):
`javascript
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):
`javascript
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):
`javascript
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):
`javascript
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):
`javascript
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):
`javascript
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):
`javascript
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):
`javascript
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):
`javascript
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):
`javascript
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):
`javascript
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):
`javascript
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:
`javascript
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:
`javascript
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):
`javascript
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() + ')');
}
``