Le mar. 12 juil. 2016 à 09:02, Daniel Patterson <[email protected]> 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
_______________________________________________ OSRM-talk mailing list [email protected] https://lists.openstreetmap.org/listinfo/osrm-talk
