anvaka / ngraph.path

Path finding in a graph

ngraph.path

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

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.

	Average	Median	Min	Max	p90	p99
A* greedy (suboptimal)	32ms	24ms	0ms	179ms	73ms	136ms
NBA*	44ms	34ms	0ms	222ms	107ms	172ms
A*, unidirectional	55ms	38ms	0ms	356ms	123ms	287ms
Dijkstra	264ms	258ms	0ms	782ms	483ms	631ms

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

Source code for performance measurements

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:

npm i ngraph.path

Or download from CDN:

<script src='https://unpkg.com/[email protected]/dist/ngraph.path.min.js'></script>

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

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

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

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:

let createGraph = require('ngraph.graph');
let graph = createGraph();

graph.addLink('a', 'b', {weight: 10});
graph.addLink('a', 'c', {weight: 10});
graph.addLink('c', 'd', {weight: 5});
graph.addLink('b', 'd', {weight: 10});

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

let pathFinder = aStar(graph, {
  // We tell our pathfinder what should it use as a distance function:
  distance(fromNode, toNode, link) {
    // We don't really care about from/to nodes in this case,
    // as link.data has all needed information:
    return link.data.weight;
  }
});
let path = pathFinder.find('a', 'd');

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.

let createGraph = require('ngraph.graph');
let graph = createGraph();

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

// and railroads:
graph.addLink('NYC', 'Boston');
graph.addLink('NYC', 'Philadelphia');
graph.addLink('Philadelphia', 'Washington');

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

let pathFinder = aStar(graph, {
  distance(fromNode, toNode) {
    // In this case we have coordinates. Lets use them as
    // distance between two nodes:
    let dx = fromNode.data.x - toNode.data.x;
    let dy = fromNode.data.y - toNode.data.y;

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

    return Math.sqrt(dx * dx + dy * dy);
  }
});
let path = pathFinder.find('NYC', 'Washington');

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:

let pathFinder = aStar(graph, {
  oriented: true
});

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:

let createGraph = require('ngraph.graph');
let graph = createGraph();

// Our graph has cities:
graph.addNode('NYC');
graph.addNode('Philadelphia');
graph.addNode('Baltimore');
graph.addNode('Pittsburgh');
graph.addNode('Washington');

// and railroads:
graph.addLink('NYC', 'Philadelphia', { disruption: false });
graph.addLink('Philadelphia', 'Baltimore', { disruption: true });
graph.addLink('Philadelphia', 'Pittsburgh', { disruption: false });
graph.addLink('Pittsburgh', 'Washington', { disruption: false });
graph.addLink('Baltimore', 'Washington', { disruption: false });

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:

let path = require('ngraph.path');

let pathFinder = path.aStar(graph, {
  blocked(fromNode, toNode, link) {
    return link.data.disruption;
  },
});
let result = pathFinder.find('NYC', 'Washington');

available finders

The library implements a few A* based path finders:

let aStarPathFinder = path.aStar(graph, options);
let aGreedyStar = path.aGreedy(graph, options);
let nbaFinder = path.nba(graph, options);

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

ngraph.path's Issues

Option to have multiple paths

Is there a way to have an option to show at least 3 shortest paths for given nodes?

Publish graph-from-ascii separately

Hey, looked through the code and I like how you can quickly visualize a graph in ascii and have it created for you. So please publish this as a module that anyone could use.

Great work with this lib BTW .. I'm sure it'll come in useful for something I need some day.

Getting specific link when used with multigraph

When used with a multigraph, is there a way to see which specific link the path is using?

