Routing with CH in graphopper 0.12 doesn't find shortest path

[buma1]

I’m upgrading from Graphopper 0.6 to GH 0.12. I have a suite of 84049 tests which compares routing results between improvements of routing algorithm.
Passing a test means that geometry of the result is close enough according to Hausdorff distance.
All tests were done with exact same PBF file with elevation.
With Bidirectional Dijkstra on CH graphs and Astar on graphs without CH.
On new GH only node based traversal is used.

We use Graphopper for routing but have custom encoder and weighting function.

After upgrading to GH 0.12 93.65% of tests passes. But some have weird results.
For example this one: Blue is new version. Red is old one. Blue pin is origin.

OSM
Path with extra 90° turn in it is longer and has larger weight then one without.
And the problem is if I set waypoints so that new version returns same path as old, weight of this path is lower then the path it found by itself. Difference in weight is 6.
This can only be reproduced with full planet import. Even importing just the Italy problem doesn’t appear.

During debugging I saved all edges for which weight was calculated during path search for this example:

It seem some VirtualEdgeIterator edges were traversed to Africa. In current GH version (0.6.0) this looks like this (red lines). They end somewhere in Russia. This happens in both cases correct and wrong in old and new.

Here are weights of edges. And path with 10+56=66 is taken over path with weight 60.

Distance of edges also look weird. Street edges look fine. But those long edges are 500km and more and have only distance of 5 or 58. Old GH is the same.

Here is even bigger problem:

OSM
Difference in weight is 5000 which is twice the weight in old version. New path is also longer has larger duration and has more uphill/downhill.
If we look in this example more:

A ----------------- B

A------x-----------B

A-B current 5883.979672842171
A-B new 11138.015028445223
A x B current 5883.966151234559
A x B new 5883.9663680501535

Disabling CH fixes most of this issues but can’t be used in practice.

Disabling CH doesn’t fix all problems. For example this one is strange:

OSM
Same distance/duration/uphill/downhill but weights differ for 2.6104560787819224. (New one is worse)

Retesting failing test cases with CH disabled fixes 60% of them.

Interestingly even in tests which have same results in geometry there is occasionally weight difference between versions (old GH vs new) from -10500 to 15211. Average difference is around 0. But there are 19-700 cases per sport where result is completely the same and weights differ. Sometimes they are better and sometimes worse. This also happens with CH disabled.

There are also some tests where origin/destination is snapped to different point in new version.

I assume that algorithm itself is fine but does anyone know what could be the issue in weighting for this weird results?

[easbar]

@buma1

Path with extra 90° turn in it is longer and has larger weight then one without.
And the problem is if I set waypoints so that new version returns same path as old, weight of this path is lower then the path it found by itself. Difference in weight is 6.
This can only be reproduced with full planet import. Even importing just the Italy problem doesn’t appear.

The blue path indeed looks wrong. This sounds like something goes wrong with CH shortcuts. When you specify the waypoint a (possibly) wrong shortcut is no longer used and the path is calculated correctly.

@buma1

It seem some VirtualEdgeIterator edges were traversed to Africa.

Are you sure these are virtual edges ? This would be very hard to understand for me. I assume these are shortcut edges (CHEdgeIteratorState).

@buma1

Here are weights of edges. And path with 10+56=66 is taken over path with weight 60.

Assuming the long red edges are CH shortcuts (which I think they are) their weight is certainly suspicious and should be much larger (and the same for distances).

@buma1

Same distance/duration/uphill/downhill but weights differ for 2.6104560787819224. (New one is worse)

@buma1

Interestingly even in tests which have same results in geometry there is occasionally weight difference between versions (old GH vs new) from -10500 to 15211. Average difference is around 0. But there are 19-700 cases per sport where result is completely the same and weights differ. Sometimes they are better and sometimes worse. This also happens with CH disabled.

The absolute value of the weight should not be too much of your concern and be treated rather like an internal number that can change between different GH versions.

