Cool spatial algos with Neo4j: Part 1 - Routing with A* in Ruby

Introduction

The GIS and Spatial domain is one of the hottest areas of complex data right now, and an interesting case for using a graph database like Neo4j as well. There are several trends that come into play here:

• The accessibility of geographic datasets with Google Maps, the Open Street Map Project , Nokias Ovi Maps providing increasingly accurate and crowd sourced base data for geographic information
• Startups like GeoAPI and SimpleGeo providing interesting APIs for commonly needed services in an easy-to-use manner via REST and JSON
• Geographical standards and APIs like Web Map Service and others like KML, WFS etc, defined by bodies like the Open Geospatial Consortium (OpenGIS) and others catching on and becoming a good base to develop applications upon
• Most new mobile devices have now GPS sensors and APIs built in, augmenting more data with location info.

As a result of the increasing availability of geospatial information it's becoming part of the core domain model for an expanding range of applications. Events, photos, running routes, logistics systems and location games all have the geographical position of the domain data as a core aspect of their data.

The traditional approach has been to create spatial indexes as a separate system, typically in PostGIS, Oracle Spatial or other specialized systems in order to then ask them certain types of queries. Afterwards, these results are intersected in set operations with the domain objects in question.

As spatial attributes and queries are now becoming intertwined with the domain models, so are the datasets. The domain objects like friends, buildings or trucks ARE the spatial "points of interest", so a separate spatial system just to do these queries means duplication of your data, resulting in synchronization problems. Queries like

• "Give me all my friends that are listening to the same music genre, are between 20 and 40 years old, live within 50km of my current position and are online in GTalk"

span a lot of different aspects of a dataset, spatial queries just being one of them. In a graph, all of these data aspects can be modeled in the same data structure, resulting in a traversal-based approach to these queries as opposed to a set-based crunching of different index-results.

Neo4j and routing

Neo4j as a Graph Database is modeling all data as Nodes, Relationships and Properties on them. Since this is a very flexible model, arbitrary data can be added to any domain model in order to build for instance spatial indexes and logic right into the data itself. In a typical application, a subgraph could contain some road network like this:

The advantage of having the spatial data in the graph is that at any time the different points can be related and incorporated into different indexes, e.g. K-trees, QuadTrees and other interesting approaches.

Since Neo4j has very fast traversal performances, we can employ classic deep graph algos like the A* algorithm that is effectively a cost minimizing deep traversal through a network.

Original from Wikipedia, see here

Now, in Neo4j an A* implementation in Java looks like this. Basically, nodes are evaluated regarding their accumulated cost from the start node, and the "as the crow flies" remaining distance to the end node. For this, we need a EstimateEvaluator which can calculate the remaining distance (as the geodetic distance) in meters (in Ruby):

#implements a Java Interface
class GeoCostEvaluator
  include EstimateEvaluator
  def getCost(node, goal)
    distance(node.getProperty("lat"), node.getProperty("lon"), goal.getProperty("lat"),goal.getProperty("lon"))
  end
end

#calculates a geodetic distance between two spatial points
def distance(start_lat, start_lon, other_lat, other_lon)
  latitude1 = start_lat.to_f * Math::PI/180 #in radian
  longitude1 = start_lon.to_f * Math::PI/180 #in radian
  latitude2 = other_lat.to_f * Math::PI/180 #in radian
  longitude2 = other_lon.to_f * Math::PI/180 #in radian
  cLa1 = Math.cos( latitude1 );
  x_A = RADIUS_EARTH * cLa1 * Math.cos( longitude1 )
  y_A = RADIUS_EARTH * cLa1 * Math.sin( longitude1 )
  z_A = RADIUS_EARTH * Math.sin( latitude1 );

  cLa2 = Math.cos( latitude2 );
  x_B = RADIUS_EARTH * cLa2 * Math.cos( longitude2 )
  y_B = RADIUS_EARTH * cLa2 * Math.sin( longitude2 )
  z_B = RADIUS_EARTH * Math.sin( latitude2 )
  
  #in meters
  distance = Math.sqrt( ( x_A - x_B ) * ( x_A - x_B ) + ( y_A - y_B ) * ( y_A - y_B ) + ( z_A - z_B ) * ( z_A - z_B ) )
end

We also need a CostEvaluator which calculates the cost associated with choosing a certain path using the stored information in the graph (here the cost is attached to the relationships representing roads as meters). In our case, we'll model this in our domain as a "cost" property attached to the edges representing roads:

#domain model
class Road
  include Neo4j::RelationshipMixin
  
  property :cost
end

