[PPL-devel] integer versus rational solutions

[P M Hill]

On Wed, 8 Jul 2009, Tobias Grosser wrote:

> Hi,
>
> I just tried to use the ppl to work with integer polyhedron, however I
> am stuck with the examples in the documentation for the
> Partial_Reduced_Product:
>
> http://www.cs.unipr.it/ppl/Documentation/user/ppl-user-0.10.2-html/classParma__Polyhedra__Library_1_1Partially__Reduced__Product.html#_details
>
> ---------------------------------------------------------------------
> In all the examples it is assumed that the template R is the
> No_Reduction<D1, D2> class and that variables x and y are defined (where
> they are used) as follows:
>          Variable x(0);
>          Variable y(1);
>
> Example 1
>        The following code builds a direct product of a Grid and NNC
>        Polyhedron, corresponding to the positive even integer pairs in
>        R^2, given as a system of congruences:
>
>          Congruence_System cgs;
>          cgs.insert((x %= 0) / 2);
>          cgs.insert((y %= 0) / 2);
>          Partially_Reduced_Product<Grid, NNC_Polyhedron, No_Reduction<D1, D2> >
>            dp(cgs);
>          dp.add_constraint(x >= 0);
>          dp.add_constraint(y >= 0);
>
> Example 2
>        The following code builds the same product in R^2:
>        Partially_Reduced_Product<Grid, NNC_Polyhedron, No_Reduction<D1, D2> > dp(2);
>          dp.add_constraint(x >= 0);
>          dp.add_constraint(y >= 0);
>          dp.add_congruence((x %= 0) / 2);
>          dp.add_congruence((y %= 0) / 2);
> ---------------------------------------------------------------------

Hi Tobias,

>
> I would like to create the set of even positive integer pairs, so I
> tried Example 1 and 2. With both I have the same problems.
>
> 1. D1 and D2 are not defined:
>
> test.cpp:9: error: 'D1' was not declared in this scope
> test.cpp:9: error: 'D2' was not declared in this scope
>
> So I replace D1 with "Grid" and D2 with "NNC_Polyhedron"

That is correct. They have to be specified.

>
> 2. An exception when adding constrains:

Only equalities can be added to a product of a grid and polyhedron,
best to use refine_with-...() methods here.

>
> terminate called after throwing an instance of 'std::invalid_argument'
>  what():  PPL::Grid::add_constraint(c):
> c is not an equality constraint.
>
> So I removed the positive constraints.
>
> 3. An exception when adding congruences:
>
> terminate called after throwing an instance of 'std::invalid_argument'
>  what():  PPL::NNC_Polyhedron::add_congruence(cg):
> cg is a non-trivial, proper congruence.
>
> Do you have any idea what I did wrong?

Yes, you have to use refiine_with_constraint()
and refine_with_congruence();

The add methods cannot be used here unless the constraint/congruence is 
an equality.

There is also another problem in your code in that you cannot build the 
product directly from the congruences as they cannot be add'ed to the 
NNC_Polyhedron component. Instead, first build a grid from the congruences 
and then build the product using the grid.

Here is my code, based on your examples, that works here:

-------------------------------------------------

  /*
    Example 1
  */

           Congruence_System cgs;
           cgs.insert((x %= 0) / 2);
           cgs.insert((y %= 0) / 2);
           Grid gr(cgs);
           Partially_Reduced_Product<Grid, NNC_Polyhedron,
                                     No_Reduction<Grid, NNC_Polyhedron> >
             dp(gr);
           dp.refine_with_constraint(x >= 0);
           dp.refine_with_constraint(y >= 0);

--------------------------------------------------

  /*
Example 2
  */

        Partially_Reduced_Product<Grid, NNC_Polyhedron,
                                  No_Reduction<Grid, NNC_Polyhedron> >
          dp(2);

        dp.refine_with_constraint(x >= 0);
        dp.refine_with_constraint(y >= 0);
        dp.refine_with_congruence((x %= 0) / 2);
        dp.refine_with_congruence((y %= 0) / 2);

--------------------------------------------------

I used here the master branch of the git repository head version. The 
latest developments for the PPL domain for partially reduced products are 
in the products branch.

HTH. Let me know if you have further queries wrt this domain, we will glad 
to help.

Pat