<div dir="ltr"><div class="gmail_quote"><div dir="ltr">Le mar. 12 juil. 2016 à 09:02, Daniel Patterson <<a href="mailto:daniel@mapbox.com">daniel@mapbox.com</a>> a écrit :<br></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">Francis,<div><br></div><div>  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">https://en.wikipedia.org/wiki/Contraction_hierarchies#Querying</a></div><div><br></div></div></blockquote><div><br></div><div>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">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><br></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"><div></div><div>  "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><br></div><div>  If you don't use the `--core` parameter, everything gets contracted, and there are no core nodes.</div></div></blockquote><div><br></div><div>Thanks Daniel for this enlightenment.</div><div><br></div><div>Francis</div></div></div><div dir="ltr">-- <br></div><div data-smartmail="gmail_signature"><div dir="ltr">Francis Giraldeau</div></div>