Calculating the shortest path (least number of relationships) between two nodes:
Node startNode = graphDb.createNode(); Node middleNode1 = graphDb.createNode(); Node middleNode2 = graphDb.createNode(); Node middleNode3 = graphDb.createNode(); Node endNode = graphDb.createNode(); createRelationshipsBetween( startNode, middleNode1, endNode ); createRelationshipsBetween( startNode, middleNode2, middleNode3, endNode ); // Will find the shortest path between startNode and endNode via // "MY_TYPE" relationships (in OUTGOING direction), like f.ex: // // (startNode)-->(middleNode1)-->(endNode) // PathFinder<Path> finder = GraphAlgoFactory.shortestPath( Traversal.expanderForTypes( ExampleTypes.MY_TYPE, Direction.OUTGOING ), 15 ); Iterable<Path> paths = finder.findAllPaths( startNode, endNode );
Using Dijkstra’s algorithm to calculate cheapest path between node A and B where each relationship can have a weight (i.e. cost) and the path(s) with least cost are found.
PathFinder<WeightedPath> finder = GraphAlgoFactory.dijkstra( Traversal.expanderForTypes( ExampleTypes.MY_TYPE, Direction.BOTH ), "cost" ); WeightedPath path = finder.findSinglePath( nodeA, nodeB ); // Get the weight for the found path path.weight();
Using A* to calculate the cheapest path between node A and B, where cheapest is for example the path in a network of roads which has the shortest length between node A and B. Here’s our example graph:
Node nodeA = createNode( "name", "A", "x", 0d, "y", 0d ); Node nodeB = createNode( "name", "B", "x", 7d, "y", 0d ); Node nodeC = createNode( "name", "C", "x", 2d, "y", 1d ); Relationship relAB = createRelationship( nodeA, nodeC, "length", 2d ); Relationship relBC = createRelationship( nodeC, nodeB, "length", 3d ); Relationship relAC = createRelationship( nodeA, nodeB, "length", 10d ); 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.expanderForAllTypes(), CommonEvaluators.doubleCostEvaluator( "length" ), estimateEvaluator ); WeightedPath path = astar.findSinglePath( nodeA, nodeB );
Full source code: PathFindingExamplesTest.java
Copyright © 2012 Neo Technology