Over a million developers have joined DZone.

Pathfinding with Neo4j Unmanaged Extensions

· Database Zone

Learn NoSQL for free with hands-on sample code, example queries, tutorials, and more.  Brought to you in partnership with Couchbase.

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;

    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(
           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"));
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"));

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:


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.

The Getting Started with NoSQL Guide will get you hands-on with NoSQL in minutes with no coding needed. Brought to you in partnership with Couchbase.


Published at DZone with permission of Max De Marzi, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

The best of DZone straight to your inbox.

Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}