{"action":"created","issue":{"url":"https://api.github.com/repos/graphhopper/graphhopper/issues/1247","repository_url":"https://api.github.com/repos/graphhopper/graphhopper","labels_url":"https://api.github.com/repos/graphhopper/graphhopper/issues/1247/labels{/name}","comments_url":"https://api.github.com/repos/graphhopper/graphhopper/issues/1247/comments","events_url":"https://api.github.com/repos/graphhopper/graphhopper/issues/1247/events","html_url":"https://github.com/graphhopper/graphhopper/pull/1247","id":283389173,"number":1247,"title":"(WIP) Edge-based Contraction Hierarchies and Turncost support","user":{"login":"ammagamma","id":17603532,"avatar_url":"https://avatars1.githubusercontent.com/u/17603532?v=4","gravatar_id":"","url":"https://api.github.com/users/ammagamma","html_url":"https://github.com/ammagamma","followers_url":"https://api.github.com/users/ammagamma/followers","following_url":"https://api.github.com/users/ammagamma/following{/other_user}","gists_url":"https://api.github.com/users/ammagamma/gists{/gist_id}","starred_url":"https://api.github.com/users/ammagamma/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ammagamma/subscriptions","organizations_url":"https://api.github.com/users/ammagamma/orgs","repos_url":"https://api.github.com/users/ammagamma/repos","events_url":"https://api.github.com/users/ammagamma/events{/privacy}","received_events_url":"https://api.github.com/users/ammagamma/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":12,"created_at":"2017-12-19T22:25:32Z","updated_at":"2018-02-02T09:56:23Z","closed_at":null,"author_association":"CONTRIBUTOR","pull_request":{"url":"https://api.github.com/repos/graphhopper/graphhopper/pulls/1247","html_url":"https://github.com/graphhopper/graphhopper/pull/1247","diff_url":"https://github.com/graphhopper/graphhopper/pull/1247.diff","patch_url":"https://github.com/graphhopper/graphhopper/pull/1247.patch"},"body":"This PR shall enable turn costs for contraction hierarchies as described in this [paper](https://pdfs.semanticscholar.org/4aa9/65d323ccb8b9e7c71de77f910900ff69a773.pdf) by R. Geisberger and C.Vetter.\r\n\r\nThis PR has the same goal as #912, but follows a rather different approach and is much closer\r\nto what is described in the paper. Several of the problems described in #912 are addressed here\r\nlike multiple loops/p-turns, u-turn detection and fixed size turn cost tables. Fundamentally\r\nthis is realized by storing two additional integers per shortcut edge, which are set to the\r\nIDs of the first and last original edges that are skipped by the shortcut. Doing this requires\r\nmany adjustments of the CH query algorithm (when expanding nodes and when checking bridge nodes where forward and backward searches meet) as well as the node contraction / shortcut searches.\r\n\r\n### What is working so far:\r\n\r\n* (Hopefully) error-free implementation of the node contraction and query algorithms. There are extensive tests that try to cover all edge cases, some of them compare the query results with the standard Dijkstra implementation for many queries and node contraction orders. So far it looks like all situations are handled correctly. The U-Turn based traversal mode is not yet supported and requires further changes and tests (if it should be supported), see comment below. \r\n\r\n### Next steps:\r\n\r\n* Integration with previous (node-based) CH code (`NodeContractor` and `PrepareContractionHierarchies`) and support for automatic node ordering. So far the nodes can only be ordered in random order or ordered by ID, but this makes no sense for larger graphs. So far `EdgeBasedNodeContractor` does not return any metrics that can be used for node ordering heuristics.\r\n\r\n* Integration with Graphhopper API and integration tests, see what the performance is like.\r\n\r\n* Performance optimizations: There are many obvious things that can be improved:\r\n\r\n   - Probably the most important thing is reusing data structures between the different witness path searches, something like `DijkstraOneToMany`. For the turn replacement difference algorithm that is being used we need a way to initialize the search with edges adjacent to the start node and it must be possible to initialize them with arbitrary weights.\r\n\r\n   - Tuning of the node contraction parameters. The above mentioned paper describes a different metric than the one that is currently used for example. We can start with something simple (edge difference / quotient only for example) and see what the performance is like.\r\n\r\n   - Minor stuff: See some of the todos in the code, there is definitely room for improvements.\r\n\r\n\r\n"},"comment":{"url":"https://api.github.com/repos/graphhopper/graphhopper/issues/comments/362540228","html_url":"https://github.com/graphhopper/graphhopper/pull/1247#issuecomment-362540228","issue_url":"https://api.github.com/repos/graphhopper/graphhopper/issues/1247","id":362540228,"user":{"login":"ammagamma","id":17603532,"avatar_url":"https://avatars1.githubusercontent.com/u/17603532?v=4","gravatar_id":"","url":"https://api.github.com/users/ammagamma","html_url":"https://github.com/ammagamma","followers_url":"https://api.github.com/users/ammagamma/followers","following_url":"https://api.github.com/users/ammagamma/following{/other_user}","gists_url":"https://api.github.com/users/ammagamma/gists{/gist_id}","starred_url":"https://api.github.com/users/ammagamma/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/ammagamma/subscriptions","organizations_url":"https://api.github.com/users/ammagamma/orgs","repos_url":"https://api.github.com/users/ammagamma/repos","events_url":"https://api.github.com/users/ammagamma/events{/privacy}","received_events_url":"https://api.github.com/users/ammagamma/received_events","type":"User","site_admin":false},"created_at":"2018-02-02T09:56:23Z","updated_at":"2018-02-02T09:56:23Z","author_association":"CONTRIBUTOR","body":"**Update**: I have made some improvements. Besides some minor improvements local searches are now cancelled entirely as soon as it is clear that the target edge can not be reached via the node to be contracted, it is checked if a shortcut that is about to be added exists already and I implemented the node contraction priority calculation as given in the paper.\r\n\r\nFor [Berlin](http://download.geofabrik.de/europe/germany/berlin.html) the contraction now takes about 4 minutes on my machine (about 15min previously) and I measured an average query time of about 13ms. For [Bremen](http://download.geofabrik.de/europe/germany/bremen.html)) the contraction takes about 25s contraction time and the queries run about 3ms.\r\n\r\nHowever, the number of shortcuts is still very high and I am struggling to find a way to reduce it. For Berlin I am getting about 430k and for Bremen about 110k. The high density of shortcuts edges seems to limit the performance of both the graph contraction and the routing queries. Especially towards the end of the contraction there seem to be just too many shortcut edges that get introduced. Right now I am still hoping to find an error that is responsible for the large number of shortcuts, but having checked many things I am slowly running out of ideas what could be wrong.\r\n\r\nHere is a list of things I have already looked into so far (but did not help much at least when I tried them): \r\n\r\n1.  Use an array- (instead of map-)based version for WitnessPathFinder similar to DijkstraOneToMany -> not too much improvement and does not help with the number of shortcuts (currently not commited in this branch)\r\n\r\n2. node priority calculation -> I am using edge differences instead of the edge quotients mentioned in the paper, which seem to perform worse. I have not spent too much time trying different linear combinations of the different terms, but whenever I tried varying them it seemed like not too much is changing. --> I suspect this can be used to further improve performance, but this probably is not the main issue.\r\n\r\n3. Try different witness path search algorithms as implemented in `EdgeBasedNodeContractor`. The turn replacement algorithm should already give the least amount of shortcuts, but the `SimpleSearch` is simpler and takes less effort. However, right now I think both variants introduce 'too many' shortcuts and take too long to prepare the graph. I was also thinking about a hybrid where we do the 'costly' turn replacement search or the 'fast' simple search depending on some metric, but right now I do not think this is the bottleneck.\r\n\r\n4. Collect all shortcuts to be inserted for a given node and do a batch insert instead of adding them one by one (this is currently done in the node-based version of CH) --> did not seem to help much, because I am checking for duplicate shortcuts when the shortcuts are inserted anyway.\r\n\r\n5. One thing I am doing different than in the paper is that for loop shortcuts I recursively add some helper shortcuts to be able to unpack them later. However, I found that the number of these helper shortcuts is rather small and I (no longer) think that this is the root of the problem of so many shortcuts.\r\n\r\n6. Limiting of local searches: We can not cancel the search entirely, because the witness path search needs to 'find' the shortcut connection (via loops). However, we can discontinue all active leafs of the search that do not belong to a possible connection consisting only of the in- and out edges that are currently checked and loops at the node to be contracted. This is done when the number of settled edges exceeds a certain number (not given in the paper). If this number is too low some witnesses will not be found, but even increasing the limit to a very high number did not significantly reduce the number of shortcuts. So again, I think there is room for some improvement by tuning this parameter, but I could not get a significant improvement doing so so far.\r\n\r\n7. Using fwd/bwd flags on shortcut edges. Right now all shortcuts are used with only the fwd flag. If we use fwd/bwd flags we can potentially reduce the number of EdgeIteratorStates by 50% , which should be beneficial, but it requires some changes, because we then need a more involved way to decide what the 'first' and 'last' original edges of a shortcut are (similar to the edge-key calculation where the two node ids of an edge are used to decide if it is fwd or bwd). So this would definitely improve performance I think, but it does not reduce the 'real' number of shortcuts.\r\n\r\n8. One interesting thing I found was in https://github.com/graphhopper/graphhopper/pull/1247/commits/382432d5a09f9613bee6a8a9ac5f52fd7647e499 where I disabled a previously introduced simple check for duplicate neighbor updates. Disabling this check improved the query time by a factor of 13 (!) on the map for Bremen without changing the number of shortcuts very much (less than 1% difference). I currently have no understanding why this makes such a large difference.\r\n\r\nIt could be that the rather poor performance can only be improved by a combination of all of the above things, but I am still hoping there is some kind of bottleneck that can be fixed or I am simply forgetting something important. \r\n\r\n@karussell (or anybody else interested) maybe you could have a look and notice something ? Not sure how familiar you are with the turncost version of CH, but maybe there is something that was crucial for node-based CH that I am missing ?\r\n\r\nFor testing I am currently using the CHMeasurement class, which performs the contraction for given OSM data and compares some random queries with normal Dijkstra. It usually also logs some errors, where the calculated weights are different, but they should be very small (I think some rounding issue that I did not find the reason for yet). Afterwards the query time is also measured. During the contraction some statistics are logged (for example we see that a lot of time is spent on neighbor updates and the number of shortcuts that are checked rises dramatically at the end).\r\n\r\n"}}
{"actor":{"display_login":"ammagamma"}}