@buma1

I assume that algorithm itself is fine but does anyone know what could be the issue in weighting for this weird results?

Maybe its just a blind guess, but considering that you say that the problem only happens for planet-wide imports my first guess is that the shortcut weights are somehow overflowing. The CH shortcut weight is limited to 31bits at the moment and as you saw for yourself the shortcut edges can be very long (spanning across continents). In theory such an overflow should not happen, but the weight should rather be truncated to the maximum value, but maybe something goes wrong here ? See this method:

graphhopper/graphhopper/blob/1abfbc3301b0f1d7f3e4610eb60b7c09340fe81d/core/src/main/java/com/graphhopper/storage/CHGraphImpl.java#L838-L869

The other interesting thing you could do is pick these long edges (that surprisingly have such a small weight) and take a look at their ‘skippedEdge1/2’ fields: These are edge ids of the underlying edges of the shortcuts and you can recursively take a look at these edges (using chGraph.getEdgeIteratorState(edgeId, Integer.MIN_VALUE) until you see the original edges. In any case the weight of the long edges must equal the sum of the weight of `skippedEdge1/2’. If that is not the case something must have gone wrong during the CH preparation.

Also maybe you should try GH 0.13 to make sure you are not facing a problem that already has been fixed.

And of course if you can share your custom encoder or weighting it would be much easier to analyze possible sources of error.

[karussell]

@buma1 interesting.

to what @easbar said.

@easbar

And of course if you can share your custom encoder or weighting it would be much easier to analyze possible sources of error.

Or can you reproduce the differences with a default FlagEncoder? If yes, please try 0.13 and see if you can still reproduce the differences.

Also please see Large distant searches by foot result in connection not found · Issue #1022 · graphhopper/graphhopper · GitHub and Distance of single edge restricted · Issue #435 · graphhopper/graphhopper · GitHub for related issues, but likely this is more a shortcut weight limitation/bug.

There are also some tests where origin/destination is snapped to different point in new version.

Can you reproduce this difference with a default FlagEncoder?

[easbar]

@karussell

Or can you reproduce the differences with a default FlagEncoder?

Oh yeah thats indeed the first thing you should try (run your tests with default encoder/weighting with 0.6 vs 0.12/13).

Btw I like the idea of comparing the Hausdorff distance of some set of paths between versions. Can you share some code that does this ?

[buma1]

Thank you both for quick answer. Those long edges are definitely VirtualEdges. Since they are VirtualEdgeIterator class, but are probably created from CHGraph.

I found out that I debugged geometry wrong since I saved base and adj node geometry for linestring coordinates if edgeState instanceof CHEdgeIteratorState in weighting. (since fetchWayGeometry doesn’t work for CH edges). This was also called for VirtualEdgeIterator class. And it seems those nodes are very different then what gets outputed with fetchWayGeometry.

This looks much better:

I’ll look into CH edges if they are close to overflow, or if weights of shortcuts sum to weight of edge.

@easbar Do you really think that weight of same results shouldn’t be very similar on same data? Since our flagEncoder and weighting function didn’t change. I would expect couple of percentage change since it seems some nodes have slightly different elevation sometimes.

I’ll try to reproduce with default FlagEncoder.

@karussell I tried to reproduce snapping to nodes with default FlagEncoder but wasn’t able to. It always snapped to same edges in both versions. It also happens very rarely in our version but I wasn’t able to reproduce it in pure GH. Which seems strange since the code for snapping is pure GH code even in our version and I haven’t been able to find any logic changes in Git logs between 0.6 and 0.12 in this part of the code.

[easbar]

@buma1

I found out that I debugged geometry wrong since I saved base and adj node geometry for linestring coordinates if edgeState instanceof CHEdgeIteratorState in weighting. (since fetchWayGeometry doesn’t work for CH edges). This was also called for VirtualEdgeIterator class. And it seems those nodes are very different then what gets outputed with fetchWayGeometry.

Not sure I fully understand what you mean, but if these ‘long’ edges are just the virtual edges, but drawn incorrectly this would explain their small weight+distance.

@buma1

@easbar Do you really think that weight of same results shouldn’t be very similar on same data? Since our flagEncoder and weighting function didn’t change. I would expect couple of percentage change since it seems some nodes have slightly different elevation sometimes.

Yeah, as long as you control the Weighting and FlagEncoder I see no real reason why the weight should change.

[karussell]

@easbar

Yeah, as long as you control the Weighting and FlagEncoder I see no real reason why the weight should change.

We likely changed internal storage stuff (IntsRef) and it is unlikely that we match everything identical especially since this is not required.

[buma1]

I did change in my own flagEncoder to use new IntsRef. The rest of it stayed the same.

I’m still working on replicating issue on graphopper but during debugging I found something else strange.

On short path I get same geometry with same distance/duration calculated elevation gain back but weight differ for 139. Which is a lot for a short path.

I found that the issue is in origin (blue pin) edge. This VirtualEdge has different elevation in baseNode then in node you get in fetchWayGeometry.

Since slope is calculated based on that elevation weight is then different.

Green edge on top is geometry I get in fetchWayGeometry on this edge.
Red edge is what I get if I just print base and adj nodes locations
Is this normal for VirtualEdgeIterator edges and VirtualEdgeIteratorState edges?

This is graph without CH edges so I’m not sure why is this long edge here. Same thing happens in old version only edge is a little shorter.

I can’t get source edge. I tried to get it like that in Weighting function:

public double calcWeight(EdgeIteratorState edgeState, boolean reverse, int prevOrNextEdgeId) {
EdgeIteratorState edge = edgeState.detach(false);
if (edge instanceof VirtualEdgeIteratorState) {
int origEdgeId = ((VirtualEdgeIteratorState) edge).getOriginalEdgeKey();
EdgeIteratorState origEdge = graph.getEdgeIteratorState(origEdgeId, Integer.MIN_VALUE);

But origEdge is edge somewhere completely different in Austria.

[easbar]

@buma1

int origEdgeId = ((VirtualEdgeIteratorState) edge).getOriginalEdgeKey();

There is a difference between the edge key and the edge id! The edge key contains information about the direction of the edge. You need to transform this edge key into an edge id like this:

int origEdgeId = GHUtility.getEdgeFromEdgeKey(....getOriginalEdgeKey());

[buma1]

@easbar: Thank you. Now results make much more sense.

I wrote out all edges for which calcWeight in scoring function is called during search and I don’t find any difference in weight of edges between old and new version.

But in new version I get correct result if I disable stall_on_demand. Since correct edge gets removed since it is stallable for some reason.
I think that stall_on_demand should also be disabled in CH generation to be completely correct. Since option for stall on demand is also during CH preparation. I’ll keep looking.

And I couldn’t reproduced the error with pure GH.

[buma1]

Bug also doesn’t appear if I apply this commit which patches some CH stall edge cases and leave stall_on_demand enabled.

I’ll have to run full test suite but at least for one sport it seems fixed.

[easbar]

@buma1

Bug also doesn’t appear if I apply this commit which patches some CH stall edge cases and leave stall_on_demand enabled.

This indeed was a (very rare) bug that existed in 0.12 but should be fixed in 0.13. Maybe your special weighting/encoder makes this bug more likely in your project, that it was in core 0.12. You should definitely run your tests with stall on demand disabled (and maybe also with algorithm=dijkstra (to make sure the Dijkstra CH algorithm is selected) to track down the cause of the error.

Hmm no actually I was thinking about this fix: Fixes wrong routing occurring when stall on demand is used with virtual via-nodes. by easbar · Pull Request #1581 · graphhopper/graphhopper · GitHub and it was already included in 0.12.