You got it, the level is implicit in the ordering. You'll see this behavior in a few spots in the codebase - IDs are implied by positions in lists, rather than explicitly stored.
daniel > On Jul 12, 2016, at 8:35 AM, Francis Giraldeau <[email protected]> > wrote: > > Le mar. 12 juil. 2016 à 09:02, Daniel Patterson <[email protected] > <mailto:[email protected]>> a écrit : > Francis, > > Yes, it's a bidirectional Dijkstra search. The Wikipedia page for CH > describes it, so I won't repeat it here: > https://en.wikipedia.org/wiki/Contraction_hierarchies#Querying > <https://en.wikipedia.org/wiki/Contraction_hierarchies#Querying> > > > OK, I think I get it. In the graph preprocessing, shortcut edges are added to > the edges representing the streets. The relaxation selects edges (including > shorcuts) that converges to the goal, such as A*. Of course, the largest > shortcut is taken first. However, I was expecting that EdgeData contains a > "level" field or a reference to the children, but it is not (i guess to > reduce memory usage). I will have a second look at UnpackPath and the > Contractor to understand the implicit hierarchy (shortcuts edges at a given > level have greater ids than their child level?). > > "Core nodes" are uncontracted nodes. `osrm-contract` has the option to not > fully contract the edge-based graph (using the `--core` command-line > parameter). In this case, the search needs to be modified when it comes > across nodes that are uncontracted. The purpose of this feature is to allow > faster pre-processing, at the expense of query-time performance. > > If you don't use the `--core` parameter, everything gets contracted, and > there are no core nodes. > > Thanks Daniel for this enlightenment. > > Francis > -- > Francis Giraldeau > _______________________________________________ > OSRM-talk mailing list > [email protected] > https://lists.openstreetmap.org/listinfo/osrm-talk
_______________________________________________ OSRM-talk mailing list [email protected] https://lists.openstreetmap.org/listinfo/osrm-talk
