Error for building 'big' network with germany-latest.osm.pbf (seemingly caused by turn-restrictions)

[SRN1973]

I realized that r5r that builds on r5 does not write back a calculated network.dat / respectively fails in the network building process when the input files cover a whole country. (If I try the same for a small subset e.g. the city of Hamburg than r5r works as described and expected).

Trying to isolate the error, I got following answer from the r5r programmers which solved the problem for me (nevertheless I feel that it schould be corrected in r5):

"This is definitely an upstream bug in R5, and it has to do with turn restrictions, If you don't care about turn restrictions (which really only matter for driving, and to a lesser extent biking, but you can always walk your bike), you can use osmconvert with the --drop-relations option to remove them from your PBF. Then R5R should build the network, albeit without information on turn restrictions."

By the way I encounter a similar error when I try to build the Graph for the newer versions of the Open Trip Planner, too (as such I suspect it might be the same cause)

OPERATING SYSTEM:

Ubuntu 20.04.1 LTS
RAM: 1 TB
120 cernels

INPUT FILES:

germany-latest-osm.pbf (https://download.geofabrik.de/europe/germany-latest.osm.pbf)
[I already tried several dumps form different dates of the germany-latest-osm.pbf]
-GTFS files (whole public transport for Germany):
https://download.gtfs.de/germany/fv_free/latest.zip
https://download.gtfs.de/germany/nv_free/latest.zip
https://download.gtfs.de/germany/rv_free/latest.zip

COMMAND TO BUILD AND SAVE THE GRAPH:

java -Xmx500g -jar /usr/local/lib/R/site-library/r5r/jar/r5-v6.0.1-2-gf44e585-all.jar point --build

ERROR MESSAGE:
...
16:17:11.702 [main] WARN com.conveyal.r5.streets.StreetLayer - Did not find from/to edges for restriction 4429939, skipping
16:17:11.702 [main] WARN com.conveyal.r5.streets.StreetLayer - Did not find from/to edges for restriction 4429940, skipping
16:17:11.702 [main] WARN com.conveyal.r5.streets.StreetLayer - Did not find from/to edges for restriction 4429941, skipping
16:17:11.702 [main] WARN com.conveyal.r5.streets.StreetLayer - Did not find from/to edges for restriction 4429942, skipping
16:17:11.777 [main] ERROR com.conveyal.r5.streets.StreetLayer - Invalid turn restriction 4437683, does not have from, to and via, skipping
16:17:11.780 [main] ERROR com.conveyal.r5.streets.StreetLayer - Turn restriction 4437852 has multiple 'from' members, skipping.
16:17:11.780 [main] ERROR com.conveyal.r5.streets.StreetLayer - Turn restriction 4437855 has multiple 'from' members, skipping.
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index -1 out of bounds for length 17384613
at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64)
at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70)
at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248)
at java.base/java.util.Objects.checkIndex(Objects.java:372)
at java.base/java.util.ArrayList.get(ArrayList.java:459)
at com.conveyal.r5.streets.StreetLayer.applyTurnRestriction(StreetLayer.java:896)
at com.conveyal.r5.streets.StreetLayer.lambda$loadFromOsm$1(StreetLayer.java:374)
at java.base/java.util.stream.ForEachOps$ForEachOp$OfRef.accept(ForEachOps.java:183)
at java.base/java.util.stream.ReferencePipeline$2$1.accept(ReferencePipeline.java:177)
at java.base/java.util.Iterator.forEachRemaining(Iterator.java:133)
at java.base/java.util.Spliterators$IteratorSpliterator.forEachRemaining(Spliterators.java:1801)
at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:484)
at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:474)
at java.base/java.util.stream.ForEachOps$ForEachOp.evaluateSequential(ForEachOps.java:150)
at java.base/java.util.stream.ForEachOps$ForEachOp$OfRef.evaluateSequential(ForEachOps.java:173)
at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
at java.base/java.util.stream.ReferencePipeline.forEach(ReferencePipeline.java:497)
at com.conveyal.r5.streets.StreetLayer.loadFromOsm(StreetLayer.java:374)
at com.conveyal.r5.streets.StreetLayer.loadFromOsm(StreetLayer.java:205)
at com.conveyal.r5.transit.TransportNetwork.fromFiles(TransportNetwork.java:142)
at com.conveyal.r5.transit.TransportNetwork.fromFiles(TransportNetwork.java:201)
at com.conveyal.r5.transit.TransportNetwork.fromDirectory(TransportNetwork.java:235)
at com.conveyal.r5.point_to_point.PointToPointRouterServer.main(PointToPointRouterServer.java:92)
at com.conveyal.r5.R5Main.main(R5Main.java:32)

[abyrd]

Thanks for the report @SRN1973, hope to look into this soon.

[SRN1973]

