Way finding / navigation with neo4j

Question

i know I'll probably get scolded for asking this but I'm hoping someone can help point me in the right direction.

I'm trying to create a way finding application like googles maps but have it mark routes to multiple points on a map.

I am attempting to make an animal transport tool that allows multiple people to meet in a path from point A to B. I thought I read you can do this with a graph database.

Can anyone offer resources on map databases, articles, etc to help me? I've been trying to google for articles but can find any matches so I assume I am using the wrong terms like 'way finding' or 'directions'

Thanks!

Answer 1

Graph databases works well for path finding, especially with shortestPath as mentioned by FrobberOfBits.

This works well as long as you have nodes that can form a path. From what I understand in your comments, in fact you'll need to build these nodes dynamically first depending of the user driving preferences.

Also, apparently you don't have currently a data model for Point A to Point B ?

This is how I would proceed, briefly :

The use case is the Point A is my home and the point 2 is where live the Neo4j Community CareTaker, on a map it would be :

All the little white points in the route from A to B can be Neo4j nodes.

Now you say, that for e.g., there is an awesome girl with a driving preference of 50km in order to join the route, so the current route has to change.

As in your application, you do not force users to choose an intermediary point, you will have to create it on the fly.

So my quick solution, is to get the point on the radius that will be the closest to the destination point of the initial route.

To achieve it, first you'll need the initial bearing from the current position of the girl to the destination (here Dresden)

Where lat1 and lon1 are the position of the girl, and lat2, lon2 the position of Dresden

Then, given this initial bearing you can calculate the position starting from the girl in the bearing bearing and 50 kms distance for e.g.

In PHP it would look like (tested) :

// Function that calculate new coordinates from point A
// Given a bearing and a distance to point B
function getAwayPosition($lat1, $lon1, $lat2, $lon2, $distance)
{
    // Getting true course from point A to point B
    $la1 = deg2rad($lat1);
    $la2 = deg2rad($lat2);
    $lo1 = deg2rad($lon1);
    $lo2 = deg2rad($lon2);

    $y = sin($la2-$la1)*cos($lo1);
    $x = cos($lo1*sin($lo2))-sin($lo1)*cos($lo2)*cos($la2-$la1);
    $course = fmod(rad2deg(atan2($y, $x)+360), 360);

    // Getting the new lat/lon points from lat1/lon1 given the course and the distance
    $bearing = deg2rad($course); //back to radians for the coordinates calculation
    $laa = asin(sin($la1 * cos($distance/6371 + $la1 * cos($course))));
    $loo = $lo1 + atan2(sin($bearing) * sin($distance/6371) * cos($la1), cos($distance/6371) - sin($la1) * sin($laa));

    return array(
        'lat' => rad2deg($laa),
        'lon' => rad2deg($loo),
        'bearing' => $course
    );
}

NB: There is also the haversin function in Cypher for calculating earth distances, I didn't play that much with it though

So, you can add a node that would represent the desired position for the girl in order to join the trip.

So far, we have now 3 good nodes for Neo4j :

Now I think it would be up to your data model for the rest of the process, if the route from A to B don't form already Neo4j nodes in your database, you can build it dynamically by calculating the distance from all the points with Google Maps API and set is as relationship property. Then you can do a Cypher shortestPath and reduce on the relationship distance property.

If you have already nodes representing multiple intermediate points of the initial route from A to B, you can use Neo4j Spatial and get the closest point from the desired position of the girl to the intermediate nodes of the route and create a relationship with the distance. And again shortestPath for the best mapped route.

The second solution would be better, because you will immediately have a graph to play with :

And a simple Cypher query if you want to get the path with the least kilometers :

MATCH (a:Point {id:'A'}), (b:Point {id:'B'})
MATCH p=allShortestPaths((a)-[:NEXT_POINT]-(b))
RETURN p, reduce(totalKm = 0, x in relationships(p)| totalKm + x.kilometers) as distance
ORDER BY distance ASC

There is also the Djikstra algorithm with cost properties available with the Neo4j ReST API http://neo4j.com/docs/stable/rest-api-graph-algos.html

Some resources :

• https://software.intel.com/node/341473
• http://www.movable-type.co.uk/scripts/latlong.html
• http://williams.best.vwh.net/avform.htm

So as a conclusion, if you want to use Neo4j for determining the best route, you'll need to help him with some data in the database ;-)

Answer 2

What you appear to be describing is a route from A to B via different waypoints (people's locations), but with the goal that the overall distance travelled from A to B is minimised. A path in a graph with these characteristics is known as a Minimum Spanning Tree. Crucially, the fact that people can travel to meet the "main route" simply introduces additional waypoints it does not change the overall problem, or the way it is classically solved.

Neither Cypher nor the REST API have a function to calculate minimum spanning trees and unfortunately simply collecting shortest paths between individual nodes (e.g using Dijkstra's algorithm) and then trying to create a path from these shortest-path segments will not be optimal in the general case.

However it is not difficult to implement Prim's algorithm via a server plugin or unmanaged extension in Neo4j, and I would recommend you look into this.

Answer 3

I'd start with this article. To ask a more specific question, you'll need a data model and an example of what you're trying to do.

But in general the language to use is probably "shortest path". Generally, if you're trying to find a path from point A to point B, you're looking for the "shortest path" where the "cost of the path" is minimal. Sometimes cost is distance, and sometimes cost is time - but either way you're usually looking for the shortest path, not just any path.