Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Package provides javascript implementation of algorithms for graph processing

License

NotificationsYou must be signed in to change notification settings

chen0040/js-graph-algorithms

Repository files navigation

Package provides javascript implementation of algorithms for graph processing

Build StatusCoverage Status

Features

  • 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)

Install

npm install js-graph-algorithms

Usage

Create an undirected unweighted graph

The sample code below shows how to create a undirected and unweighted graph (Link:HTML DEMO):

varjsgraphs=require('js-graph-algorithms');varg=newjsgraphs.Graph(6);// 6 is the number vertices in the graphg.addEdge(0,5);// add undirected edge connecting vertex 0 to vertex 5g.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 2g.edge(0,2).label='World';// edge between 0 and 2console.log(g.V);// display 6, which is the number of vertices in gconsole.log(g.adj(0));// display [5, 1, 2], which is the adjacent list to vertex 0

Create directed unweighted graph

The sample code below shows how to create a direted and unweighted graph (Link:HTML DEMO):

varjsgraphs=require('js-graph-algorithms');varg=newjsgraphs.DiGraph(13);// 13 is the number vertices in the graphg.addEdge(4,2);// add directed edge from 4 to 2g.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 2g.edge(0,5).label='World';// edge from 0 to 5console.log(g.V);// display 13, which is the number of vertices in gconsole.log(g.adj(0));// display the adjacency list which are vertices directed from vertex 0

Create undirected weighted graph

The sample code below shows show to create undirected weighted graph (Link:HTML DEMO):

varjsgraphs=require('js-graph-algorithms');varg=newjsgraphs.WeightedGraph(8);// 8 is the number vertices in the graphg.addEdge(newjsgraphs.Edge(0,7,0.16));g.addEdge(newjsgraphs.Edge(2,3,0.17));g.addEdge(newjsgraphs.Edge(1,7,0.19));g.addEdge(newjsgraphs.Edge(0,2,0.26));g.addEdge(newjsgraphs.Edge(5,7,0.28));g.addEdge(newjsgraphs.Edge(1,3,0.29));g.addEdge(newjsgraphs.Edge(1,5,0.32));g.addEdge(newjsgraphs.Edge(2,7,0.34));g.addEdge(newjsgraphs.Edge(4,5,0.35));g.addEdge(newjsgraphs.Edge(1,2,0.36));g.addEdge(newjsgraphs.Edge(4,7,0.37));g.addEdge(newjsgraphs.Edge(0,4,0.38));g.addEdge(newjsgraphs.Edge(6,2,0.4));g.addEdge(newjsgraphs.Edge(3,6,0.52));g.addEdge(newjsgraphs.Edge(6,0,0.58));g.addEdge(newjsgraphs.Edge(6,4,0.93));g.node(2).label='Hello';// assign 'Hello' as label for node 2g.edge(4,5).label='World';// edge between node 4 and 5console.log(g.V);// display 13, which is the number of vertices in gconsole.log(g.adj(0));// display the adjacency list which are undirected edges connected to vertex 0

Create directed weighted graph

The sample code below shows show to create directed weighted graph (Link:HTML DEMO):

varjsgraphs=require('js-graph-algorithms');varg=newjsgraphs.WeightedDiGraph(8);// 8 is the number vertices in the graphg.addEdge(newjsgraphs.Edge(0,7,0.16));g.addEdge(newjsgraphs.Edge(2,3,0.17));g.addEdge(newjsgraphs.Edge(1,7,0.19));g.addEdge(newjsgraphs.Edge(0,2,0.26));g.addEdge(newjsgraphs.Edge(5,7,0.28));g.addEdge(newjsgraphs.Edge(1,3,0.29));g.addEdge(newjsgraphs.Edge(1,5,0.32));g.addEdge(newjsgraphs.Edge(2,7,0.34));g.addEdge(newjsgraphs.Edge(4,5,0.35));g.addEdge(newjsgraphs.Edge(1,2,0.36));g.addEdge(newjsgraphs.Edge(4,7,0.37));g.addEdge(newjsgraphs.Edge(0,4,0.38));g.addEdge(newjsgraphs.Edge(6,2,0.4));g.addEdge(newjsgraphs.Edge(3,6,0.52));g.addEdge(newjsgraphs.Edge(6,0,0.58));g.addEdge(newjsgraphs.Edge(6,4,0.93));g.node(2).label='Hello';g.edge(4,5).label='World';// edge from node 4 to node 5console.log(g.V);// display 13, which is the number of vertices in gconsole.log(g.adj(0));// display the adjacency list which are directed edges from vertex 0

