The traversal framework
The traversal API described in this section has been deprecated and will be replaced by a new version of the API in the next major release of Neo4j. This new version will be available in a future release of Neo4j 4.x, alongside the current version. The current version, as detailed below, will be removed in Neo4j 5.0. For a detailed example on how to use the traversal framework, refer to The Neo4j Java Developer Reference v3.5. |
This section provides an overview of the concepts of the traversal framework, and a detailed description of the Neo4j traversal framework Java API.
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 Traversal.
You can also use the Cypher query language as a powerful declarative way to query the graph.
1. Main concepts
Below is a short explanation of all different methods that can modify or add to a traversal description.
-
Pathexpanders — define what to traverse, typically in terms of relationship direction and type.
-
Order — for example depth-first or breadth-first.
-
Uniqueness — visit nodes (relationships, paths) only once.
-
Evaluator — decide what to return and whether to stop or continue traversal beyond the current position.
-
Starting nodes where the traversal will begin.
2. Traversal framework Java API
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. |
The traversal framework consists of a few main interfaces in addition to Node
and Relationship
: TraversalDescription
, Evaluator
, Traverser
and Uniqueness
are the main ones.
The Path
interface also has a special purpose in traversals, since it is used to represent a position in the graph when evaluating that position.
Furthermore the PathExpander
(replacing RelationshipExpander
and 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: BranchSelector
, BranchOrderingPolicy
and TraversalBranch
.
2.1. TraversalDescription
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.
2.1.1. Relationships
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.
2.2. Evaluator
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.
Given a 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. |
2.3. Traverser
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.
2.4. Uniqueness
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:
-
NONE
: Any position in the graph may be revisited. -
NODE_GLOBAL
uniqueness: 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_GLOBAL
uniqueness: no relationship in the entire graph may be visited more than once. Just likeNODE_GLOBAL
uniqueness, 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_PATH
uniqueness: A node may not occur previously in the path reaching up to it. -
RELATIONSHIP_PATH
uniqueness: A relationship may not occur previously in the path reaching up to it. -
NODE_RECENT
uniqueness: Similar toNODE_GLOBAL
uniqueness 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_RECENT
uniqueness: Works likeNODE_RECENT
uniqueness, but with relationships instead of nodes.
2.4.1. Depth first / Breadth first
These are convenience methods for setting preorder depth-first / breadth-first BranchSelector
| ordering
policies.
The same result can be achieved by calling the order
method with ordering policies from BranchOrderingPolicies
, or to write your own BranchSelector
/ BranchOrderingPolicy
and pass in.
2.5. Order - how to move through branches?
This is a more generic version of depthFirst/ breadthFirst methods in that it enables an arbitrary BranchOrderingPolicy
to be injected into the description.
2.6. BranchSelector
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:
-
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. |
A BranchSelector
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.
2.6.1. BranchOrderingPolicy
A factory for creating BranchSelector
s 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 );
2.7. Path
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.
2.8. PathExpander / RelationshipExpander
The traversal framework use the PathExpander
(replacing RelationshipExpander
) to discover the relationships that should be followed from a particular path to further branches in the traversal.
2.9. Expander
This is 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.
2.10. How to use the Traversal framework
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. |
Was this page helpful?