[OSRM-talk] Questions about internals

Francis Giraldeau 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
é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
>
>
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20160712/6debce86/attachment.html>


More information about the OSRM-talk mailing list