Graphhopper: Curvature Weighting produces Exception for Path#calcMillis

[boldtrn]

As discussed here, there are cases that result in an Exception using the CurvatureWeighting.

Interesting is that in these cases the speed for that edge is 0, but we never set an edge to speed 0 using the getSpeed() method in the CarEncoder.

The weighting returns 0. And we get the following Exception:

java.lang.IllegalStateException: Calculating time should not require to read speed from edge in wrong direction. Reverse:false, fwd:false, bwd:true
    at com.graphhopper.routing.Path.calcMillis(Path.java:266)
    at com.graphhopper.routing.Path.processEdge(Path.java:238)
    at com.graphhopper.routing.PathBidirRef.extract(PathBidirRef.java:95)
    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)

To reproduce this Exception, load the current germany.osm.pbf. And visit this URL: http://localhost:8989/?point=48.873748%2C8.412781&point=49.099864%2C7.993197&locale=de-DE&vehicle=motorcycle&weighting=curvature&elevation=false&layer=Omniscale

[easbar]

I think I made a little progress with this and reproduced the error in a unit test. I figured out that there is a single edge that causes the error and when I looked up the coordinates I found out that its the ferry crossing the Rhine river near Karlsruhe :)

A routing request from one riverside to the other only works (again using the map for all of Germany from Geofabrik) when going from West to East but not the other way around.

This works:
http://localhost:8989/?point=48.978881%2C8.25488&point=48.977273%2C8.2569&locale=de-DE&vehicle=motorcycle&weighting=curvature&elevation=false&layer=Omniscale

This does not:
http://localhost:8989/?point=48.977273%2C8.2569&point=48.978881%2C8.25488&locale=de-DE&vehicle=motorcycle&weighting=curvature&elevation=false&layer=Omniscale

Similarly, the error appears whenever it would be 'best' to take the ferry and as soon as the endpoints are set such that a route without the ferry is found to be better the request does not fail anymore.

The error occurs in AbstractBidirAlgo.calcPath() which is called on a DijkstraBidirectionRef instance.
However it does not appear in the call to runAlgo(), but in the call to extractPath().

Apparently, the edge representing the ferry (edgeId=5877) is considered in both directions (from node 31864 to 31907 and vice versa) by the routing algorithm. To be more precise, with my limited understanding of the details of the Graph representation, I think the riversides are connected in both directions because an EdgeExplorer with baseNode 31907 returns an EdgeIterator that has edge 5877 with adjNode 31864 and an EdgeExplorer with baseNode 31864 returns an EdgeIterator that has edge 5877 with adjNode 31907. I do not know if these IDs are fully determined by the osm data, but I hope you get the idea.

Therefore I think the problem could be related to:

encoder.isForward(queryGraph.getEdgeIteratorState(5877, 31864).getFlags()); //false encoder.isForward(queryGraph.getEdgeIteratorState(5877, 31907).getFlags()); //true

i.e. the encoder says that the edge 5877 can only be taken in one direction (?) while the routing algorithm considers both directions.

If someone could give some advice I would try to make a unit test with a very small Graph that still captures the problem. My idea is to simply 'copy' the full Graph in a very small region around the ferry, but I am not so sure about the best way to do this. Basically I expect that a single edge that has the same properties as the ferry in the full graph might already reveal a bug causing this problem.

[karussell]

Thanks for the investigation! Picking just a small area can be done with the 'export' button on osm.org then copy the 'map' file into 'map.osm' and gzip it (so that the repo holds only a few more bytes). But even better would be indeed a unit tests to keep everything slightly more lean

I do not know if these IDs are fully determined by the osm data

no, the differ for every import and are kind of 'array indices' (having the nice property of being consecutive instead of with holes like the OSM IDs). See here and here for some insights

i.e. the encoder says that the edge 5877 can only be taken in one direction (?)

That is indeed strange. Would you mind to make sure that the IDs are real edge and node IDs and no virtual IDs? (see the explanations in the two links)

[boldtrn]

Thanks for investigating. This is the ferry http://www.openstreetmap.org/way/3500103

Right now I cannot see any issues with the tags of the ferry. The only interesting part is the TMC.

[easbar]

Ok thank you. I managed to reproduce the error with a very small graph (4 nodes) by exporting some OSM data in a very small region around the ferry section. Also I am running the routing algorithm between real nodes and I am not using the QueryGraph at all. I would still like to create the Graph using the Java API without importing the real OSM data. When I tried to do this I found that the Graph created from the OSM data looks like this:

2 0-3 (f: true, b: true)
0 0-1 (f: true, b: true) // A
1 1-2 (f: true, b: true)
0 1-0 (f: false, b: true) // B
1 2-1 (f: true, b: true)
2 3-0 (f: true, b: true)

Here the format is: edgeId baseNode-adjNode, f and b show the output of iter.isForward(encoder)
and iter.isBackward(encoder) (I use an EdgeIterator iter to iterate over the edges of each node).

This seems to be very strange to me, because the second and fourth lines (marked as A and B) seem to contradict: 'A' says edge 0 (which is the ferry) is an undirected edge 0<->1 while 'B' says that edge 0 is a directed edge 0->1.

Using the BaseGraph.edge() method I did not even manage to create such a Graph by hand (without reading it from the .osm file), I think because EdgeAccess.internalEdgeAdd() connects the nodes in a consistent way.

If my assumption that this Graph is invalid is correct I think two things need to be done: 1) create the above Graph in code (probably using some very low level methods) and use it for a unit test that should assert that this Graph gets rejected, 2) find out why this Graph gets created from the OSM data.

[karussell]

Oh, that looks suspicious. Would you mind to create a pull request with the OSM data creating this graph? This way I can debug it easily and see how to create this graph by hand and what is going on here.

This looks like a bug maybe where we invert the edge flags. Maybe the result of the relative small duration for the ferry or related to similar issues #367, #657, #523, #178

Using the BaseGraph.edge() method I did not even manage to create such a Graph
by hand (without reading it from the .osm file),
I think because EdgeAccess.internalEdgeAdd() connects the nodes in a consistent way.

OSMReader is using the normal API, no magic should happen here.

[easbar]

Yes the flags of the edge seem to be wrong. I could reproduce the weird graph by setting the flags the way they are set within OSMReader when the original data is read. See my code here: #703, the OSM data is included

[karussell]

Please let me know if #711 fixes the problem here for you.

[boldtrn]

I cannot reproduce the error using #711, so this seems to be the valid fix, thanks :)..