[gecode-users] edge-finder propagator
Filip Konvička
filip.konvicka at logis.cz
Fri Aug 22 16:28:20 CEST 2008
Hi Jan,
> The implementation of the O(n^2) edge-finder of [Baptiste,Le Pape,
> Nuijten] seemed to us easier to implement than the O(n log n) algorithm
> of Vilim, which uses binary trees.
> So we chose the O(n^2), as it was the first propagator we were implementing.
>
> Maybe we should try to implement that O(n log n) version.
The binary trees are easy - implement them using vectors: compute the
next larger power of two (N), make a vector of N*2-1 items, the tree
leaves start at index N-1, parent node of node I is (I-1)/2.
In fact, efficient computation of the next power of two is what I can
share with you because it is already part of the FloatVar implementation
I posted earlier today: it is in float/float/bi/prop_linear.icc, look
for "namespace __Utils".
Theta-lambda trees are usable not just for propagators, but also for
branchings (you can easily compute firsts/lasts using theta-lambda trees).
Hope this helps,
Filip
More information about the gecode-users
mailing list