Calculating time should not require to read speed from edge in wrong direction

Developers
1

Hi,

from time to time I get an Exception like:

Calculating time should not require to read speed from edge in wrong direction. Reverse:false, fwd:false, bwd:true

I changed some values in my weighting. Now I can reproduce this error. Before it only happened occasionally when generating round trips. What I don’t understand is why we call the method calcMillis with false for the revert boolean. Any idea why this might happen?

Best,
Robin

This is the Stacktrace:

at com.graphhopper.routing.Path.calcMillis(Path.java:250)
	at com.graphhopper.routing.Path.processEdge(Path.java:237)
	at com.graphhopper.routing.PathBidirRef.extract(PathBidirRef.java:92)
	at com.graphhopper.routing.DijkstraBidirectionRef.extractPath(DijkstraBidirectionRef.java:132)
	at com.graphhopper.routing.AbstractBidirAlgo.calcPath(AbstractBidirAlgo.java:64)
	at com.graphhopper.routing.AbstractRoutingAlgorithm.calcPaths(AbstractRoutingAlgorithm.java:121)
	at com.graphhopper.GraphHopper.calcPaths(GraphHopper.java:1327)
	at com.graphhopper.GraphHopper.calcPaths(GraphHopper.java:1188)
	at com.graphhopper.GraphHopper.route(GraphHopper.java:1182)
	at com.graphhopper.http.GraphHopperServlet.doGet(GraphHopperServlet.java:142)
	at javax.servlet.http.HttpServlet.service(HttpServlet.java:735)
	at javax.servlet.http.HttpServlet.service(HttpServlet.java:848)
	at com.google.inject.servlet.ServletDefinition.doServiceImpl(ServletDefinition.java:287)
	at com.google.inject.servlet.ServletDefinition.doService(ServletDefinition.java:277)
	at com.google.inject.servlet.ServletDefinition.service(ServletDefinition.java:182)
	at com.google.inject.servlet.ManagedServletPipeline.service(ManagedServletPipeline.java:91)
	at com.graphhopper.http.IPFilter.doFilter(IPFilter.java:46)
	at org.eclipse.jetty.servlets.UserAgentFilter.doFilter(UserAgentFilter.java:82)
	at com.graphhopper.http.CORSFilter.doFilter(CORSFilter.java:43)
	at org.eclipse.jetty.servlets.UserAgentFilter.doFilter(UserAgentFilter.java:82)
	at org.eclipse.jetty.servlets.GzipFilter.doFilter(GzipFilter.java:294)
	at com.graphhopper.http.GHGZIPHook.doFilter(GHGZIPHook.java:44)
	at com.google.inject.servlet.ManagedFilterPipeline.dispatch(ManagedFilterPipeline.java:119)
	at com.google.inject.servlet.GuiceFilter$1.call(GuiceFilter.java:133)
	at com.google.inject.servlet.GuiceFilter$1.call(GuiceFilter.java:130)
	at com.google.inject.servlet.GuiceFilter$Context.call(GuiceFilter.java:203)
	at com.google.inject.servlet.GuiceFilter.doFilter(GuiceFilter.java:130)
	at org.eclipse.jetty.servlet.ServletHandler$CachedChain.doFilter(ServletHandler.java:1467)
	at org.eclipse.jetty.servlet.ServletHandler.doHandle(ServletHandler.java:501)
	at org.eclipse.jetty.server.handler.ContextHandler.doHandle(ContextHandler.java:1086)
	at org.eclipse.jetty.servlet.ServletHandler.doScope(ServletHandler.java:429)
	at org.eclipse.jetty.server.handler.ContextHandler.doScope(ContextHandler.java:1020)
	at org.eclipse.jetty.server.handler.ScopedHandler.handle(ScopedHandler.java:135)
	at org.eclipse.jetty.server.handler.HandlerList.handle(HandlerList.java:52)
	at org.eclipse.jetty.server.handler.HandlerWrapper.handle(HandlerWrapper.java:116)
	at org.eclipse.jetty.server.Server.handle(Server.java:370)
	at org.eclipse.jetty.server.AbstractHttpConnection.handleRequest(AbstractHttpConnection.java:494)
	at org.eclipse.jetty.server.AbstractHttpConnection.headerComplete(AbstractHttpConnection.java:971)
	at org.eclipse.jetty.server.AbstractHttpConnection$RequestHandler.headerComplete(AbstractHttpConnection.java:1033)
	at org.eclipse.jetty.http.HttpParser.parseNext(HttpParser.java:644)
	at org.eclipse.jetty.http.HttpParser.parseAvailable(HttpParser.java:235)
	at org.eclipse.jetty.server.AsyncHttpConnection.handle(AsyncHttpConnection.java:82)
	at org.eclipse.jetty.io.nio.SelectChannelEndPoint.handle(SelectChannelEndPoint.java:696)
	at org.eclipse.jetty.io.nio.SelectChannelEndPoint$1.run(SelectChannelEndPoint.java:53)
	at org.eclipse.jetty.util.thread.QueuedThreadPool.runJob(QueuedThreadPool.java:608)
	at org.eclipse.jetty.util.thread.QueuedThreadPool$3.run(QueuedThreadPool.java:543)
	at java.lang.Thread.run(Thread.java:745)
