NoSQL Zone is brought to you in partnership with:

Max De Marzi, is a seasoned web developer. He started building websites in 1996 and has worked with Ruby on Rails since 2006. The web forced Max to wear many hats and master a wide range of technologies. He can be a system admin, database developer, graphic designer, back-end engineer and data scientist in the course of one afternoon. Max is a graph database enthusiast. He built the Neography Ruby Gem, a rest api wrapper to the Neo4j Graph Database. He is addicted to learning new things, loves a challenge and finding pragmatic solutions. Max is very easy to work with, focuses under pressure and has the patience of a rock. Max is a DZone MVB and is not an employee of DZone and has posted 60 posts at DZone. You can read more from them at their website. View Full User Profile

Pathfinding with Neo4j Unmanaged Extensions

11.28.2012
| 3328 views |
  • submit to reddit

In Extending Neo4j I showed you how to create an unmanaged extension to warm up the node and relationship caches. Let’s try doing something more interesting like exposing the A* (A Star) search algorithm through the REST API. The graph we created earlier looks like this:

I created a 5 by 5 grid of nodes with properties x and y and “next_to” relationships between them with a random time property. The x and y properties of the node tells us where along the grid that node lies, and the time property between two adjacent nodes tells us how long it takes to travel along the path connecting them. A* finds the least-cost path between a starting node and an ending point.

A* needs to know: the start and end node, some way to estimate the distance to the end node, and the cost of traversing relationships. With this information A* traverses along the graph following the path with the least known heuristic cost which is just the sum of the cost of the path currently traveled and the estimate to the end node.

Take a look at the video below for a visual demonstration of the A* algorithm in action.

To do this in Neo4j, we would add a method to the MyService.java file we created previously.

import org.neo4j.graphalgo.*;
import org.neo4j.kernel.Traversal;

    @GET
    @Path("/astar/{from}/{to}")
    @Produces("application/json")
    public Response routeAStar(@PathParam("from") Long from, @PathParam("to") Long to, 
                               @Context GraphDatabaseService db) throws IOException {
       Node nodeA = db.getNodeById(from);
       Node nodeB = db.getNodeById(to);

       EstimateEvaluator<Double> estimateEvaluator = new EstimateEvaluator<Double>()
	        {
	            public Double getCost( final Node node, final Node goal )
	            {
	                double dx = (Double) node.getProperty( "x" ) - (Double) goal.getProperty( "x" );
	                double dy = (Double) node.getProperty( "y" ) - (Double) goal.getProperty( "y" );
	                double result = Math.sqrt( Math.pow( dx, 2 ) + Math.pow( dy, 2 ) );
	                return result;
	            }
	        };

       PathFinder<WeightedPath> astar = GraphAlgoFactory.aStar(
           Traversal.pathExpanderForAllTypes(),
           CommonEvaluators.doubleCostEvaluator( "time" ), estimateEvaluator );

       WeightedPath path = astar.findSinglePath( nodeA, nodeB );

       return Response.ok().entity( path.toString() ).build();
    }

We created an EstimateEvaluator that in this case uses the Euclidean Distance for its heuristic, and the property time for the actual cost of traversing a relationship. We are using the GraphAlgoFactory and the aStar method going over all types of relationships with a pathExpander.

Let’s try going from node 1 to node 12 in the REST web admin panel:

We get a path from node 1, to 2, to 7 to 12 at a weight of 8.0 (if you try this at home your numbers may differ as your graph will be randomly generated).

get /example/service/astar/1/12
(1)--[next_to,1]-->(2)--[next_to,2]-->(7)--[next_to,12]-->(12) weight:8.0

I like the compact representation of the path, but what if I want to see more than that? For example I want to return a nice JSON representation of the time the path takes, the nodes and relationships in the path, and their respective properties? I can build a HashMap and add the pieces I want to it:

Map<String, Object> astarMap = new HashMap<String, Object>();
astarMap.put("time", path.weight());

List<Object> nodes = new ArrayList<Object>();
for ( Node node : path.nodes() )
    {
	 Map<String, Object> nodeMap = new HashMap<String, Object>();
        		 nodeMap.put("id", node.getId());
        		 nodeMap.put("x", node.getProperty("x"));
        		 nodeMap.put("y", node.getProperty("y"));
     nodes.add(nodeMap);
          }
astarMap.put("nodes", nodes);

List<Object> relationships = new ArrayList<Object>();
for ( Relationship relationship : path.relationships() )
    {
         		 Map<String, Object> relMap = new HashMap<String, Object>();
                  relMap.put("id", relationship.getId());
                  relMap.put("rel_type", relationship.getType().name());
                  relMap.put("start_node", relationship.getStartNode().getId());
                  relMap.put("end_node", relationship.getEndNode().getId());
                  relMap.put("time", relationship.getProperty("time"));
         relationships.add(relMap);
          }

astarMap.put("relationships", relationships);

ObjectMapper objectMapper = new ObjectMapper();
         return Response.ok().entity(objectMapper.writeValueAsString(astarMap)).build();

When I run the get command again, I now return:

{"time":8.0,
 "nodes":[{"id":1,"y":0.0,"x":0.0},
          {"id":2,"y":1.0,"x":0.0},
          {"id":7,"y":1.0,"x":1.0},
          {"id":12,"y":1.0,"x":2.0}],
 "relationships":[{"start_node":1,"id":1,"time":3.0,"rel_type":"next_to","end_node":2},      
                  {"start_node":2,"id":2,"time":4.0,"rel_type":"next_to","end_node":7},
                  {"start_node":7,"id":12,"time":1.0,"rel_type":"next_to","end_node":12}]
}

Which is a little more verbose, but easier to deal with. If you want to learn more about A* and path finding, I recommend Amit Patel’s blog on Game Programming. The code as always is available on github.

With unmanaged extensions you can have your cake and eat it too. The full power and speed of the embedded Java API over REST. Use it wisely and enjoy.

Published at DZone with permission of Max De Marzi, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)