[GraphHopper] Question on PrepareContractionHierarchies

[Renaud De Landtsheer]

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


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