ngraph.path

Path finding in a graph

Graph
anvaka/ngraph.pathanvaka.github.io/ngraph.path.demo/ngraph.path

README

ngraph.path


Fast path finding for arbitrary graphs. Play with a demo or watch it on YouTube.

demo

If you want to learn how the demo was made, please refer to the demo's source code.
I tried to describe it in great details.

Performance


I measured performance of this library on New York City roads graph (733,844 edges, 264,346 nodes).
It was done by solving 250 random path finding problems. Each algorithm was solving
the same set of problems. Table below shows required time to solve one problem.

|MedianMinMaxp90p99
|----------------------------------------|---------|:------:|:---:|-------|-------|-------|
A*32ms24ms0ms179ms73ms
NBA*44ms34ms0ms222ms107ms
A*,55ms38ms0ms356ms123ms
Dijkstra264ms258ms0ms782ms483ms

"A* greedy" converged the fastest, however, as name implies the found path is not necessary
globally optimal.

Why is it fast?


There are a few things that contribute to the performance of this library.

I'm using heap-based priority queue, built specifically for the path finding.
I modified a heap's implementation,
so that changing priority of any element takes O(lg n) time.

Each path finder opens many graph nodes during its exploration, which creates pressure
on garbage collector. To avoid the pressure, I've created an object pool,
which recycles nodes when possible.

In general, the A* algorithm helps to converge to the optimal solution faster than
Dijkstra, because it uses "hints" from the heuristic function. When search is performed
in both directions (source -> target and target -> source), the convergence can be
improved even more. The NBA* algorithm
is a bi-directional path finder, that guarantees optimal shortest path. At the same time it
removes balanced heuristic requirement. It also seem to be the fastest algorithm, among implemented
here (NB: If you have suggestions how to improve this even further - please let me know!)

I also tried to create my own version of bi-directional A* search, which
turned out to be harder than I expected - the two searches met each other quickly, but the point
where they met was not necessary on the shortest global path. It was close to optimal, but not the optimal.
I wanted to remove the code, but then changed my mind: It finds a path very quickly. So, in case when
speed matters more than correctness, this could be a good trade off. I called this algorithm A* greedy,
but maybe it should be A* lazy.

usage


installation


You can install this module, bu requiring it from npm:

  1. ```
  2. npm i ngraph.path
  3. ```

Or download from CDN:

  1. ``` html
  2. <script src='https://unpkg.com/ngraph.path@1.3.1/dist/ngraph.path.min.js'></script>
  3. ```

If you download from CDN the library will be available under ngraphPath global name.

Basic usage


This is a basic example, which finds a path between arbitrary
two nodes in arbitrary graph

  1. ``` js
  2. let path = require('ngraph.path');
  3. let pathFinder = path.aStar(graph); // graph is https://github.com/anvaka/ngraph.graph

  5. // now we can find a path between two nodes:
  6. let fromNodeId = 40;
  7. let toNodeId = 42;
  8. let foundPath = pathFinder.find(fromNodeId, toNodeId);
  9. // foundPath is array of nodes in the graph
  10. ```

Example above works for any graph, and it's equivalent to unweighted Dijkstra's algorithm.

Weighted graph


Let's say we have the following graph:

  1. ``` js
  2. let createGraph = require('ngraph.graph');
  3. let graph = createGraph();

  5. graph.addLink('a', 'b', {weight: 10});
  6. graph.addLink('a', 'c', {weight: 10});
  7. graph.addLink('c', 'd', {weight: 5});
  8. graph.addLink('b', 'd', {weight: 10});
  9. ```

weighted

We want to find a path with the smallest possible weight:

  1. ``` js
  2. let pathFinder = aStar(graph, {
  3.   // We tell our pathfinder what should it use as a distance function:
  4.   distance(fromNode, toNode, link) {
  5.     // We don't really care about from/to nodes in this case,
  6.     // as link.data has all needed information:
  7.     return link.data.weight;
  8.   }
  9. });
  10. let path = pathFinder.find('a', 'd');
  11. ```

This code will correctly print a path: d <- c <- a.

Guided (A-Star)


When pathfinder searches for a path between two nodes it considers all
neighbors of a given node without any preference. In some cases we may want to
guide the pathfinder and tell it our preferred exploration direction.

