graph-dijkstra

A simple undirected graph that allows for finding the shortest path between nodes via Dijkstra's algorithm. This portable package can easily be wrapper into an angular service (as seen in our demo).

Developed for use in our Office Employee Locator application.

Version: 1.2.0

Installation & Typical Usage

1. Install via npm
   • $ npm install --save-dev https://github.com/LincolnTechOpenSource/graph-dijkstra
2. Include the JavaScript file
   • <link rel="stylesheet" href="node_modules/graph-dijkstra/dist/graph-dijkstra.js">
   • or <link rel="stylesheet" href="node_modules/graph-dijkstra/dist/graph-dijkstra.min.js">
3. Use the available API - for example:

   var graph = new Graph();
   graph.addNode(1, {weight: 1, nType: 1});
   // graph.nodes     => { '1': GraphNode { id: 1, weight: 1, nType: 1, neighbors: [] } }
   // graph.nodeCount => 1
   
   graph.addNode(2, {weight: 1, nType: 1});
   // graph.nodes     => { '1': GraphNode { id: 1, ... }, '2': GraphNode { id: 2, ... } }
   // graph.nodeCount =>  2
   
   graph.addNode(3, {weight: 4, nType: 1});
   // graph.nodes     => { '1': GraphNode { id: 1, ... }, '2': GraphNode { id: 2, ... }, '3': GraphNode { id: 3, weight: 4, ... } }
   // graph.nodeCount => 3
   
   graph.addEdge(1, 2);
   // graph.nodes     => { '1': GraphNode { id: 1, ..., neighbors: [ 2 ] }, '2': GraphNode { id: 2, ..., neighbors: [ 1 ] }, '3': GraphNode { id: 3, ...} }
   // graph.edgeCount => 1
   
   graph.addEdge(2, 3);
   // graph.nodes     => { '1': GraphNode { id: 1, ... }, '2': GraphNode { id: 2, ..., neighbors: [ 1, 3 ] }, '3': GraphNode { id: 3, ..., neighbors: [ 2 ] } }
   // graph.edgeCount => 2
   
   graph.addEdge(1, 3);
   // graph.nodes     => { '1': GraphNode { id: 1, ..., neighbors: [ 2, 3 ] }, '2': GraphNode { id: 2, ... }, '3': GraphNode { id: 3, ..., neighbors: [ 2, 1 ] } }
   // graph.edgeCount => 3
   
   var results   = Dijkstra.run(graph, 1, 3);
   var path      = Dijkstra.getPath(results.prev, 3);
   var printDist = 'node 1 is ' + results.dist[3] + ' unit from node 3'
   
   // results   => { source: 1, target: 3, dist: { '1': 0, '2': 1, '3': 1 }, prev: { '1': 1, '2': 1, '3': 1 } }
   // path      => [ 1, 3 ]
   // printDist => node 1 is 1 unit from node 3

Demos

• See the package in an angular application with our simple demo.

  Here we create a simple angular service to wrap the Graph and Dijkstra libraries. Using this service we make a 36 node graph to serve as a grid and demonstrate how to go about finding and acting on the shortest path.

• For an example of this package at work in a larger project, see our Office Employee Locator application.

  In this project we again create a service to wrap Graph and Dijkstra. Graph serves as the underlying graph of location objects (nodes) on which we run Dijkstra to find the shortest paths between them and generate directions.

Public API

See our project page for the full documentation (generated by documentationjs)

Graph

(prototype)

• Graph(graph)
• nodes
• nodeCount
• edgeCount
• find(id)
• exists(id)
• addNode(id, props)
• deleteNode(id)
• eachNode(fn)
• eachNeighbor(id, fn)
• addEdge(source, target)
• addOrCreateEdge(source, target)
• deleteEdge(source, target)
• connected(source, target)
• update(id, props)

GraphNode

(prototype)

• id
• weight
• nType
• neighbors

Dijkstra

(static)

• run(graph, pathType, source, target)
• getPath(prevList, target)

How to Contribute

Please see our Contributing Guide

This project was created for use in the Office Employee Locator application. We encourage and appreciate any contributions that aim to enhance the robustness of this module.

Credits

Authors: Matthew Vasseur and David Tahvildaran

Adapted Resources:

• Min Heap with Decrease Key

Library Resources:

• Lodash v4.3.1

License

See the LICENSE file for license rights and limitations (MIT).