<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">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.<div class=""><br class=""></div><div class="">daniel<br class=""><div class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Jul 12, 2016, at 8:35 AM, Francis Giraldeau <<a href="mailto:francis.giraldeau@gmail.com" class="">francis.giraldeau@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class="gmail_quote"><div dir="ltr" class="">Le mar. 12 juil. 2016 à 09:02, Daniel Patterson <<a href="mailto:daniel@mapbox.com" class="">daniel@mapbox.com</a>> a écrit :<br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class="">Francis,<div class=""><br class=""></div><div class=""> Yes, it's a bidirectional Dijkstra search. The Wikipedia page for CH describes it, so I won't repeat it here: <a href="https://en.wikipedia.org/wiki/Contraction_hierarchies#Querying" target="_blank" class="">https://en.wikipedia.org/wiki/Contraction_hierarchies#Querying</a></div><div class=""><br class=""></div></div></blockquote><div class=""><br class=""></div><div class="">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 <span style="line-height:1.5" class="">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?).</span></div><div class=""><br class=""></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word" class=""><div class=""></div><div class=""> "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.</div><div class=""><br class=""></div><div class=""> If you don't use the `--core` parameter, everything gets contracted, and there are no core nodes.</div></div></blockquote><div class=""><br class=""></div><div class="">Thanks Daniel for this enlightenment.</div><div class=""><br class=""></div><div class="">Francis</div></div></div><div dir="ltr" class="">-- <br class=""></div><div data-smartmail="gmail_signature" class=""><div dir="ltr" class="">Francis Giraldeau</div></div>
_______________________________________________<br class="">OSRM-talk mailing list<br class=""><a href="mailto:OSRM-talk@openstreetmap.org" class="">OSRM-talk@openstreetmap.org</a><br class="">https://lists.openstreetmap.org/listinfo/osrm-talk<br class=""></div></blockquote></div><br class=""></div></div></body></html>