The Neo4j Traversal API is a callback based, lazily executed way of specifying desired movements through a graph in Java. Some traversal examples are collected under [tutorials-java-embedded-traversal].
You can also use The Cypher Query Language as a powerful declarative way to query the graph.
Here follows 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.
"Traversal Description" [fillcolor="NODEHIGHLIGHT"] Uniqueness -> "Traversal Description" [label="avoid duplicates"] Evaluator -> "Traversal Description" [label="return and prune policy"] Order -> "Traversal Description" [label="where to go next"] PathExpander -> "Traversal Description" [label="what to traverse"] "Depth First" [TEXTNODE] "Breadth First" [TEXTNODE] "Relationship Type" [TEXTNODE] "Direction" [TEXTNODE] "Unique Nodes" [TEXTNODE] "Unique Relationships" [TEXTNODE] "Unique Paths" [TEXTNODE] "None" [TEXTNODE] "Include/Exclude" [TEXTNODE] "Prune/Continue" [TEXTNODE] "Depth First" -> Order [dir="back"] "Breadth First" -> Order [dir="back"] PathExpander -> "Relationship Type" "Direction" -> PathExpander [dir="back"] "Unique Nodes" -> Uniqueness [dir="back"] "Unique Relationships" -> Uniqueness [dir="back"] "Unique Paths" -> Uniqueness [dir="back"] "None" -> Uniqueness [dir="back"] "Include/Exclude" -> Evaluator [dir="back"] Evaluator -> "Prune/Continue" Traverser [fillcolor="NODE2HIGHLIGHT"] "A Node" [fillcolor="NODEHIGHLIGHT"] "Traversal Description" -> Traverser [dir="back" label="applies" weight=3.0] "A Node" -> Traverser [label="starting point of"] Traverser -> Paths [label="result as"] Traverser -> Nodes [label="result as"] Traverser -> Relationships [label="result as"] { rank="same"; Traverser; "A Node" }
See Traversal Framework Java API for more details.
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
.
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.
Adds a relationship type to the list of relationship types to traverse. By default that 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.
Evaluator
s 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:
-
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 don’t 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 don’t continue 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:
-
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. For the same reasons asNODE_GLOBAL
uniqueness, this could 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.
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.
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:
-
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.
Note
|
Please note that breadth first traversals have a higher memory overhead than depth first traversals. |
BranchSelector
s 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.
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’s 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 TraversalBranch
es from the current one.
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 PathExpander
s (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.