[GraphHopper] Reconnecting edges after the contraction

[Renaud De Landtsheer]

Le 28/10/2013 14:19, Peter K a écrit :
> The removal will especially improve query performance on Android, not 
> sure if there is a big difference for the contraction process or the 
> query performance on the server. So probably you do not need this 
> optimization at all.

Some exotic algorithm descend in the hierarchy instead of climbing,
and make use of a previous exploration to mark nodes to funnel the 
descending search.

> > My question is: to reconnect an edge, can I simply put is as head of 
> the list of edges leaving the node?
>
> Yes, this should work.

Thank you.

Just curious, when a new edge is created, it is always inserted at the 
end of this list,
as shown in the following code:

    private void connectNewEdge( int fromNodeId, int newOrExistingEdge )
     {
         long nodePointer = (long) fromNodeId * nodeEntryBytes;
         int edge = nodes.getInt(nodePointer + N_EDGE_REF);
         if (edge > EdgeIterator.NO_EDGE)
         {
             // append edge and overwrite EMPTY_LINK
             long lastEdge = getLastEdge(fromNodeId, edge);
             edges.setInt(lastEdge, newOrExistingEdge);
         } else
         {
             nodes.setInt(nodePointer + N_EDGE_REF, newOrExistingEdge);
         }
     }

Is there a reason for not inserting it at the beginning?
I guess there is something related to the specific context of this 
operation.

>
> Regards,
> Peter.
>
>
>> Hi Peter,
>>
>> I am playing with the code of your contractor, and I have a small 
>> question.
>>
>> The contractor can remove edges from lists of edges leaving a node if 
>> the flag removesHigher2LowerEdges is set.
>> This flag, when set, provides a quite important speedup to the 
>> contraction process.
>>
>> Sometime, you do not want this flag to be set, because you do not 
>> want edges to be disconnected, because you want to use some exotic 
>> algorithms. In such cases, the contraction is slower.
>>
>> I was wondering about disconnecting such edges always, and 
>> reconnecting them after the contraction is completed, to have a fast 
>> contraction, and have the desired graph in the end.
>> I am planning therefore to have a list of disconnected edges saved 
>> somewhere, and reconnecting them after the contraction.
>>
>> My question is: to reconnect an edge, can I simply put is as head of 
>> the list of edges leaving the node?
>>
>> Thank you.
>> -- 
>> *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


-- 
*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/20131028/f0eacfa7/attachment.html>