The Neo4j Manual v3.1.0-SNAPSHOT33.2. Traversal Framework Java API

The TraversalDescription is the main interface used for defining and initializing traversals. It is not meant to be implemented by users of the traversal framework, but rather to be provided by the implementation of the traversal framework as a way for the user to describe traversals. TraversalDescription instances are immutable and its methods returns a new TraversalDescription that is modified compared to the object the method was invoked on with the arguments of the method.

Evaluators are used for deciding, at each position (represented as a Path): should the traversal continue, and/or should the node be included in the result. Given a Path, it asks for one of four actions for that branch of the traversal:

More than one evaluator can be added. Note that evaluators will be called for all positions the traverser encounters, even for the start node.

The Traverser object is the result of invoking traverse() of a TraversalDescription object. It represents a traversal positioned in the graph, and a specification of the format of the result. The actual traversal is performed lazily each time the next()-method of the iterator of the Traverser is invoked.

Sets the rules for how positions can be revisited during a traversal as stated in Uniqueness. Default if not set is NODE_GLOBAL.

A Uniqueness can be supplied to the TraversalDescription to dictate under what circumstances a traversal may revisit the same position in the graph. The various uniqueness levels that can be used in Neo4j are:

A more generic version of depthFirst/breadthFirst methods in that it allows an arbitrary BranchOrderingPolicy to be injected into the description.

A BranchSelector/BranchOrderingPolicy is used for selecting which branch of the traversal to attempt next. This is used for implementing traversal orderings. The traversal framework provides a few basic ordering implementations:

Note Please note that breadth first traversals have a higher memory overhead than depth first traversals.

BranchSelectors carries state and hence needs to be uniquely instantiated for each traversal. Therefore it is supplied to the TraversalDescription through a BranchOrderingPolicy interface, which is a factory of BranchSelector instances.

A user of the Traversal framework rarely needs to implement his own BranchSelector or BranchOrderingPolicy, it is provided to let graph algorithm implementors provide their own traversal orders. The Neo4j Graph Algorithms package contains for example a BestFirst order BranchSelector/BranchOrderingPolicy that is used in BestFirst search algorithms such as A* and Dijkstra.

description.order( BranchOrderingPolicies.PREORDER_DEPTH_FIRST );

A Path is a general interface that is part of the Neo4j API. In the traversal API of Neo4j the use of Paths are twofold. Traversers can return their results in the form of the Paths of the visited positions in the graph that are marked for being returned. Path objects are also used in the evaluation of positions in the graph, for determining if the traversal should continue from a certain point or not, and whether a certain position should be included in the result set or not.

The traversal framework use PathExpanders (replacing RelationshipExpander) to discover the relationships that should be followed from a particular path to further branches in the traversal.

A more generic version of relationships where a RelationshipExpander is injected, defining all relationships to be traversed for any given node.

The Expander interface is an extension of the RelationshipExpander interface that makes it possible to build customized versions of an Expander. The implementation of TraversalDescription uses this to provide methods for defining which relationship types to traverse, this is the usual way a user of the API would define a RelationshipExpander — by building it internally in the TraversalDescription.

All the RelationshipExpanders provided by the Neo4j traversal framework also implement the Expander interface. For a user of the traversal API it is easier to implement the PathExpander/RelationshipExpander interface, since it only contains one method — the method for getting the relationships from a path/node, the methods that the Expander interface adds are just for building new Expanders.

A traversal description is built using a fluent interface and such a description can then spawn traversers.

Figure 33.1. Traversal Example Graph

With the definition of the RelationshipTypes as

private enum Rels implements RelationshipType
{
    LIKES, KNOWS
}

The graph can be traversed with for example the following traverser, starting at the “Joe” node:

for ( Path position : db.traversalDescription()
        .depthFirst()
        .relationships( Rels.KNOWS )
        .relationships( Rels.LIKES, Direction.INCOMING )
        .evaluator( Evaluators.toDepth( 5 ) )
        .traverse( node ) )
{
    output += position + "\n";
}