...The above described problem still persits. I am still unable to build the network with tha latest germany-latest-osm.pbf (https://download.geofabrik.de/europe/germany-latest.osm.pbf) without removing the turn restrictions prior to the network building process. I think this is a major issu as this prevents to properly use any applications building on R5 therefore I would be very pleased if you would address the problem at last .... it was reportet more than one year ago now and I can not see any improvement yet.

[LeLunZ]

@abyrd also still having the problem. It also fails for smaller parts of Germany when using two osm files (of Germany) from Geofabrik with the merge function of osmium.

So it also happens for smaller files and I think not only Germany. I come across this regularly. As I currently don't have a problem with dropping all turn restrictions, I am doing that for now. But that shouldn't be the solution :)

[abyrd]

Thanks again @LeLunZ and @SRN1973 for reporting your observations.

First, please be aware that R5 is developed primarily as a component of Conveyal's accessibility analysis system. The software is shared with the world under an open source license to ensure transparency around our methods, and to share building blocks which may be useful for researchers. While you are welcome to reuse the software, we must prioritize problems directly affecting or reported by our customers, and do not always have time to research problems encountered by people reusing the software in other contexts.

The error you're seeing seems to be caused by a way referencing a node that is not present in the input data. When OSM data are cropped to a geographic area (or otherwise filtered), the cropping process may retain elements (relations or ways) referencing other elements (ways or nodes) that are outside the selected geographic area. For example a turn restriction relation could overlap the cropping area, but reference a way that is outside the cropping area. Most cropping tools have options to track the referenced entities and ensure referenced entities are included even if they spill outside the border. We always enable such features when cropping OSM data, and extract services like Geofabrik would also do this. We very regularly use Geofabrik exports and have never run into the problem you report.

So I'm not sure why this is happening, but it may well be due to an error in our code that applies turn restrictions, triggered by some specific pattern present in this input data. It would not truly fix the underlying problem, but a simple check for missing referenced nodes could just drop the turn restriction and at least prevent the crash, allowing your build to complete. I will work on a patch to that effect.

Here are a few more notes I took down while exploring this problem:

Note that the size of this PBF file is on the extreme high end of what we would encounter and R5 is not generally tested on such large inputs. This is about four times bigger than the largest file I'd regularly use (full Netherlands) and 10-15 times bigger than OSM data typically used with R5. So it's conceivable that there are problems purely due to the size or quantity of entities - things like identifier or array index overflows - which we have not caught because they do not come up in normal usage. Quite a lot of design decisions in R5 were made for metropolitan scale planning and analysis, meaning the scale of a single large employment basin. For example travel times (including transfers and waits) over two hours have historically been considered out of scope. Working on geographic areas as large as all of Germany may well break some assumptions and lead to intractable computations. Of course you are welcome to try, but this is pushing the limits beyond what it was designed and tested for.

Files that are so large usually consist mostly of data that are not used at all by R5. There have been jokes about renaming OpenStreetMap OpenBuildingMap because in some countries the streets (which we would use for routing) are only a small part of the data, with buildings making up the majority. This is the case in the Netherlands and probably also in Germany. The documentation for Conveyal's accessibility analysis system contains some tips on filtering the data to keep only the parts that you need: https://docs.conveyal.com/prepare-inputs#filtering

I tried filtering this way with osmium. On my 7 year old laptop, this took less than 40 seconds and reduced my germany-latest.pbf file from 3.7GB to 974MB, avoiding the need for R5 to interpret about 74% of the source data. This pre-filtering can be quite helpful because it avoids R5 loading and indexing millions and millions of buildings that will then be thrown away. Loading this PBF file took about 3 minutes, although the total build process is still quite long at about 20 minutes before it hits the problematic turn restriction.

The command that I used was osmium tags-filter germany-latest.osm.pbf w/highway w/public_transport=platform w/railway=platform w/park_ride r/type=restriction -o filtered.osm.pbf which should retain not only the entities with those tags, but all other entities referenced by them. So if a turn restriction references ways, and those ways reference nodes, everything should be included (see https://docs.osmcode.org/osmium/latest/osmium-tags-filter.html).

This part of the build process may be significant for the problem at hand:

[main] INFO c.c.r.s.TarjanIslandPruner - Removed 5190088 strong component (islands) with fewer than 40 vertices for mode CAR in 3.593sec. 5548136 vertices removed.

Across all the modes (walking, bicycle, and car) over 7 million small areas of the graph were removed because they were completely disconnected from the rest of the street network . If this is done incorrectly, or if certain indexes are built after this operation, it's possible that turn restrictions are still referencing ways that were removed as part of these disconnected subgraphs. The way they are removed is supposed to avoid such problems, but this is worth keeping in mind as a possible underlying source of the problem.

[abyrd]

I patched the vertex lookups to fail cleanly with a log message when the vertex is not found. Then I re-ran the build, changing StreetLayer#loadFromOsm() so it calls loadFromOsm(osm, false, false); with removeIslands set to false. This skips the whole pruning process but the problematic vertex lookup is still hit, indicating that pruning was not the culprit. The vertex lookup fails gracefully and the build completes.

So I don't yet know why it can't find this particular from vertex, but there were already many other such cases detected for via nodes. Dropping these problematic restrictions will at least avoid an annoying failure after 20 minutes of network building.