[PPL-devel] [Fwd: Re: A question on powerset operations]

25 Oct 2004

      -------- Original Message --------
Subject: Re: A question on powerset operations
Date: Sun, 24 Oct 2004 23:32:36 -0400
From: Hosung Song hosungs@umich.edu
To: Roberto Bagnara bagnara@cs.unipr.it
References: 402A51EB.60609@andrew.cmu.edu 402AA44B.2010702@cs.unipr.it 402A77E8.2000907@andrew.cmu.edu 41249897.9060800@cs.unipr.it 412CFC0C.7040501@ece.cmu.edu 41339C73.3000003@cs.unipr.it Pine.LNX.4.58.0410240107150.1142@smtp.eecs.umich.edu 417B5E19.6080202@cs.unipr.it
Prof. Bagnara,
Thank you very much. Encouraged by your prompt feedback, I decided to
try to implement my own C interface for those polyhedra powerset
operations. All I need is just three operations: creation of an empty
powerset, add a disjunct, and finally check if a polyhedron is contained
(geometrically covered) by a powerset. (Maybe I would need more later.)
Since my C++ knowledge is very shallow, it took quite a long time to
figure out how (after all, most answers I found from the ppl_c.cc),
especially how to deal with the compile errors due to differences in
Polyhedron and NNC_Polyhedron. Polyhedra_PowerSet is defined as a
template class, and I just don't know much how to deal with one
effectively. I tried various different ad hoc trials, and it turns out
that there's a simple casting operation, which I found in another
portion of ppl_c.cc. Anyway, I know my implementation may be too
specific for my purpose, but I'd like you to look over it and give me
some confirmation. It seems that the integration works well for my
project right now, but who knows if my implementation is just completely
bogus. I'm attaching the diffs for interfaces/C/ppl_c.cc and
interfaces/C/ppl_c.h.in. All diffs are just additions to the original
ppl_c.cc and ppl_c.h.in. I know they are really tiny, but it took me a
novice C++ user quite a few hours. Any of your comments would be greatly
appreciated. I'd be happy if you somehow incorporate this kind of C
interface in the new release. In fact, I thought of coding this as a
separate source file, maybe under my project directory, because I didn't
want to modify the PPL distribution. However, my lack of knowledge on
how to compile it and manage as a library prohibited that approach. If
you could give me a pointer on general methods of making C interface for
library written in C++, I would certainly try that.
Thanks always.
Hosung
Roberto Bagnara wrote:
...
Hosung Song wrote:
...
Would you verify the execution result of the following simple program?

#include    <ppl.hh>
#include    <iostream>
using namespace Parma_Polyhedra_Library;
using namespace IO_Operators;
using namespace std;
int
main(void)
{
        Variable x(0);
    ConSys cs1, cs2, cs3, cs4;
    cs1.insert(x >= 0);
    cs1.insert(x <= 4);
    cs2.insert(x >= 2);
    cs2.insert(x <= 6);
    cs3.insert(x >= 1);
    cs3.insert(x <= 5);

    NNC_Polyhedron ph1(cs1), ph2(cs2), ph3(cs3);
    cout << "ph1 : " << ph1 << endl;
    cout << "ph2 : " << ph2 << endl;
    cout << "ph3 : " << ph3 << endl;

    Polyhedra_PowerSet<NNC_Polyhedron> ps12(2,

Polyhedron::EMPTY);
        ps12.add_disjunct(ph1);
        ps12.add_disjunct(ph2);
        cout << "ps12 : " << ps12 << endl;
    if (check_containment(ph3, ps12))
            cout << "ph3 is contained in ps12..." <<

endl;
        else
                cout << "ph3 is not contained in ps12..."
<< endl;
}

