[PPL-devel] PowerSet operations (Was: Re: Compiling PPL under Cygwin?)

[Roberto Bagnara]

Goran Frehse wrote:
> congratulations on the new version. I will try it asap, and I'm 
> particularly excited about the faster map_dimensions routine.

Hello Goran,

yes, the speedup for map_dimensions() is significant.

> If I understand correctly, the PowerSets are finite unions of polyhedra, 
> so I guess I could use those instead of my own implementation. We'll see 
> who's are faster ;-) But seriously, this is great.

They are finite sets of polyhedra that are non-redundant.  This means
that a powerset cannot contain the empty polyhedron or two polyhedra
that are one the subset of the other.

> Do you plan to implement all boolean operations (union, intersection, 
> difference)?

Here I am not sure I understand your needs, that is, if you need
something like std::set<C_Polyhedron, ...> or what we call
Polyhedra_PowerSet.  In the first case, a strict weak ordering
is required, and this is not available (any idea on how to realize
it efficiently is very welcome).  In the latter case, we have

   void upper_bound_assign(const PowerSet& y);

that computes the union, then it eliminates the redundant elements.
We have

   void meet_assign(const PowerSet& y);

(which we may rename before the next release) that computes all the
intersections of a polyhedron from *this with a polyhedron from y,
then it eliminates the redundant elements from the collection so obtained.

Difference has still to be implemented: it will compute a non-redundant
set of polyhedra such that their union is the difference of the unions
of the polyhedra contained in its arguments.

Are these the operations you need?
All the best,

     Roberto

-- 
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:bagnara at cs.unipr.it