The traversal will output:

(0)
(0)<--[LIKES,1]--(5)
(0)<--[LIKES,1]--(5)--[KNOWS,6]-->(1)
(0)<--[LIKES,1]--(5)--[KNOWS,6]-->(1)<--[KNOWS,5]--(6)
(0)<--[LIKES,1]--(5)--[KNOWS,6]-->(1)--[KNOWS,4]-->(4)
(0)<--[LIKES,1]--(5)--[KNOWS,6]-->(1)--[KNOWS,4]-->(4)--[KNOWS,3]-->(3)
(0)<--[LIKES,1]--(5)--[KNOWS,6]-->(1)--[KNOWS,4]-->(4)--[KNOWS,3]-->(3)--[KNOWS,2]-->(2)

Since TraversalDescriptions are immutable it is also useful to create template descriptions which holds common settings shared by different traversals. For example, let’s start with this traverser:

friendsTraversal = db.traversalDescription()
        .depthFirst()
        .relationships( Rels.KNOWS )
        .uniqueness( Uniqueness.RELATIONSHIP_GLOBAL );

This traverser would yield the following output (we will keep starting from the “Joe” node):

(0)
(0)--[KNOWS,0]-->(2)
(0)--[KNOWS,0]-->(2)<--[KNOWS,2]--(3)
(0)--[KNOWS,0]-->(2)<--[KNOWS,2]--(3)<--[KNOWS,3]--(4)
(0)--[KNOWS,0]-->(2)<--[KNOWS,2]--(3)<--[KNOWS,3]--(4)<--[KNOWS,4]--(1)
(0)--[KNOWS,0]-->(2)<--[KNOWS,2]--(3)<--[KNOWS,3]--(4)<--[KNOWS,4]--(1)<--[KNOWS,6]--(5)
(0)--[KNOWS,0]-->(2)<--[KNOWS,2]--(3)<--[KNOWS,3]--(4)<--[KNOWS,4]--(1)<--[KNOWS,5]--(6)

Now let’s create a new traverser from it, restricting depth to three:

for ( Path path : friendsTraversal
        .evaluator( Evaluators.toDepth( 3 ) )
        .traverse( node ) )
{
    output += path + "\n";
}

This will give us the following result:

(0)
(0)--[KNOWS,0]-->(2)
(0)--[KNOWS,0]-->(2)<--[KNOWS,2]--(3)
(0)--[KNOWS,0]-->(2)<--[KNOWS,2]--(3)<--[KNOWS,3]--(4)

Or how about from depth two to four? That’s done like this:

for ( Path path : friendsTraversal
        .evaluator( Evaluators.fromDepth( 2 ) )
        .evaluator( Evaluators.toDepth( 4 ) )
        .traverse( node ) )
{
    output += path + "\n";
}

This traversal gives us:

(0)--[KNOWS,0]-->(2)<--[KNOWS,2]--(3)
(0)--[KNOWS,0]-->(2)<--[KNOWS,2]--(3)<--[KNOWS,3]--(4)
(0)--[KNOWS,0]-->(2)<--[KNOWS,2]--(3)<--[KNOWS,3]--(4)<--[KNOWS,4]--(1)

For various useful evaluators, see the Evaluators Java API or simply implement the Evaluator interface yourself.

If you’re not interested in the Paths, but the Nodes you can transform the traverser into an iterable of nodes like this:

for ( Node currentNode : friendsTraversal
        .traverse( node )
        .nodes() )
{
    output += currentNode.getProperty( "name" ) + "\n";
}

In this case we use it to retrieve the names:

Joe
Sara
Peter
Dirk
Lars
Lisa
Ed

Relationships are fine as well, here’s how to get them:

for ( Relationship relationship : friendsTraversal
        .traverse( node )
        .relationships() )
{
    output += relationship.getType().name() + "\n";
}

Here the relationship types are written, and we get:

KNOWS
KNOWS
KNOWS
KNOWS
KNOWS
KNOWS

Tip The source code for the traversers in this example is available at: TraversalExample.java