Changes in Direction with The Traversal API

We got an odd request in User Slack the other day. A user wanted to find paths between nodes where the direction of the relationships changes up to just one time. Cypher doesn’t have a good handle on the concept of Direction beyond specifying it on a path. APOC doesn’t seem to have a method to figure this one out either… but to be fair I may have missed it since there are hundreds of awesome stored procedures now. Regardless, lets go ahead and build it the “old school” way. Using the Traversal API… and just to be slick, we’ll use the Bidirectional Traverser.

Wait a minute! Hasn’t the Traversal API been deprecated:

Boo Hoo Hoo, who cares. It’s still in Neo4j 4.1.1, there is nothing that replaces it (sit down Cypher, you can’t do half what this baby can do) and it will make you feel “big brain” every time you use it. Alright let’s get right into it. We are going to get two nodes passed in to us, then we need a list of relationship types we are allowed to traverse and a maximum length so we don’t go crazy looking all over the universe for paths.

 
@Procedure(name = "com.maxdemarzi.one.direction", mode = Mode.READ)
@Description("CALL com.maxdemarzi.one.direction(start, end, types, length)")
public Stream<PathResult> OneDirection(@Name(value = "start") Node start,
                                       @Name(value = "end") Node end,
                                       @Name(value = "types") String types,
                                       @Name(value = "length") Long length) {

Alright now what do we do? Well, we need to be able to describe what our traversal does in order to use the Traversal API, so we’ll create a Traversal Description. Since we’re going bi-directional, we’ll make the traversal explore breadth first. 99% of the time you want depth first, the 1% is when you are doing bi-directional. Next we need to tell it what relationship types to expand and for up to what length, so we’ll create a custom Expander to capture this logic. Lastly we need to pick a uniqueness and for this particular user they did not want to see the same node in a path twice, so that’s what we went with:

 
 TraversalDescription td = tx.traversalDescription()
       .breadthFirst()
       .expand(new RelTypesExpander(types, length))
       .uniqueness(Uniqueness.NODE_PATH);

Alright, we have our description, how do we make it bi-directional? Well… we create a new description but this time take the description we just created and use mirroredSides so that it expands the same way from both directions. You can also choose to expand in different ways from either side, but mirror is fine for us. The last thing to deal with is what do we do when both sides meet? For that we’ll add a custom collision evaluator. More on that coming up.

 
BidirectionalTraversalDescription bidirtd = tx.bidirectionalTraversalDescription()
          .mirroredSides(td)
          .collisionEvaluator(ONE_DIRECTION_CHANGE_EVALUATOR);

To finish off the procedure, we will perform the traversal which gives us an iterator of paths and we’ll turn it into a Stream and map each path to a PathResult to return to the client. Easy right?

 
return StreamSupport.stream(bidirtd.traverse(start, end).spliterator(), false).map(PathResult::new);

Well, not so fast. Working backwards we need the collision evaluator, but its the same for every traversal so we can make it static:

 
private static final OneDirectionChangeEvaluator ONE_DIRECTION_CHANGE_EVALUATOR = new OneDirectionChangeEvaluator();

Alright, what does it actually look like? Well we are overriding the evaluate method of an Evaluator, so we start with that. If the path is one or two hops we know at most we changed direction once, so there is no point worrying about checking things, we just include the path in our result and stop going this way:

 
public class OneDirectionChangeEvaluator implements Evaluator {
    @Override
    public Evaluation evaluate(Path path) {
        long nodeId = path.startNode().getId();

        if(path.length() < 3) {
            return Evaluation.INCLUDE_AND_PRUNE;
        }

It’s at 3 hops and greater that things get interesting. I need to count the number of times the direction of the traversal changed. So I’ll start with a direction of BOTH and a changes count of -1. Why -1, why not zero? Well because I need to set it to zero the first time I see a direction but I don’t want to change my logic, so -1 it is.

 
Direction direction = Direction.BOTH;
int changes = -1;

What’s the logic? For each relationship in the path I check the starting node of the relationship against the last nodeId we looked at. If they are equal, then it’s an OUTGOING relationship, so we check the direction and if it isn’t already outgoing we increment changes and set it. If the nodeId is not equal to the relationship start node id, then it’s an INCOMING relationship so we check the current direction for INCOMING, set it and increment it if it is different. Finally we change the nodeId we’re looking at to be the other node in the relationship.

 
        for(Relationship rel : path.relationships()) {
            if(rel.getStartNodeId() == nodeId) {
                if(direction != Direction.OUTGOING) {
                    changes++;
                    direction = Direction.OUTGOING;
                }
            } else {
                if(direction != Direction.INCOMING) {
                    changes++;
                    direction = Direction.INCOMING;
                }
            }
            nodeId = rel.getOtherNodeId(nodeId);
        }

After going through all the relationships we check the changes. If it’s less than 2 then we’re good. We include the path and stop looking this way. If not we exclude the path and also stop looking.

 
        if (changes < 2) {
            return Evaluation.INCLUDE_AND_PRUNE;
        } else {
            return Evaluation.EXCLUDE_AND_PRUNE;
        }

Alright, now let’s set our sights on the custom Expander we talked about earlier. It has a constructor that takes the relationship types as a comma separated string, splits them, trims each and adds them to a list. It also keeps track of the maximum length.

 
public class RelTypesExpander implements PathExpander {
    ArrayList<RelationshipType> relationshipTypes;
    Long length;

    public RelTypesExpander(String types, Long length) {

        this.relationshipTypes = new ArrayList<>();
        for (String typeName : types.split(",")) {
            typeName = typeName.trim();
            this.relationshipTypes.add(RelationshipType.withName(typeName));
        }
        this.length = length;
    }

We need to override the expand method to make a PathExpander, so we start by checking the path length. If we’ve gone too far, we return an empty list so there is nowhere else to go.

 
    @Override
    public Iterable<Relationship> expand(Path path, BranchState branchState) {
        // If we're past the length limit return an empty list
        if (path.length() > length) { return Collections.emptyList(); }

Next we get the last node along the path:

 
final Node node = path.endNode();

We need to get the relationships of this node by type, but they are in a relationship type list and the getRelationships method can’t handle that. So we have to do some fancy Java magic to create a “Nesting Iterator” (an iterator of iterators) which goes through the list and gets the relationships of that type from the node:

 
        // Traverse all the relationship types in either direction
        return Iterators.asList(new NestingIterator<>(relationshipTypes.iterator()) {
            @Override
            protected Iterator<Relationship> createNestedIterator(RelationshipType relationshipType) {
                return node.getRelationships(relationshipType).iterator();
            }
        });

If someone knows a better way to do this, send me a pull request please. Lastly we need to provide a reverse method which returns an Expander that goes backwards. In our case we can just return “this”.

 
    @Override
    public PathExpander reverse() {
        return this;
    }

Let’s not forget to write a test as well. We’ll find our two nodes, then call the stored procedure and count up the number of paths it finds.

 
   @Test
    void shouldFindValidPaths() {
        // In a try-block, to make sure we close the driver after the test
        try(Driver driver = GraphDatabase.driver( neo4j.boltURI() , Config.builder().withoutEncryption().build())) {
            // Given I've started Neo4j with the procedure
            //       which my 'neo4j' rule above does.
            Session session = driver.session();

            // When I use the procedure
            Result result = session.run("MATCH (u1:User { name: 'max' } ), (u4:User { name: 'luke' } ) WITH u1, u4 " +
                    "CALL com.maxdemarzi.one.direction(u1, u4, 'KNOWS, LIKES', 5) YIELD path RETURN count(path) AS count");
            Record record = result.single();
            assertEquals(2L, record.get("count").asLong());
        }
    }

In my test that answer was just 2. As always, the source code is on github so go take a look. Just remember, if you can’t do it with Cypher, and you can’t do it with APOC, then roll up your sleeves, get down and dirty and write it yourself. Ping me if you need help.

Tagged , , , , , , , , ,

One thought on “Changes in Direction with The Traversal API

  1. Jaime Hernandez says:

    This was awesome. I had never heard of the traversal API.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: