graph.js's Introduction

graph.js

A liteweight javascript graph algorithms library.

Algorithms implemented so far

BFS/DFS
Dijkstra for shortest path
Bellman- Ford for shortest path ( Negative Cycle checking )
Johnson's for all pair shortest paths
Prim's Algorithm for minimum spanning tree of Undirected complete graph

To do Algorithms

Kruskal
Max Flow
Centrality
A * Search
DAG shortest path
Connected Components

How to contribute

Fork the repo and implement the algorithms in to do list.
If you find any bug just open an issue.
You can always contact me at @devenbhooshan on twitter.

How to use

Build the library by typing make from the root directory of graph.js.
A file named graph.js would be created in the folder build/
Done (ya!!!)
Sample code can be found in test folder

Initialization

graph =new Graph(); // creates a graph
node1=graph.AddNode("India"); // creates a node
node2=graph.AddNode("Delhi"); // creates a node
node1.addEdge(node2);         // Adds an edge between node1 & node2
console.log(node1.adjList);   // returns all neighbouring nodes of nod1
console.log(node2.adjList);   // returns all neighbouring nodes of nod2
console.log(graph.nodes.length); // returns number of nodes in graph

Traversal

var bfsTraversedNodes=bfs(graph); // returns a bfs traversal of graph
var dfsTraversedNodes=dfs(graph); // returns a dfs traversal of graph

Shortest Distance beween two nodes

dijkstra(graph,sourceNode,destinationNode); // returns shortest distance between source and destination nodes
bellman_ford(graph,node1,node6); // This function returns null if there exist negative cycle in the graph otherwise it gives the shortest distance between node1 and node6

Recommend Projects