Depth First Search

The sample code below show how to perform depth first search of an undirected graph (Link:HTML DEMO):

varjsgraphs=require('js-graph-algorithms');varg=newjsgraphs.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);vars=0;vardfs=newjsgraphs.DepthFirstSearch(g,s);for(varv=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);}}

Connected Components

The sample code below show how to obtain the number of connected components in an undirected graph (Link:HTML DEMO):

varjsgraphs=require('js-graph-algorithms');varg=newjsgraphs.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);varcc=newjsgraphs.ConnectedComponents(g);console.log(cc.componentCount());// display 3for(varv=0;v<g.V;++v){console.log('id['+v+']: '+cc.componentId(v));}

Topological Sort

The sample code below show how to obtain the reverse post order of a topological sort in a directed acyclic graph (Link:HTML DEMO):

varjsgraphs=require('js-graph-algorithms');vardag=newjsgraphs.DiGraph(7);// must be directed acyclic graphdag.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);varts=newjsgraphs.TopologicalSort(dag);varorder=ts.order();console.log(order);// display array which is the topological sort order

Strongly Connected Components for Directed Graph

The sample code below show how to obtain the strongly connected components from a directed graph (Link:HTML DEMO):

varjsgraphs=require('js-graph-algorithms');vargraph=newjsgraphs.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);varscc=newjsgraphs.StronglyConnectedComponents(graph);console.log(scc.componentCount());// display 5for(varv=0;v<graph.V;++v){console.log('id['+v+']: '+scc.componentId(v));}

Use Kruskal algorithm to find the minimum spanning tree of a weighted graph

The sample code below show how to obtain the minimum spanning tree from a weighted graph using Kruskal algorithm (Link:HTML DEMO):

varjsgraphs=require('js-graph-algorithms');varg=newjsgraphs.WeightedGraph(8);g.addEdge(newjsgraphs.Edge(0,7,0.16));g.addEdge(newjsgraphs.Edge(2,3,0.17));g.addEdge(newjsgraphs.Edge(1,7,0.19));g.addEdge(newjsgraphs.Edge(0,2,0.26));g.addEdge(newjsgraphs.Edge(5,7,0.28));g.addEdge(newjsgraphs.Edge(1,3,0.29));g.addEdge(newjsgraphs.Edge(1,5,0.32));g.addEdge(newjsgraphs.Edge(2,7,0.34));g.addEdge(newjsgraphs.Edge(4,5,0.35));g.addEdge(newjsgraphs.Edge(1,2,0.36));g.addEdge(newjsgraphs.Edge(4,7,0.37));g.addEdge(newjsgraphs.Edge(0,4,0.38));g.addEdge(newjsgraphs.Edge(6,2,0.4));g.addEdge(newjsgraphs.Edge(3,6,0.52));g.addEdge(newjsgraphs.Edge(6,0,0.58));g.addEdge(newjsgraphs.Edge(6,4,0.93));varkruskal=newjsgraphs.KruskalMST(g);varmst=kruskal.mst;for(vari=0;i<mst.length;++i){vare=mst[i];varv=e.either();varw=e.other(v);console.log('('+v+', '+w+'): '+e.weight);}

Use Lazy Prim algorithm to find the minimum spanning tree of a weighted graph

The sample code below show how to obtain the minimum spanning tree from a weighted graph using Lazy Prim algorithm (Link:HTML DEMO):

varjsgraphs=require('js-graph-algorithms');varg=newjsgraphs.WeightedGraph(8);g.addEdge(newjsgraphs.Edge(0,7,0.16));g.addEdge(newjsgraphs.Edge(2,3,0.17));g.addEdge(newjsgraphs.Edge(1,7,0.19));g.addEdge(newjsgraphs.Edge(0,2,0.26));g.addEdge(newjsgraphs.Edge(5,7,0.28));g.addEdge(newjsgraphs.Edge(1,3,0.29));g.addEdge(newjsgraphs.Edge(1,5,0.32));g.addEdge(newjsgraphs.Edge(2,7,0.34));g.addEdge(newjsgraphs.Edge(4,5,0.35));g.addEdge(newjsgraphs.Edge(1,2,0.36));g.addEdge(newjsgraphs.Edge(4,7,0.37));g.addEdge(newjsgraphs.Edge(0,4,0.38));g.addEdge(newjsgraphs.Edge(6,2,0.4));g.addEdge(newjsgraphs.Edge(3,6,0.52));g.addEdge(newjsgraphs.Edge(6,0,0.58));g.addEdge(newjsgraphs.Edge(6,4,0.93));varprim=newjsgraphs.LazyPrimMST(g);varmst=prim.mst;for(vari=0;i<mst.length;++i){vare=mst[i];varv=e.either();varw=e.other(v);console.log('('+v+', '+w+'): '+e.weight);}

