POST error : No path found due to maximum nodes exceeded 3000000

Directions API
1

Hi, I got this error with the payload below. Do you have any hint of why it is happening ?

Payload :

{"points":[[19.714527,49.238613],[19.722558,49.2288],[19.747748,49.214158],[19.74984,49.220441],[19.749968,49.22087],[19.750043,49.221158],[19.750574,49.220604],[19.750902,49.220439],[19.751132,49.220422],[19.75286,49.220229],[19.753128,49.219966],[19.753546,49.219756],[19.754597,49.21861],[19.756657,49.217047],[19.758406,49.21601],[19.760391,49.217587],[19.762397,49.218673],[19.765418,49.221129],[19.76671,49.222454],[19.767375,49.223137],[19.767483,49.223645],[19.7673,49.225113],[19.76759,49.226437],[19.768513,49.228175],[19.769162,49.23028],[19.767467,49.232859],[19.766775,49.235969],[19.766807,49.236585],[19.762222,49.232562],[19.754769,49.23002],[19.746115,49.234811],[19.734007,49.239586],[19.711284,49.244207]],"profile":"hike","points_encoded":false,"elevation":true,"locale":"fr","details":["hike_rating","road_class","road_environment","surface","road_access","track_type","foot_network"],"ch.disable":true,"custom_model":{"priority":[{"if":"hike_rating >= 4","multiply_by":"0"}]}}

Error :

com.graphhopper.util.exceptions.MaximumNodesExceededException
"No path found due to maximum nodes exceeded 3000000"

Regards, Olivier

2

This looks like some bug and it shouldn’t happen for this short route. We’ll investigate.

3

Thanks :slight_smile:

4

I think I understand the problem. Have a look into this link to GH Maps and select hike_rating in the bottom right elevation widget. You see that in the middle there is a hike_rating of 4, then 0 and then followed by hike_rating=4.

So this means your custom model blocks the access for the hike_rating==4 segments but creates an “island” of hike_rating==0 where routing is again possible but only within this island (consisting of a single way). And now the algorithm tries to find a connection from e.g. the start towards this island via exploring the “outside”/“mainland” but it won’t find a connection and so it will stop when the maximum junction count (“visited nodes”) of 3M is reached.

If you think about it it makes sense as there could be a tunnel or whatever strange path towards an Island and so depending on your use case you’ll either have to remove locations from the separated islands or use a low number like 0.01 instead of 0 in the custom model.

Do you understand what I mean :slight_smile: ?

We could also put this custom model on the server side and do a special pre-processing (“island removal”), which then changes the snapping of markers of the “island” to the “mainland”.

5

So basically if a custom model blocks a road (weight zero) that is required to connect the start and destination points the routing algorithm tries to find a way until it hits some limit (like the maximum visited nodes), even though the points aren’t connected by a finite weight path. The quick solution is using a small but finite weight instead of zero like @karussell explained already.

Another solution could be applying a maximum weight limitation to the routing algorithm that is based on the beeline distance, at least if a factor of 0 appears in the custom model. For example if the maximum (finite) weight of a custom model (per meter) was 0.1 and the beeline distance was 1000m the algorithm could stop at something like weight=500 (the equivalent to five times the beeline distance times the maximum weight), because very likely there is no connection between the points.

6

I think the small but finite solution is not acceptable since we don’t want our users to take a way too difficult, event in fallback.

By the way I am ok with the fact that there is no result available, maybe it would be better to have a clearer error, like, “No routing available for these parameters” or something like that.

7

I had an idea and we are investigating a better solution, i.e. the snapping of the via point would “probe” the area and determine that it cannot find a route to the other via points (i.e. a separated island/subnetwork) leading to a snapping outside of this subnetwork and probably doing what your intentions are: avoiding this area (without an error).

8

Would you prefer an immediate error, or do you expect the route to start/end at a nearby location that is connected? If your primary concern is that you are getting confused by the message "com.graphhopper.util.exceptions.MaximumNodesExceededException: No path found due to maximum nodes exceeded 3000000" you can just read this as ‘connection not found’, but I agree this might be misleading. Not sure if it would be of much help if we just changed the error message?

9

I think the message could be only “No path found” and this way a lot clearer while keeping the exception as it is, what do you think ?

10

Yes that would be great.

Would it be possible, if some via points are being ignored, to have this information somewere in the response ?

I encountered this problem already, if for example two following via points are one the same spot, they are deduped silently, leading that there is in snapped_waypoints less via points than those given to the api.

11

Do you have an example request where this is the case?