Max De Marzi

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.