class Waypoint
  include Neo4j::NodeMixin
  
  # neo4j node properties
  property :lat, :lon, :name
  
  # lucene indexed node properties
  index :name
  
  # relationships to other waypoints
  has_n(:road).to(Waypoint).relationship(Road)
  
  # for this example just calculate the straight distance between points as cost
  def connect(other)
    self.road.new(other).update(:cost => distance(self.lat, self.lon, other.lat, other.lon))
  end
  def to_s
    "Waypoint, #{name}, lon=#{lon}, lat=#{lat}"
  end
end

Then, let's look up the coordinates of cities using Yahoo!'s geocoding webservice with the name and state of the city. It makes the creation of a sample a lot easier:

# create point, and look up the location via Yahoo! MapsService
def create_waypoint(city, state)
  url = "http://local.yahooapis.com/MapsService/V1/geocode?appid=#{APP_ID}"
  res = Net::HTTP.get(URI.parse( URI.escape(url + "&state=#{state}&city=#{city}") ))
  
  lat = res.slice(/Latitude\>(.*)\<\/Latitude/,1)
  lon = res.slice(/Longitude\>(.*)\<\/Longitude/,1)
  point = Waypoint.new :name=>city, :lon=>lon, :lat=>lat
  puts point
  point
end

Now, populating the system with a few cities and connect them is as easy as:

# populating the routing test
Neo4j::Transaction.run do
  NYC = create_waypoint('New York', 'New York')
  KAN = create_waypoint('Kansas City', 'Kansas')
  SFE = create_waypoint('Santa Fe', 'New Mexico')
  SEA = create_waypoint('Seattle', 'Washington')
  SF = create_waypoint('San Francisco', 'CA')
  NYC.connect(KAN)
  NYC.connect(SEA)
  SEA.connect(SF)
  KAN.connect(SFE)
  SFE.connect(SF)
end

The resulting routing network looks something like this:

Now finding the optimal route is simply a matter of calling the Java A* algo form Ruby:

# Finding the route
sp = AStar.new( Neo4j::instance, RelationshipExpander.forTypes( DynamicRelationshipType.withName('Waypoint#road'), Direction::BOTH),
				        DoubleEvaluator.new("cost") , GeoCostEvaluator.new)
path = sp.findSinglePath(NYC._java_node, SF._java_node)
nodes = path.getNodes.iterator
until !nodes.hasNext() do 
  puts nodes.next.getProperty('name')
end

In our case, populating the network and finding a route from New York to San Francisco will look like this:

Waypoint, New York, lon=-74.007124, lat=40.714550
Waypoint, Kansas City, lon=-94.626824, lat=39.113380
Waypoint, Santa Fe, lon=-105.937406, lat=35.691543
Waypoint, Seattle, lon=-122.329439, lat=47.603560
Waypoint, San Francisco, lon=-122.420139, lat=37.779600
New York
Kansas City
Santa Fe
San Francisco

Which is depicted here:

This is a very trivial example, but the A* algorithm works well in Neo4j with routes hundreds and thousands of hops deep, on millions of roads and waypoints, imported for instance from OpenStreetMaps. A Neo4j plugin to the Osmosis project to export that data is underway and will be part of another spatial blog entry.

Summary

The A* algorithm is not the best of solutions for advanced routing in real life conditions, but it provides a first measure of the mechanics and performance characteristics involved when operating on big graphs with deep traversals. Of course, obvious improvements are:

• Introduce a bi-directional approach (two A* starting from start and end node, meeting in the middle), thus cutting time
• Introduce "via" waypoints like cities or big traffic hubs, cutting the total distance into shorter chunks that can be calculated in parallel
• introduce higher-order graphs that describe the logistics backbone like Highways and Autobahns and first find the nearest connection to that network, go near the end point and return to the local road network for the final distance
• Introduce better cost functions that take into account not only distance but also allowed speed, road conditions, one-way lanes etc.
• Factor in customer context like the current used car, family preferences and so on.

Still being able to do these calculations in sub-second speeds on graphs of millions of roads and waypoints makes it possible in many cases to abandon the normal approach of precomputing indexes with K/V stores and be able to put routing into the critical path with the possibility to adapt to the live conditions and build highly personalized and dynamic spatial services.

The full source code and project setup is found at github.com/neo4j-examples/ruby-astar-routing. Play with the code, add cities, connections and have some fun with the routing! There is even a Java version at http://github.com/neo4j-examples/java-astar-routing.

Feel free to comment or contact me at peter at neotechnology dot com. You're welcome to the Neo4j mailing lists as well.