31 Oct 2017

Neo4j: Traversal query timeout

I’ve been spending some of my spare time over the last few weeks creating an application that generates running routes from Open Roads data - transformed and imported into Neo4j of course!

I’ve created a user defined procedure which combines several shortest path queries, but I wanted to exit any of these shortest path searches if they were taking too long. My code without a timeout looks like this:

StandardExpander orderedExpander = new OrderedByTypeExpander()
    .add( RelationshipType.withName( "CONNECTS" ), Direction.BOTH );

PathFinder<Path> shortestPathFinder = GraphAlgoFactory.shortestPath( expander, 250 );

...

There are several places where we could check the time elapsed, but the expand method in the Expander seemed like an obvious one to me. I wrote my own Expander class which looks like this:

public class TimeConstrainedExpander implements PathExpander
{
    private final StandardExpander expander;
    private final long startTime;
    private final Clock clock;
    private int pathsExpanded = 0;
    private long timeLimitInMillis;

    public TimeConstrainedExpander( StandardExpander expander, Clock clock, long timeLimitInMillis )
    {
        this.expander = expander;
        this.clock = clock;
        this.startTime = clock.instant().toEpochMilli();
        this.timeLimitInMillis = timeLimitInMillis;
    }

    @Override
    public Iterable<Relationship> expand( Path path, BranchState state )
    {
        long timeSoFar = clock.instant().toEpochMilli() - startTime;
        if ( timeSoFar > timeLimitInMillis )
        {
            return Collections.emptyList();
        }

        return expander.expand( path, state );
    }

    @Override
    public PathExpander reverse()
    {
        return expander.reverse();
    }
}

The code snippet from earlier now needs to be updated to use our new class, which isn’t too tricky:

StandardExpander orderedExpander = new OrderedByTypeExpander()
    .add( RelationshipType.withName( "CONNECTS" ), Direction.BOTH );

TimeConstrainedExpander expander = new TimeConstrainedExpander(orderedExpander,
    Clock.systemUTC(), 200);

PathFinder<Path> shortestPathFinder = GraphAlgoFactory.shortestPath( expander, 250 );
...

I’m not sure if this is the best way to achieve what I want but after failing with several other approaches at least this one actually works!

About the author

I'm currently working on short form content at ClickHouse. I publish short 5 minute videos showing how to solve data problems on YouTube @LearnDataWithMark. I previously worked on graph analytics at Neo4j, where I also co-authored the O'Reilly Graph Algorithms Book with Amy Hodler.