[GraphHopper] Question on PrepareContractionHierarchies

[Peter K]

There is indeed no need for the super call - fixed.
Also the preparation now seems to be >5% faster(for germany)! cool &
thanks :) !

Regards,
Peter.

> Hi Peter,
>
> yes, this is related to the principle of CH, which I understand.
> I was focusing on the conditions actually tested by the class
> LevelEdgeFilterCH .
>
> I do not understand the inheritance to LevelEdgeFilter and the call to
> the super the the accept method,
> but since it is very deep into the code, I wanted to know if there is
> something I do not understand wrt the invariants of the
> PrepareContraction algorithm: eg: can the level of a node be negative?
>
> Here is the accept method of LevelEdgeFilterCH.
> I've put some comments with //// to point the lines related to my
> question.
>
>         public final boolean accept( EdgeIterator iter )
>         {
>             if (!super.accept(iter))  ////here we check the accept
> condition of LevelEdgeFilter
>             {
>                 return false;
>             }
>             ////at this point, we can go up or equal in the hierarchy,
> not strictly down
>             // ignore if it is skipNode or a endNode already contracted
>             int node = iter.getAdjNode();
>             ////in the test below, we ensure that we will stay at
> level zero in the hierarchy,
>             ////meaning that we can only go to non-contracted nodes,
> so what's the point of the call to super here above?
>             return avoidNode != node && graph.getLevel(node) == 0;
>         }
>
>
> regards
> --
> Renaud
>
>
> Le 2/10/2013 13:23, Peter K a écrit :
>> 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
>>
>>
>>
>> _______________________________________________
>> GraphHopper mailing list
>> GraphHopper at openstreetmap.org
>> https://lists.openstreetmap.org/listinfo/graphhopper
>
>
> -- 
> *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/143defd3/attachment.html>