2

I just changed the code of the calcMillis method to the following:

    protected long calcMillis( double distance, long flags, boolean revert )
    {
        if(!encoder.isBackward(flags) && !encoder.isForward(flags)){
            throw new IllegalStateException("Edge is neither Forward nor Backwards. "
                    + "Reverse:" + revert + ", fwd:" + encoder.isForward(flags) + ", bwd:" + encoder.isBackward(flags));
        }
        revert = !encoder.isForward(flags);
        /*
        if (revert && !encoder.isBackward(flags)
                || !revert && !encoder.isForward(flags))
            throw new IllegalStateException("Calculating time should not require to read speed from edge in wrong direction. "
                    + "Reverse:" + revert + ", fwd:" + encoder.isForward(flags) + ", bwd:" + encoder.isBackward(flags));

        */

        double speed = revert ? encoder.getReverseSpeed(flags) : encoder.getSpeed(flags);
        if (Double.isInfinite(speed) || Double.isNaN(speed) || speed < 0)
            throw new IllegalStateException("Invalid speed stored in edge! " + speed);

        if (speed == 0)
            throw new IllegalStateException("Speed cannot be 0 for unblocked edge, use access properties to mark edge blocked! Should only occur for shortest path calculation. See #242.");

        return (long) (distance * 3600 / speed);
    }
3

The path object stores the EdgeIteratorStates in one direction (after extract was called) and therefor revert has to be always false. Somehow the edge is not available in forward direction in your case but still returned. Can you print the weight of the Path in the exception too?

What do you mean here?

4

Hi Peter,

thanks for your reply.

I added the following output to the Exception (in the Path.java#processEdge):

System.out.println(iter);
System.out.println(this.getWeight());

This is the output:

5564 31022-30989
7522.473327755479

So the first ist the Edge that is causing the error and the second is the weight of the path.
BTW: the Path is 114km long and takes 1h 40m (according to GraphHopper).

I locally changed the code of the calcMillis method, because I did not understand the revert parameter. With this change I can calculate the time of the path. But I guess it makes more sense to find the source of the problem.

Best,
Robin

P.S. I just received a 502 Bad Gateway from discuss.graphhopper.com

5

The revert parameter is true if a bidirectional Algo like Dijkstra or A* is requesting the weight for the reverse shortest path tree.

I locally changed the code of the calcMillis method

Is the exception thrown without the change and with the change it is okay?

Hmmh, strange. Did not update or something :confused:

6

Really? I only found calls using false, except for one Test Case and in the Path4CH class.

Yes. The change fixes the Exception, but I guess the change is not a really nice one. We probably need something more sophisticated. As a first solution we could combine both approachs like this (not sure if you want to do this?):

if (revert && !encoder.isBackward(flags) || !revert && !encoder.isForward(flags)){
  if(!encoder.isBackward(flags) && !encoder.isForward(flags)){
     throw new IllegalStateException("Edge is neither Forward nor Backwards. "
                    + "Reverse:" + revert + ", fwd:" + encoder.isForward(flags) + ", bwd:" + encoder.isBackward(flags));
  }
  revert = !encoder.isForward(flags);
  // Log the event?
}

It was gone after some seconds. Just wanted to let you know.

7

Sorry, I mixed calcMillis with calcWeight. But the exception indicates reverse=false which should be fine. I still think that the exception is ‘correct’ and do not understand why the edge is stored in the wrong direction in your case - did you had a chance to debug this?

Or can you recreate this in a unit test or will it only happen with your modified weights?

8

This only happens with certain Path and Weighting combinations. It works for almost all cases, but for some cases it doesn’t.

I tried to get a better understanding of the issue. So it seems to happen on the BiDir extract. From the toEdge towards the mid. After we reversed the Order. I tried to debug it, but could not find anything suspicious. Could you give me a hint on how to debug this?

9

I am able to reproduce this Exception using the current germany.osm.pbf (downloaded yesterday) and the current graphhopper master using the curvature weighting and motorcycle. Here is an URL that produces the error:

http://localhost:8989/?point=48.873748%2C8.412781&point=49.099864%2C7.993197&locale=de-DE&vehicle=motorcycle&weighting=curvature&elevation=false&layer=Omniscale

10

Ok, strange. Would you create an issue for that? And as a test: can you throw an exception when the weighting gets 0 (or smaller than e.g. 0e-10) or negative in the CurvatureWeighting?

11

Thanks. I will create an issue for that. I just checked the CurvatureWeighting. There are cases where we return 0 in the Weighting. I just change the return to 1 if we would return 0, but this didn’t change anything.

The EdgeId of where we return 0 is also the same Edge where the Exception is thrown.

1 Like