Significant difference between TryCalculateWeight results for contracted and non-contracted graphs

[lukaskabrt]

I am using Itinero to calculate distance matrix among points and I have discovered, that in some cases there is a significant difference between results calculated using RouterDb with and without contracted graph. Tested on the latest stable version (1.5.0) and the latest pre-release version (1.6.0-pre19) with the same results.

Code to reproduce the issue:

class Program
{
    static void Main(string[] args)
    {
        RouterDb routerDb = new RouterDb();
        using (var stream = File.OpenRead("C:\\Temp\\OSM\\prague-small.osm.pbf"))
        {
            routerDb.LoadOsmData(stream, new LoadSettings { }, Vehicle.Car);
        }

        var router = new Router(routerDb);
        var profile = routerDb.GetSupportedProfile("car.shortest");

        var from = router.Resolve(profile, new Coordinate(50.13463848643f, 14.49010693683f));
        var to = router.Resolve(profile, new Coordinate(50.13450614509f, 14.4897319773f));

        var distanceMatrix = router.TryCalculateWeight(profile, router.GetDefaultWeightHandler(profile), new RouterPoint[] { from }, new RouterPoint[] { to }, new HashSet<int>(), new HashSet<int>());
        Console.WriteLine($"{distanceMatrix.Value[0][0]}m"); // prints 271.65m

        var route = router.Calculate(profile, from, to);
        Console.WriteLine($"{route.TotalDistance}m"); // prints 271.65m

        routerDb.AddContracted(profile);
        distanceMatrix = router.TryCalculateWeight(profile, router.GetDefaultWeightHandler(profile), new RouterPoint[] { from }, new RouterPoint[] { to }, new HashSet<int>(), new HashSet<int>());
        Console.WriteLine($"{distanceMatrix.Value[0][0]}m"); // prints 996.5m

        route = router.Calculate(profile, from, to);
        Console.WriteLine($"{route.TotalDistance}m"); // still prints 271.65m
    }
}

OSM file was downloaded from Geofabric a cropped with Osmosis.

osmosis --read-pbf "C:\Temp\OSM\czech-republic-latest.osm.pbf" --bounding-box top=50.15 left=14.45 bottom=50.11 right=14.53 --write-pbf "C:\Temp\OSM\prague-small.osm.pbf"

It is also attached to this issue prague-small.osm.pbf.zip

I think, this is different issue then #267 because route is calculated correctly in both cases, there is just difference in weights returned by TryCalculateWeight

[lukaskabrt]

Update: The problem is related to the edge based graph

• if I set ProcessRestrictions = false all distances are computed correctly
• if I set ProcessRestrictions = false and forceEdgeBased: true the error appears again

[lukaskabrt]

I was able to reproduce the problem on an even smaller network (just 3 vertices and 2 edges). See minimal-example.osm.pbf.zip

[xivk]

Can the above code be used to reproduce with the tiny network? If not can you share the code used to compare the timings on the smaller network? My time working on this is limited but I'll try to have a look asap.

Any info you can provide is useful, it looks like this is an issue specifically with the contracted edge-based network. Itinero will automatically create an edge-based contracted network if it encounters complex restrictions.

[lukaskabrt]

@xivk Yes, the same code with forceEdgeBased: true flag can be used to reproduce the issue with the tiny network. Absolute values of weights are little different than in the original post, but the problem is the same.

    class Program {
        static void Main(string[] args) {
            RouterDb routerDb = new RouterDb();
            using (var stream = File.OpenRead("C:\\Temp\\OSM\\minimal-example.osm.pbf")) {
                routerDb.LoadOsmData(stream, new LoadSettings { }, Vehicle.Car);
            }

            var router = new Router(routerDb);
            var profile = routerDb.GetSupportedProfile("car.shortest");

            var from = router.Resolve(profile, new Coordinate(50.13463848643f, 14.49010693683f));
            var to = router.Resolve(profile, new Coordinate(50.13450614509f, 14.4897319773f));

            var distanceMatrix = router.TryCalculateWeight(profile, router.GetDefaultWeightHandler(profile), new RouterPoint[] { from }, new RouterPoint[] { to }, new HashSet<int>(), new HashSet<int>());
            Console.WriteLine($"{distanceMatrix.Value[0][0]}m"); // prints 271.65m

            var route = router.Calculate(profile, from, to);
            Console.WriteLine($"{route.TotalDistance}m"); // prints 271.65m

            routerDb.AddContracted(profile, forceEdgeBased: true);
            distanceMatrix = router.TryCalculateWeight(profile, router.GetDefaultWeightHandler(profile), new RouterPoint[] { from }, new RouterPoint[] { to }, new HashSet<int>(), new HashSet<int>());
            Console.WriteLine($"{distanceMatrix.Value[0][0]}m"); // prints 996.5m

            route = router.Calculate(profile, from, to);
            Console.WriteLine($"{route.TotalDistance}m"); // still prints 271.65m
        }
    }

