[GraphHopper] Question on PrepareContractionHierarchies

[Peter K]

Hi Renaud,

the LevelEdgeFilterCH (additionally to the hierarchy filtering) just
makes sure that the specified node is excluded from the dijkstra. If the
dijkstra finds a shorter path (without that node) we do not need the
shortcut. E.g.:

   |  |
..-A--B--C
   |     |
   \-D-E-/

To contract B we introduce several shortcuts. One of them is the
shortcut from A to C. But we can avoid that if we find a shorter way
from A to C without B.

Regards,
Peter.

> Dear Peter,
>
> I have a question on the PrepareContractionHierarchies algo.
>
> There is a class LevelEdgeFilterCH, which is used in the Dijkstra to
> check if the shortest path between two non-contracted nodes pass
> through a node that we want to contract.
>
> My point is that this class inherits from LevelEdgeFilter, and uses
> its check,
> and I do not understand why; I fear that there is something I do not
> understand.
>
> LevelEdgeFilter prevents us from strictly going down in the hierarchy.
> and LevelEdgeFilterCH check this condition first.
> If it is OK, it further check that the neighbour node is not
> contracted, that is: of level zero.
> Knowing that the source node is also non-contracted, this second check
> seems stronger than the first check inherited from the LevelEdgeFilter
> class.
>
> Thank you for your help.
>
> -- 
> *Renaud De Landtsheer, Ir, Phd*
> Sr R&D Engineer
> CETIC
> Rue des Frères Wright, 29/3
> B-6041 Charleroi
> Phone: +32 71 490 754
>
>
>
>
> _______________________________________________
> GraphHopper mailing list
> GraphHopper at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/graphhopper

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20131002/0ed61f1c/attachment.html>