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 _______________________________________________ Gecode users mailing list [EMAIL PROTECTED] https://www.gecode.org/mailman/listinfo/gecode-users
