-------- 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 */