[OSRM-talk] Questions about internals
francis.giraldeau at gmail.com
Tue Jul 12 14:35:19 UTC 2016
Le mar. 12 juil. 2016 à 09:02, Daniel Patterson <daniel at mapbox.com> a
> Yes, it's a bidirectional Dijkstra search. The Wikipedia page for CH
> describes it, so I won't repeat it here:
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
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.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the OSRM-talk