[OSRM-talk] Questions about internals

[Daniel Patterson]

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 <francis.giraldeau at gmail.com> wrote:
> 
> Le mar. 12 juil. 2016 à 09:02, Daniel Patterson <daniel at mapbox.com <mailto: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 <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
> OSRM-talk at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20160712/dd49e86c/attachment.html>