[gecode-users] Clockwise constraint

[Guido Tack]

Malcolm Ryan wote:

> On 03/06/2008, at 7:45 PM, Guido Tack wrote:
>
>> The problem is here: testing B.in(b) is linear time, so it's just as
>> expensive as finding a new b.
>
> Ah. Is there a way to iterate through the elements of B's domain in
> order in time proportional to the number of elements?

You can even iterate through the ranges (the continuous intervals of a  
domain) in time proportional to the number of ranges, using a  
ViewRanges<IntView> iterator, e.g.

> Eek. I'm still new to C++, and that code is rather scary.
>
> I'm figuring that I'll have to make a reified ternary propagator along
> the lines of ReBinaryPropagator in propagator.icc and then implement
> the methods as shown in eq.icc.

Yes, but ReTernaryPropagator is not predefined in Gecode.  But you can  
take ReBinaryPropagator (from int/propagator.icc) as a starting point,  
just extend it with a third view in the obvious way.

> One question, how do I tell it to do the rewrites with conjunctions or
> disjunctions:
>
> If X = true, post A < B and B < C
> if X = false, post A > B or B > C

For X=true, you post two Le propagators.  You post the first one using  
GECODE_ES_CHECK(Le<IntView>::post...), and the second one using  
GECODE_REWRITE(...).

For X=false, you have to create two new Boolean variables, turn them  
into views, and then post B<=A or C<=B, using two ReLq propagators and  
a BinOrTrue propagator.

> Hmm, I really don't think I understand your code well enough to do
> this properly. I'm trying to implement a reified A < B < C operator,
> but I'm really lost.

You should probably start by writing some really simple propagator,  
like equality (without reification), to get an idea how things work in  
Gecode.  Maybe you then have some more specific questions and we can  
help you better.

Cheers,
	Guido