[gecode-users] IntSet question

[Gustavo Gutierrez]

Thank you very much Guido! just what I needed :) .

2010/8/2 Guido Tack <tack at gecode.org>

> Gustavo Gutierrez wrote:
> > Probably what I am going to ask is not useful or is just to much
> particular to my case that does not worth have it, however, I wouldn't
> hesitate to ask :).
> >
> > While writing a propagator I realized that keeping some state in it will
> lower the complexity. This propagator is on a finite set variable and what I
> does is to track "the new elements in the glb" and propagate according with
> its semantics. At the beginning to I was using an std::set to keep the "old
> values" and using it to compute the new elements:
> >
> > new elements = current glb \  old values
> >
> > The propagator was performing well but the memory consumption and the
> time to compute the intersection was quite high. After realizing that I
> start using an IntSet instead of a std::set to keep the data. The advantage
> is that the IntSet stores ranges and then is *hopefully* less memory hungry.
> There is also something nice, you can use all the iterators with them (range
> iterators). The only problem is that they are intended to be used only to
> represent variable domains in initializations or when posting constraints
> and this is reflected in the fact that they lack of "modification
> operations" in the API.
> >
> > In my case I have to copy construct all the time and this is of course
> time consuming but far better than my previous implementation. Now my
> question, sounds it very crazy or stupid to use the IntSet in this way?, if
> it does not, then it would be nice to provide an specialization (via
> inheritance, for instance) that allows this kind of use.  What do you think?
>
> Yes, that is very crazy :-)  However, there's a different data structure
> you can use in exactly the way you describe.  It's actually two data
> structures, LUBndSet and GLBndSet.  The difference is in the available
> operations: LUBndSet has intersectI and excludeI operations (i.e., it can
> shrink), and GLBndSet has an includeI operation (i.e., it can grow). These
> sets are used internally for implementing set variables. In your case, you'd
> use a GLBndSet (and includeI the current lower bound after each
> propagation).  There's an iterator called BndSetRanges that you can use on
> these sets.
> You should have a look at the IntersectionN propagator, it uses a LUBndSet
> to remember the intersection of all assigned variables it has seen so far
> (it will show you how to initialize and copy these sets).
>
> Cheers,
>        Guido
>
> --
> Guido Tack, http://people.cs.kuleuven.be/~guido.tack/
>
>
>
>
> _______________________________________________
> Gecode users mailing list
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users
>



-- 
Gustavo Gutierrez
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.gecode.org/pipermail/users/attachments/20100802/9c54cc44/attachment.htm>