Mark Needham

Thoughts on Software Development

Neo4j: Traversal query timeout

without comments

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!

Be Sociable, Share!

Written by Mark Needham

October 31st, 2017 at 9:43 pm

Posted in neo4j

Tagged with ,