I also think it is an issue with edge-based contracted networks, but to tell the truth, I got lost in the graph representation and structures used in the algorithms, so I was unable to solve the problem myself.

[juliusfriedman]

I am also experiencing this, See #281

[juliusfriedman]

I think this was somewhat fixed in #302.

[juliusfriedman]

Triple confirmed, the lock issue seems to have fixed the route deviation! We are now analyzing to provide proof that the differences are with the multi threading, the way we are doing that is to analyze the points which are different and see if they are within the tolerances we provided to the engine. That would support why there were differences and where there were differences.

I will see if I can provide you with some good examples once we have completed the 4th review tomorrow.

[juliusfriedman]

I just noticed that your not using ParallelEnumerable here so the changes may have been fixed elsewhere in the develop branch. If I get some time I will see if I can create some unit tests for this using your code as an example to confirm or not.
We are still checking the files we created in parallel with their logs to see if we can confirm the differences seemed to be threading related.

[lukaskabrt]

Unfortunately it doesn't seem to be fixed ... if I download source code form #302 and try to run code from #293 (comment) to reproduce the bug, I still get different results for contracted and uncontracted graphs.

253.72285m
253.72287m
573.7m
253.72287m

[juliusfriedman]

Thanks, I will add a test for this when I can and attempt to debug further, sorry for the confusion. I have confirmed in parallel that my issues are gone however I am not using the TryCalculateWeight.

[juliusfriedman]

I added the test case and verify I get the same results as you do. I will take a look and see if I can see anything which causes this.

[juliusfriedman]

It seems like RouterExtensions.CalculateManyToMany is called which uses the VertexToVertexWeightAlgorithm, beyond that I don't have much at the moment but I can confirm that there is definitely a difference.

Also noting that TryCalculateWeight seems to fall into the path for HasNodeBasedGraph rather than HasEdgeBasedGraph once the graph is contracted.

[juliusfriedman]

@lukaskabrt, It seems the GetAugmentedWeightHandler doesn't exhibit this issue... I have updated the code to show and maybe I can also find the difference later on.

[juliusfriedman]

@xivk is it expected that the default weight handler would provide different results than that of the augmented? If not I can take a shot at trying to find out what the differences are there and making another PR

[juliusfriedman]

@lukaskabrt, I think I was able to fix it. I updated #302

All unit tests are still passing and your test now passes as well.

We will have to wait for @xivk to confirm but please do let me know if your still experiencing the issue and also do try the work around which is to use GetAugmentedWeightHandler

I am not sure if that code was supposed to be removed or if the logic in the VertexToVertex should have had some calls to IsLessThan.

We will have to wait for the author to confirm.

[lukaskabrt]

It seems to be fixed for the minimal repro case. But if I use larger network from the first comment (https://github.com/itinero/routing/files/4061607/prague-small.osm.pbf.zip) the issue is still there.

[juliusfriedman]

Have you also tried using the GetAugmentedWeightHandler?

Can you share a test case for that issue and I will see what I can find.

[lukaskabrt]

I haven't tried GetAugmentedWeightHandler, but over the weekend I might have a time to try it.

You can easily reproduce the issue with the source code from #293 (comment) and https://github.com/itinero/routing/files/4061607/prague-small.osm.pbf.zip file instead of minimal-example.osm.pbf.

[juliusfriedman]

I see so essentially just change the pbf file for the one linked instead of the minimal and I should be able to reproduce with the same test case?

I will give it a try when time permits. Especially because I want to give the author a chance to take a look. In the meantime please do try GetAugmentedWeightHandler as it seemed to return the correct results even without my modifications. The author would have more insight into that than I currently do.

If and when I find anything further I will let you guys know and thanks for your help!

[lukaskabrt]

I see so essentially just change the pbf file for the one linked instead of the minimal and I should be able to reproduce with the same test case?

Yes, just change path to the other PBF file.

[juliusfriedman]

I was unable to repo the problem using GetAugmentedWeighHandler, The only change required to use it instead of the other is to access the Value property for the weight.

I also notice that DefaultWeightHandler uses ContractedEdgeDataSerializer while the WeightHandler uses EdgeDataSerializer that seems backwards at first glace but @xivk would probably know better than me.

[juliusfriedman]

There seems to be an issue with CalculateManyToMany and possibly ManyToManyWeightsBidirectionalDykstra. I resolved the issue by instead running the ManyToMany algorithm and it seems to resolve both tests cases.

Addressed in #302

Please let me know if you find out different.

@xivk please let me know if this is the appropriate fix