For example, when each node in a graph has coordinates, we can assume that
nodes that are closer towards the path-finder's target should be explored
before other nodes.

  1. ``` js
  2. let createGraph = require('ngraph.graph');
  3. let graph = createGraph();

  5. // Our graph has cities:
  6. graph.addNode('NYC', {x: 0, y: 0});
  7. graph.addNode('Boston', {x: 1, y: 1});
  8. graph.addNode('Philadelphia', {x: -1, y: -1});
  9. graph.addNode('Washington', {x: -2, y: -2});

  11. // and railroads:
  12. graph.addLink('NYC', 'Boston');
  13. graph.addLink('NYC', 'Philadelphia');
  14. graph.addLink('Philadelphia', 'Washington');
  15. ```

guided

When we build the shortest path from NYC to Washington, we want to tell the pathfinder
that it should prefer Philadelphia over Boston.

  1. ``` js
  2. let pathFinder = aStar(graph, {
  3.   distance(fromNode, toNode) {
  4.     // In this case we have coordinates. Lets use them as
  5.     // distance between two nodes:
  6.     let dx = fromNode.data.x - toNode.data.x;
  7.     let dy = fromNode.data.y - toNode.data.y;

  9.     return Math.sqrt(dx * dx + dy * dy);
  10.   },
  11.   heuristic(fromNode, toNode) {
  12.     // this is where we "guess" distance between two nodes.
  13.     // In this particular case our guess is the same as our distance
  14.     // function:
  15.     let dx = fromNode.data.x - toNode.data.x;
  16.     let dy = fromNode.data.y - toNode.data.y;

  18.     return Math.sqrt(dx * dx + dy * dy);
  19.   }
  20. });
  21. let path = pathFinder.find('NYC', 'Washington');
  22. ```

With this simple heuristic our algorithm becomes smarter and faster.

It is very important that our heuristic function does not overestimate actual distance
between two nodes. If it does so, then algorithm cannot guarantee the shortest path.

oriented graphs


If you want the pathfinder to treat your graph as oriented - pass oriented: true setting:

  1. ``` js
  2. let pathFinder = aStar(graph, {
  3.   oriented: true
  4. });
  5. ```

blocked paths


In scenarios where a path might be temporarily blocked between two nodes a blocked() function
may be supplied to resolve blocked routes during path finding.

For example, train routes with service disruptions could be modelled as follows:

  1. ``` js
  2. let createGraph = require('ngraph.graph');
  3. let graph = createGraph();

  5. // Our graph has cities:
  6. graph.addNode('NYC');
  7. graph.addNode('Philadelphia');
  8. graph.addNode('Baltimore');
  9. graph.addNode('Pittsburgh');
  10. graph.addNode('Washington');

  12. // and railroads:
  13. graph.addLink('NYC', 'Philadelphia', { disruption: false });
  14. graph.addLink('Philadelphia', 'Baltimore', { disruption: true });
  15. graph.addLink('Philadelphia', 'Pittsburgh', { disruption: false });
  16. graph.addLink('Pittsburgh', 'Washington', { disruption: false });
  17. graph.addLink('Baltimore', 'Washington', { disruption: false });
  18. ```

While the Philadelphia to Baltimore route is facing a service disruption, the alternative
route to Washington is via Pittsburgh. The following is an example blocked() function implementation
that may be supplied to yield this result:

  1. ``` js
  2. let path = require('ngraph.path');

  4. let pathFinder = path.aStar(graph, {
  5.   blocked(fromNode, toNode, link) {
  6.     return link.data.disruption;
  7.   },
  8. });
  9. let result = pathFinder.find('NYC', 'Washington');
  10. ```

available finders


The library implements a few A* based path finders:

  1. ``` js
  2. let aStarPathFinder = path.aStar(graph, options);
  3. let aGreedyStar = path.aGreedy(graph, options);
  4. let nbaFinder = path.nba(graph, options);
  5. ```

Each finder has just one method find(fromNodeId, toNodeId), which returns array of
nodes, that belongs to the found path. If no path exists - empty array is returned.

Which finder to choose?


With many options available, it may be confusing whether to pick Dijkstra or A*.

I would pick Dijkstra if there is no way to guess a distance between two arbitrary nodes
in a graph. If we can guess distance between two nodes - pick A*.

Among algorithms presented above, I'd recommend A* greedy if you care more about speed and
less about accuracy. However if accuracy is your top priority - choose NBA*.
This is a bi-directional, optimal A* algorithm with very good exit criteria. You can read
about it here: https://repub.eur.nl/pub/16100/ei2009-10.pdf

license


MIT