Why MultiTreeSPEntry.totalWeight and involved summation is necessary? about openrouteservice HOT 5 CLOSED

Hi Peter,
this summation is used in the compareTo method of MultiTreeSPEntry. The sum is used here to be consistent with SPTEntry.compareTo. I do not really recall where this was used, but I'm sure it is used somewhere. In SPTEntry, the weights are compared. In MultiTreeSPEntry, there are multiple weights, but we need one boolean as result of the comparison, therefore we sum over all weights of the MultiTreeSPEntry and compare the sums. If you have a good idea, I'm happy to avoid this. Need to look into the code too to check where the compare is actually used.

from openrouteservice.

Try removing this and it will still work.

Need to look into the code too to check where the compare is actually used

I didn't find anything

from openrouteservice.

The compareTo method is used when inserting entries into the prioQueue in java.util. The SPEntry uses this as well. Not sure about the inner workings of the queue, but shouldn't this be done correctly? What happens when the prioQueue is not ordered by weight? Would it be possible to remove the compareTo method of SPTEntry then as well?

from openrouteservice.

I don't think we need a queue as we explore "everything" reachable with CH (I might be wrong here) and as long as we have a proper update mechanism of suboptimal weights (which we seem to have).

We could use a simple stack or list. IMO the weight does not matter. Again you can try if you replace the totalWeight with something completely different and it will still work correctly (the tests would be handy here ;)).

I first thought "hey summation of something completely unrelated (weights to different locations) does not make sense and max(weight_i) is more meaningful". And yes, value=max(weight_i) was working but so do all other procedures including value=0...

from openrouteservice.

Sorry, I have to take back the argument that nothing changes if we change the order (or replace the queue with a list). With max(weight) it gets slower (1.2x) and with weight=0 it gets significantly slower (7x), but correctness seems not affected. Will have to read again the papers why this is necessary for a speedup, probably the update state skips lots of uninteresting sitations? But why not weight+=weight*weight or something else?

from openrouteservice.