Use Eager Prim algorithm to find the minimum spanning tree of a weighted graph

The sample code below show how to obtain the minimum spanning tree from a weighted graph using Eager Prim algorithm (Link:HTML DEMO):

varjsgraphs=require('js-graph-algorithms');varg=newjsgraphs.WeightedGraph(8);g.addEdge(newjsgraphs.Edge(0,7,0.16));g.addEdge(newjsgraphs.Edge(2,3,0.17));g.addEdge(newjsgraphs.Edge(1,7,0.19));g.addEdge(newjsgraphs.Edge(0,2,0.26));g.addEdge(newjsgraphs.Edge(5,7,0.28));g.addEdge(newjsgraphs.Edge(1,3,0.29));g.addEdge(newjsgraphs.Edge(1,5,0.32));g.addEdge(newjsgraphs.Edge(2,7,0.34));g.addEdge(newjsgraphs.Edge(4,5,0.35));g.addEdge(newjsgraphs.Edge(1,2,0.36));g.addEdge(newjsgraphs.Edge(4,7,0.37));g.addEdge(newjsgraphs.Edge(0,4,0.38));g.addEdge(newjsgraphs.Edge(6,2,0.4));g.addEdge(newjsgraphs.Edge(3,6,0.52));g.addEdge(newjsgraphs.Edge(6,0,0.58));g.addEdge(newjsgraphs.Edge(6,4,0.93));varprim=newjsgraphs.EagerPrimMST(g);varmst=prim.mst;for(vari=0;i<mst.length;++i){vare=mst[i];varv=e.either();varw=e.other(v);console.log('('+v+', '+w+'): '+e.weight);}

Find the shortest paths using Dijkstra

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):

varjsgraphs=require('js-graph-algorithms');varg=newjsgraphs.WeightedDiGraph(8);g.addEdge(newjsgraphs.Edge(0,1,5.0));g.addEdge(newjsgraphs.Edge(0,4,9.0));g.addEdge(newjsgraphs.Edge(0,7,8.0));g.addEdge(newjsgraphs.Edge(1,2,12.0));g.addEdge(newjsgraphs.Edge(1,3,15.0));g.addEdge(newjsgraphs.Edge(1,7,4.0));g.addEdge(newjsgraphs.Edge(2,3,3.0));g.addEdge(newjsgraphs.Edge(2,6,11.0));g.addEdge(newjsgraphs.Edge(3,6,9.0));g.addEdge(newjsgraphs.Edge(4,5,5.0));g.addEdge(newjsgraphs.Edge(4,6,20.0));g.addEdge(newjsgraphs.Edge(4,7,5.0));g.addEdge(newjsgraphs.Edge(5,2,1.0));g.addEdge(newjsgraphs.Edge(5,6,13.0));g.addEdge(newjsgraphs.Edge(7,5,6.0));g.addEdge(newjsgraphs.Edge(7,2,7.0));vardijkstra=newjsgraphs.Dijkstra(g,0);for(varv=1;v<g.V;++v){if(dijkstra.hasPathTo(v)){varpath=dijkstra.pathTo(v);console.log('=====path from 0 to '+v+' start==========');for(vari=0;i<path.length;++i){vare=path[i];console.log(e.from()+' => '+e.to()+': '+e.weight);}console.log('=====path from 0 to '+v+' end==========');console.log('=====distance: '+dijkstra.distanceTo(v)+'=========');}}

Find the shortest paths using Bellman-Ford

The sample code below show how to obtain the shortest paths from a starting point 0 on a weighted directed graph using Bellman-Ford:

varjsgraphs=require('js-graph-algorithms');varg=newjsgraphs.WeightedDiGraph(8);g.addEdge(newjsgraphs.Edge(0,1,5.0));g.addEdge(newjsgraphs.Edge(0,4,9.0));g.addEdge(newjsgraphs.Edge(0,7,8.0));g.addEdge(newjsgraphs.Edge(1,2,12.0));g.addEdge(newjsgraphs.Edge(1,3,15.0));g.addEdge(newjsgraphs.Edge(1,7,4.0));g.addEdge(newjsgraphs.Edge(2,3,3.0));g.addEdge(newjsgraphs.Edge(2,6,11.0));g.addEdge(newjsgraphs.Edge(3,6,9.0));g.addEdge(newjsgraphs.Edge(4,5,5.0));g.addEdge(newjsgraphs.Edge(4,6,20.0));g.addEdge(newjsgraphs.Edge(4,7,5.0));g.addEdge(newjsgraphs.Edge(5,2,1.0));g.addEdge(newjsgraphs.Edge(5,6,13.0));g.addEdge(newjsgraphs.Edge(7,5,6.0));g.addEdge(newjsgraphs.Edge(7,2,7.0));varbf=newjsgraphs.BellmanFord(g,0);for(varv=1;v<g.V;++v){if(bf.hasPathTo(v)){varpath=bf.pathTo(v);console.log('=====path from 0 to '+v+' start==========');for(vari=0;i<path.length;++i){vare=path[i];console.log(e.from()+' => '+e.to()+': '+e.weight);}console.log('=====path from 0 to '+v+' end==========');console.log('=====distance: '+bf.distanceTo(v)+'=========');}}

Find the shortest paths using Topological Sort Shortest Paths

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:

varjsgraphs=require('js-graph-algorithms');varg=newjsgraphs.WeightedDiGraph(8);g.addEdge(newjsgraphs.Edge(0,1,5.0));g.addEdge(newjsgraphs.Edge(0,4,9.0));g.addEdge(newjsgraphs.Edge(0,7,8.0));g.addEdge(newjsgraphs.Edge(1,2,12.0));g.addEdge(newjsgraphs.Edge(1,3,15.0));g.addEdge(newjsgraphs.Edge(1,7,4.0));g.addEdge(newjsgraphs.Edge(2,3,3.0));g.addEdge(newjsgraphs.Edge(2,6,11.0));g.addEdge(newjsgraphs.Edge(3,6,9.0));g.addEdge(newjsgraphs.Edge(4,5,5.0));g.addEdge(newjsgraphs.Edge(4,6,20.0));g.addEdge(newjsgraphs.Edge(4,7,5.0));g.addEdge(newjsgraphs.Edge(5,2,1.0));g.addEdge(newjsgraphs.Edge(5,6,13.0));g.addEdge(newjsgraphs.Edge(7,5,6.0));g.addEdge(newjsgraphs.Edge(7,2,7.0));varbf=newjsgraphs.TopologicalSortShortestPaths(g,0);for(varv=1;v<g.V;++v){if(bf.hasPathTo(v)){varpath=bf.pathTo(v);console.log('=====path from 0 to '+v+' start==========');for(vari=0;i<path.length;++i){vare=path[i];console.log(e.from()+' => '+e.to()+': '+e.weight);}console.log('=====path from 0 to '+v+' end==========');console.log('=====distance: '+bf.distanceTo(v)+'=========');}}

Find the MaxFlow-MinCut using Ford-Fulkerson algorithm

The sample code below show how to obtain the MaxFlow-MinCut of a directed weighted graph using ford-fulkerson algorithm (Link:HTML DEMO):

varjsgraphs=require('js-graph-algorithms');varg=newjsgraphs.FlowNetwork(8);g.addEdge(newjsgraphs.FlowEdge(0,1,10));g.addEdge(newjsgraphs.FlowEdge(0,2,5));g.addEdge(newjsgraphs.FlowEdge(0,3,15));g.addEdge(newjsgraphs.FlowEdge(1,4,9));g.addEdge(newjsgraphs.FlowEdge(1,5,15));g.addEdge(newjsgraphs.FlowEdge(1,2,4));g.addEdge(newjsgraphs.FlowEdge(2,5,8));g.addEdge(newjsgraphs.FlowEdge(2,3,4));g.addEdge(newjsgraphs.FlowEdge(3,6,16));g.addEdge(newjsgraphs.FlowEdge(4,5,15));g.addEdge(newjsgraphs.FlowEdge(4,7,10));g.addEdge(newjsgraphs.FlowEdge(5,7,10));g.addEdge(newjsgraphs.FlowEdge(5,6,15));g.addEdge(newjsgraphs.FlowEdge(6,2,6));g.addEdge(newjsgraphs.FlowEdge(6,7,10));g.node(2).label='Hello';g.edge(0,1).label='World';varsource=0;vartarget=7;varff=newjsgraphs.FordFulkerson(g,source,target);console.log('max-flow: '+ff.value);varminCut=ff.minCut(g);for(vari=0;i<minCut.length;++i){vare=minCut[i];console.log('min-cut: ('+e.from()+", "+e.to()+')');}
[8]ページ先頭
©2009-2025 Movatter.jp