Prev |  | Next

## 6.2. Path finding examples

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

The full source code of the path finding examples are found at https://github.com/neo4j/graphdb/blob/master/graph-algo/src/test/java/examples/PathFindingExamplesTest.java.

Copyright © 2011 Neo Technology

Prev | Up | Next
| Home |