What I'm interested in is to check whether a polyhedron is contained by
the union of a set of polyhedrons. So I played around with just
Polyhedra_PowerSet class, by converting the single polyhedron to a
set of a single polyhedron. I got some unexpected results, so I looked
into the codes Polyhedra_PowerSet... and it seems like 
check_containment()
is just the function I needed. I tried that and my result is still a
little unexpected. Well, that's maybe only from my understanding, and 
that
might be quite wrong. In the above example, ph1 is 0 <= x <= 4, and 
ph2 is
2 <= x <= 6. ps12 is the union of ph1 and ph2. ph3 is 1 <= x <= 5. So, it
looks like ph3 is contained in ps12. However, my execution result is the
other way. I used "g++ test.cc -lppl -lgmpxx -lgmp" and the running 
result
is "ph3 is not contained in ps12..." Am I missing some basic 
understanding
here? I suppose my understanding of the geometrical inclusion
(containment or covering, whatever) might be seriously flawed. I'd try to
trace the execution to understand the function
completely, but I would greatly appreciate your quick insightful
advice. Thanks always.
Dear Hosung,
you have indeed been bitten by a bug in PPL 0.6.1.  This was fixed on
September 15th, 2004, but we forgot to add a mention of it to our bugs
page (http://www.cs.unipr.it/ppl/Bugs/).  I have done it now, and there
you will also find a patch you can apply to PPL 0.6.1.  Sorry about that.
By the way, with lots of interesting new features and bug fixes, the
forthcoming release (0.7) contains several changes to the
Polyhedra_PowerSet template class (starting from its name, where the
's' is now lowercase).
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@cs.unipr.it

35a36,39
> /* shpin add begin */
> #include "Polyhedra_PowerSet.defs.hh"
> #include "algorithms.hh"
> /* shpin add end */
296a301,305
> /* shpin add begin */
> typedef Polyhedra_PowerSet<NNC_Polyhedron> NNC_Polyhedra_PowerSet;
> DECLARE_CONVERSIONS(NNC_Polyhedra_PowerSet)
> /* shpin add end */
> 
2112a2122,2153
> /* shpin add begin */
> int
> ppl_new_NNC_Polyhedra_PowerSet_empty_from_dimension(ppl_NNC_Polyhedra_PowerSet_t* pps,
> 						    ppl_dimension_type d) try {
> 	*pps = to_nonconst(new NNC_Polyhedra_PowerSet(d, Polyhedron::EMPTY));
> 	return 0;
> }
> CATCH_ALL
> 
> int
> ppl_NNC_Polyhedra_PowerSet_add_disjunct(ppl_NNC_Polyhedra_PowerSet_t ps,
> 					ppl_const_Polyhedron_t ph) try {
> 	NNC_Polyhedra_PowerSet& pss = *to_nonconst(ps);
> 	const NNC_Polyhedron& phh
> 		      = *static_cast<const NNC_Polyhedron*>(to_const(ph));
> 
> 	pss.add_disjunct(phh);
> 	return 0;
> }
> CATCH_ALL
> 
> int
> ppl_NNC_Polyhedron_is_contained_in_NNC_Polyhedra_PowerSet(ppl_const_Polyhedron_t ph,
> 							  ppl_const_NNC_Polyhedra_PowerSet_t ps) try {
> 	const NNC_Polyhedron& phh
> 		      = *static_cast<const NNC_Polyhedron*>(to_const(ph));
> 	const NNC_Polyhedra_PowerSet& pss = *to_const(ps);
> 	return check_containment(phh, pss) ? 1 : 0;
> }
> CATCH_ALL
> /* shpin add end */
> 
2167a2209,2212
> /* shpin add begin */
> DEFINE_PRINT_FUNCTIONS(NNC_Polyhedra_PowerSet)
> /* shpin add end */
> 

352a353,356
> /* shpin add begin */
> PPL_TYPE_DECLARATION(NNC_Polyhedra_PowerSet);
> /* shpin add end */
> 
2218a2223,2236
> /* shpin add begin */
> int
> ppl_new_NNC_Polyhedra_PowerSet_empty_from_dimension __P((ppl_NNC_Polyhedra_PowerSet_t* pps,
> 							 ppl_dimension_type d));
> 
> int
> ppl_NNC_Polyhedra_PowerSet_add_disjunct __P((ppl_NNC_Polyhedra_PowerSet_t ps,
> 					     ppl_const_Polyhedron_t ph));
> 
> int
> ppl_NNC_Polyhedron_is_contained_in_NNC_Polyhedra_PowerSet __P((ppl_const_Polyhedron_t ph,
> 							       ppl_const_NNC_Polyhedra_PowerSet_t ps));
> /* shpin add end */
> 
2254a2273,2276
> /* shpin add begin */
> PPL_DECLARE_PRINT_FUNCTIONS(NNC_Polyhedra_PowerSet)
> /* shpin add end */
> 