MultiTreeSPEntryItem parent variable

Kia ora!

Local Java implementation on M1 Mac.

Could somebody please explain to me what the MultiTreeSPEntryItem.parent item is, and under which circumstances it could remain null during/after a MatrixRequest? Approximately 25% of my distance vector contains -1 values, and I believe it is because:

sptItem.getParent() != null in the calcValues method of the MultiTreeMetricsExtractor class.

But why? Are the two points on disconnected graphs? If so, how can I confirm this?

When constructing MultiTreeSPEntry objects, I’ve found that a large fraction of loop interations (~75%) trigger the continue block (i.e. if the weight is infinity and the parent is non-null). Is this ratio a coincidence, do we think?

This question is an attempt to fragment my core problem, here.

Appreciate your help, and sorry for spamming your forum.


The MultiTreeSPEntryItem.parent points to the parent node in the matrix search ‘tree’ and should not be null if there is a path from source to target. Likewise, a value of -1 in the matrix response indicates that no path was found. The graph might have multiple disconnected components. This might happen, e.g. on one-way-streets or highway lanes leading out of the boundary of the OSM extract or roads crossing the antimeridian. I would double-check the following:

  • Are the coordinates given in the right order (lon, lat)?
  • Can a path between source and target of the -1 entries be found when requesting a route instead of a matrix?
    • If no:
      • Does it help to increase the maximum_search_radius parameter in the config?
      • Are there reasons to believe the graph has multiple components?
    • If yes:
      • Does it work with smaller matrices?
      • Does it help to increase the maxiumum_visited_nodes parameter in the config?

Note, that the war-file needs to be repackaged if you change config settings.


1 Like

Kia ora, Sascha. Thank you for getting back to me.

To step through your points:

  • The points are given in the correct order, yes (providing <lat, lon> fails to generate points inside the bounding box required by ORS). Still need to figure out how to change the mapped region.
  • With regards to generating a route between the points that generate a matrix result of -1, no, I cannot generate routes. Further:
    • Changing the search radius to an absurdly large value does not solve my problem. The same applies to the maximum number of waypoints, etc.
    • I believe the cause comes down to an issue you raised in the first paragraph: the routes generated between the source and target extend beyond the bounds of the graph. Having a more articulate RouteNotFoundException in the RoutingProfileManager class would greatly improve debugging capacity, here.

While I need to develop a workaround for this in the long run (likely to generate points in a smaller region than that I have mapped), changing the graph of focus to the area I’m currently interested in has eliminated this error. I can generate 5000 points in its region, and generate a distance matrix with no -1 values.

I really appreciate your help.

Hi @makalakalak,

that might just be a difference between the area ors is built with and the area you are doing the requests in? I’m not sure i understood all of your setup, but if it works in the “region you have mapped”(?) and the points for the failing requests were outside that region, probably ors did just not build with what you wanted…

In that case it might just be a config issue, where it doesn’t respect your pbf file.
Also if that’s the case your ors-config.json (or if you run with docker, the docker-compose.yml) you are using would help identify the problem.

Best regards

Hi amandus,

This was the point of my final paragraph. If I use ORS to build Region A, and generate points within Region B (a small subset of Region A), the graph of Region A should extend to ensure there are feasible paths within Region A to all points in Region B.

I have done enough debugging now to be confident that it is not a config issue. I have also generated the fastest path between the coordinates in question in OSM and Google Maps, both of which show the path extending beyond the bounds of the BBox defined in ORS (of the Heidelberg data).