3.11. Graph algorithm examples

This section describes some examples of using graph algorithms.

For details on the graph algorithm usage, see the Javadocs.

The source code used in the example is found here: PathFindingDocTest.java

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(
            PathExpanders.forTypeAndDirection( 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(
            PathExpanders.forTypeAndDirection( 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 is our example graph:

A* algorithm 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>()
        {
            @Override
            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(
                PathExpanders.allTypesAndDirections(),
                CommonEvaluators.doubleCostEvaluator( "length" ), estimateEvaluator );
        WeightedPath path = astar.findSinglePath( nodeA, nodeB );