For example, when returning multiple paths (#6 (comment)), in order to know which links to invalidate for subsequent searches, we need to be able to access the links found by the pathfinder.

How to use HTML？

How to use the web side?
PHP environment

allow providing custom goal?

Let's suppose the we want pathfinder to find "water" from sourceNode ?
How about adding customGoal in the options argument similarly to the heuristic / distance options?

Usage in a grid based system

Hi,

I’m developing a simple game on a 2D grid.

I have many enemies that have to find shortest path to the player every 0.5 second.
There’s static and dynamic obstacles in the grid (when an enemy or player moves, the tile it moves onto becomes an obstacle for other enemies).
In other words they can’t stand on the same tile.

I’m trying to use your library to implement this but a little confused as to how to code the obstacles bit.

Can I get some advice please? Do I have to add links to every walkable neighbour tile of each tile?

What about providing a simple installation way?

?

Possible to get the total path distance from a pathFinder lookup?

I just started using ngraph, it's pretty good. When I try the "Weighted Graph" example from the Readme, I get the correct paths. But to get the total distance I still need to traverse my dataset to lookup the weight of every path? Or is ngraph able to deliver this as part of the result as well (and if so, how???)

I use it in vue.js (webpack), so the code looks slightly different:

        let graphRoads = createGraph();
        graphRoads.addLink('Hobitton', 'Bywater', {weight: 465});
        graphRoads.addLink('Hobitton', 'Overhill', {weight: 500});
        graphRoads.addLink('Bywater', 'Frogmorton', {weight: 450});
        graphRoads.addLink('Bywater', 'Whitfurrows', {weight: 482});
        let pathFinder = path.aStar(graphRoads, {
            // We tell our pathfinder what should it use as a distance function:
            distance(fromNode, toNode, link) {
                // We don't really care about from/to nodes in this case,
                // as link.data has all needed information:
                return link.data.weight;
            }
        });
        let pathThing = pathFinder.find('Hobitton', 'Frogmorton');
        console.log('pathThing',pathThing)

Returns an array of the three nodes, it takes to get from Hobitton to Frogmorton. There is a "data" key, but it's "undefined":

[
   Node {id: "Frogmorton", links: Array(1), data: undefined
   Node {id: "Bywater", links: Array(3), data: undefined
   Node {id: "Hobitton", links: Array(2), data: undefined
]

createGraph doesn't exist

There's no createGraph function to be found anywhere!

The module's ambient file only exposes three functions

export function aStar, aGreedy and nba.

"fewest turns" refinement?

hey @anvaka,

nice lib!

how feasible is it to add some post-processing pass to produce a "fewest turns" route to reduce the number of left-right-left-right turns in the path at the expense of some configurable "cost" for additional distance added to the route.

i frequently find it ultra aggravating when a destination can be reached with 3 turns and an extra 0.25mi rather than 7 turns. it simplifies the directions and number of legs in each route. google maps has a habit of providing such "scenic" routes.

thanks!

Turn penalties

Hi there,

I'm using this library to draw a network graph on top of a grid, and I was wondering if you could suggest how to best implement a "turn penalty", to avoid a stair-casing effect, using the distance and heuristic functions.

Thanks!

Using GPU to speed up pathfinding on large graphs

Hi!

I have been using ngraph packages for a long time and recently came across the need to use pathfinding on graphs of the order of 100M nodes and up to 600M egdes (a graph built on an ordered grid). Tell me if there is a possibility of using GPU to speed up the processing of large graphs?

@anvaka

Unable to use blocked and distance

When I create a pathfinder that uses both blocked and distance, the blocked always gets ignored.
Am I doing something wrong?

graph.addLink("shopA","liftA",{weight:10, wheelchair: true});
graph.addLink("liftA","liftB",{weight:1, wheelchair: true});
graph.addLink("liftB","shopB",{weight:10, wheelchair: true});
graph.addLink("shopA","stairsA",{weight:5, wheelchair: true});
graph.addLink("stairsA","stairsB",{weight:1, wheelchair: false});
graph.addLink("stairsB","shopB",{weight:5, wheelchair: true});

let pathFinder_wc = ngraphPath.aStar(graph, {
    blocked(fromNode, toNode, link) {
        return !link.data.wheelchair;
    },
    distance(fromNode, toNode, link) {
        return link.data.weight;
    },
});

let path = pathFinder_wc.find("shopA","shopB");

path always returns the shortest regardless of stairsA -> stairsB is wheelchair false

contraction hierarchies

You mention in your README that you want to know about faster algorithms.
The fastest I heard of for OpenStreetmap data is http://project-osrm.org/
Paper describing the concept: http://algo2.iti.kit.edu/documents/chbasedtnr_TR.pdf

Subgraphs around a center node?

Hi! Is it possible to select a subgraph of neighbours around a specific node within a given distance radius, also known as ego graphs? Thanks. (P.S. keep up the awesome work here!)

The CDN is down

Hey @anvaka, thanks for the cool lib. The CDN is not working.

Stop when a condition is met

Is there a way to have some kind of dynamic end point?

More specifically, in my case: I want to target a specific node but stop when I'm within 50px of the destination. Is there a way to achieve this?

is It possible to get more than one path ??

So nba.findpath(source, destination) returns the shortest path nodes array my question is can this return all the other position paths also? so in case if I don't want to take the first shortest path and need to another path?