[OSRM-talk] Questions about internals

[Daniel Patterson]

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>

  "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.

daniel


> On Jul 12, 2016, at 6:51 AM, Francis Giraldeau <francis.giraldeau at gmail.com> wrote:
> 
> Hello!
> 
> I'm digging into the internals of OSRM. The Processing Flow wiki page is quite informative, here are few additional questions. I can edit the wiki with the answers.  
> 
> About the routing algorithm: when inspecting RoutingStep, there are forward and backward heap, so it looks like bidirectional Dijkstra, but the documentation states that the algorithm is based on contraction hierarchies. What's the trick?
> 
> In the code, we see that some nodes are "core nodes". What does that mean?
> 
> Thanks for your help!
> 
> 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/6f3ca1e2/attachment.html>