Bidirectional Traversal Framework

A bidirectional traversal consists of two traversals starting from different nodes, returning the paths where both traversals collide. The Bidirectional Traversal Framework allows the description of such a traversal with the BidirectionalTraversalDescription.

Here is a visual representation of a bidirectional traversal from start node 1 and end node 5, where all bold relationships are in the result paths given the following restrictions:

bidirectional example

  • The start side traverser only traverses relationships of type A.

  • The end side traverser only traverses relationships of type B.

Note that paths where only one of the traversers reaches the opposite start/end node are also included, such as (1)-[:A]→(5) and (1)-[:B]→(5). In the accepted path (1)-[:A]→(2)-[:A]→(3)-[:B]→(4)-[:B]→(5), the traversers collide in the middle at node 3.

The Uniqueness is shared between both traversals, which means that there will be no results if the Uniqueness is set to Uniqueness.NODE_GLOBAL, as both traversals need to reach the same node to cause a collision. For this reason, always set the Uniqueness manually when using the BidirectionalTraversalDescription, since the default is Uniqueness.NODE_GLOBAL.

Defining the Bidirectional Traverser

When creating a BidirectionalTraversalDescription, it is possible to choose the TraversalDescription that each side takes. This can be done by setting it individually for each side (startSide/endSide), or setting one for both (mirroredSides).

Start and End Side Traversal

See this example of a BidirectionalTraversalDescription with a separate traverser for the startSide() and endSide():

BidirectionalTraversalDescription td = transaction
        .bidirectionalTraversalDescription()
        .startSide(transaction
                .traversalDescription()
                .expand(PathExpanders.forTypeAndDirection(RelationshipType.withName("A"), Direction.OUTGOING))
                .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL))
        .endSide(transaction
                .traversalDescription()
                .expand(PathExpanders.forTypeAndDirection(RelationshipType.withName("B"), Direction.INCOMING))
                .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL));
td.traverse(startNode, endNode);

One side is traversing forward from the start node and expanding all outgoing relationships of Type A. The other side is traversing backwards from the end node and expanding all incoming relationships of Type B.

The final paths will go from the start node to the end node, where all relationships have an outgoing direction. Possible paths would be:

  • All relationships are of Type A.

  • All relationships are of Type B.

  • The relationships from the start node are Type A and, after the collision, they are all of type B.

Mirrored Traversal

The mirroredSides(TraversalDescription) method sets both the start side and end side of this bidirectional traversal. However, the end side will be the reverse of the start. For the Direction of Relationships this means that OUTGOING becomes INCOMING and vice versa. The PathExpander interface also comes with a reverse() function which should be overridden if used in a mirroredSides implementation.

BidirectionalTraversalDescription td = transaction
        .bidirectionalTraversalDescription()
        .mirroredSides(transaction
                               .traversalDescription()
                               .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL));
td.traverse(startNode, endNode);

Side Selector

In a bidirectional traversal, the traverser selects which side (start or end) to move on each step. It is possible to change how this works by implementing the SideSelectorPolicy interface, as it has a function for determining which side to traverse the next step from.

  • Direction.OUTGOING — The traverser coming from the start node.

  • Direction.INCOMING — The traverser coming from the end node.

The built-in policies include:

  • SideSelectorPolicies.LEVEL — Stops traversal if the combined depth is larger than the given maximum depth.

  • SideSelectorPolicies.LEVEL_STOP_DESCENT_ON_RESULT — Stops as soon as a result is found.

  • SideSelectorPolicies.ALTERNATING — Alternates which branch continues the traversal.

The SideSelectorPolicy optionally takes a maxDepth which represents the combined depth that both sides must adhere to.

Here is an example of how to use a built-in SideSelectorPolicy with a max combined depth of 5:

BidirectionalTraversalDescription td = transaction
        .bidirectionalTraversalDescription()
        .mirroredSides(transaction
                               .traversalDescription()
                               .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL))
                               .sideSelector(SideSelectorPolicies.LEVEL, 5);
td.traverse(startNode, endNode);

Collision Policies

A BranchCollisionPolicy defines when a collision is detected and accepted in a bidirectional traversal. Given an evaluator and a path predicate, a BranchCollisionPolicy will create a BranchCollisionDetector, which will detect collisions between two traversers and add the resulting path to the result if it satisfies the conditions given by the collision evaluator and Uniqueness constraints.

These are the built-in BranchCollisionPolicies:

  • STANDARD — Returns all paths with a collision.

  • SHORTEST_PATH — Returns all paths with the smallest traversal depth.

Here is an example of how to use a built-in BranchCollisionPolicy:

BidirectionalTraversalDescription td = transaction
        .bidirectionalTraversalDescription()
        .mirroredSides(transaction
                               .traversalDescription()
                               .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL))
        .collisionPolicy(BranchCollisionPolicies.SHORTEST_PATH);
td.traverse(startNode, endNode);

Collision Evaluator

The convenience method collisionEvaluator() adds a PathEvaluator which will validate paths in a valid collision. Using the method multiple times will result in the combination of the evaluators.

BidirectionalTraversalDescription td = transaction
    .bidirectionalTraversalDescription()
    .mirroredSides(transaction
       .traversalDescription()
       .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL))
    .collisionEvaluator(Evaluators.atDepth(3));
td.traverse(startNode, endNode);