This chapter provides an overview of the concepts of the traversal framework, and a detailed description of the Neo4j traversal framework Java API.
The traversal API described in this section been deprecated and will be removed in a later release of Neo4j.
This chapter describes the following:
The Neo4j Traversal framework Java API is a callback-based, lazily-executed way of specifying desired movements through a graph in Java. Some traversal examples are collected under Section 2.7, “Traversal”.
You can also use the Cypher query language as a powerful declarative way to query the graph.
Below is a short explanation of all different methods that can modify or add to a traversal description.
The traversal framework consists of a few main interfaces in addition to
Uniqueness are the main ones.
Path interface also has a special purpose in traversals, since it is used to represent a position in the graph when evaluating
Expander) interface is central to traversals, but users of the API rarely need to implement it.
There are also a set of interfaces for advanced use, when explicit control over the traversal order is required:
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.
Adds a relationship type to the list of relationship types to traverse.
By default this list is empty and it means that it will traverse all relationships, regardless of type.
If one or more relationships are added to this list only the added types will be traversed.
There are two methods, one
including direction and another one
excluding direction, where the latter traverses relationships in both directions.
Evaluators are used for deciding, at each position (represented as a
Path) whether the traversal should continue, and/or whether the node should be included in the result.
Path, it asks for one of four actions for that branch of the traversal:
Evaluation.INCLUDE_AND_CONTINUE: Include this node in the result and continue the traversal.
Evaluation.INCLUDE_AND_PRUNE: Include this node in the result, but do not continue the traversal.
Evaluation.EXCLUDE_AND_CONTINUE: Exclude this node from the result, but continue the traversal.
Evaluation.EXCLUDE_AND_PRUNE: Exclude this node from the result and do not continue the traversal.
More than one evaluator can be added.
Evaluators will be called for all positions the traverser encounters, even for the start node.
Traverser object is the result of invoking
traverse() of a
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
Default if not set is
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:
NONE: Any position in the graph may be revisited.
NODE_GLOBALuniqueness: No node in the entire graph may be visited more than once. This could potentially consume a lot of memory since it requires keeping an in-memory data structure remembering all the visited nodes.
RELATIONSHIP_GLOBALuniqueness: no relationship in the entire graph may be visited more than once. Just like
NODE_GLOBALuniqueness, this could potentially use up a lot of memory. But since graphs typically have a larger number of relationships than nodes, the memory overhead of this uniqueness level could grow even quicker.
NODE_PATHuniqueness: A node may not occur previously in the path reaching up to it.
RELATIONSHIP_PATHuniqueness: A relationship may not occur previously in the path reaching up to it.
NODE_RECENTuniqueness: Similar to
NODE_GLOBALuniqueness in that there is a global collection of visited nodes each position is checked against. This uniqueness level does however have a cap on how much memory it may consume in the form of a collection that only contains the most recently visited nodes. The size of this collection can be specified by providing a number as the second argument to the TraversalDescription.uniqueness()-method along with the uniqueness level.
RELATIONSHIP_RECENTuniqueness: Works like
NODE_RECENTuniqueness, but with relationships instead of nodes.
These are convenience methods for setting preorder depth-first/ breadth-first
The same result can be achieved by calling the
order method with ordering policies from
BranchOrderingPolicies, or to write your own
BranchOrderingPolicy and pass in.
This is a more generic version of depthFirst/ breadthFirst methods in that it enables an arbitrary
BranchOrderingPolicy to be injected into the description.
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:
BranchOrderingPolicies.PREORDER_DEPTH_FIRST: Traversing depth first, visiting each node before visiting its child nodes.
BranchOrderingPolicies.POSTORDER_DEPTH_FIRST: Traversing depth first, visiting each node after visiting its child nodes.
BranchOrderingPolicies.PREORDER_BREADTH_FIRST: Traversing breadth first, visiting each node before visiting its child nodes.
BranchOrderingPolicies.POSTORDER_BREADTH_FIRST: Traversing breadth first, visiting each node after visiting its child nodes.
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
A user of the Traversal framework rarely needs to implement his own
BranchOrderingPolicy, it is provided to let graph algorithm implementors provide their own traversal orders.
The Neo4j Graph Algorithms package contains for example a
BranchOrderingPolicy that is used in BestFirst search algorithms such as A* and Dijkstra.
A factory for creating
BranchSelectors to decide in what order branches are returned (where a branch’s position is represented as a
Path from the start node to the current node).
Common policies are depth-first and breadth-first and that is why there are convenience methods for those.
For example, calling
TraversalDescription#depthFirst() is equivalent to:
description.order( BranchOrderingPolicies.PREORDER_DEPTH_FIRST );
An object used by the BranchSelector to get more branches from a certain branch. In essence these are a composite of a Path and a RelationshipExpander that can be used to get new TraversalBranches from the current one.
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
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
RelationshipExpander) to discover the relationships that should be followed from a particular path to further branches in the traversal.
This is a more generic version of relationships where a
RelationshipExpander is injected, defining all relationships to be traversed for any given node.
Expander interface is an extension of the
RelationshipExpander interface that makes it possible to build customized versions of an
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
RelationshipExpander — by building it internally in the
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.
The traversal framework is no longer supported. For a detailed example on how to use it, refer to The Neo4j Java Developer Reference v3.5.