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.

graphdb traversal description

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 like NODE_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 to NODE_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 like NODE_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 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 );

2.6.2. TraversalBranch

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.

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.