Cython wrapper for the Parma Polyhedra Library (PPL)¶
The Parma Polyhedra Library (PPL) is a library for polyhedral computations over \(\QQ\). This interface tries to reproduce the C++ API as faithfully as possible in Cython/Sage. For example, the following C++ excerpt:
Variable x(0);
Variable y(1);
Constraint_System cs;
cs.insert(x >= 0);
cs.insert(x <= 3);
cs.insert(y >= 0);
cs.insert(y <= 3);
C_Polyhedron poly_from_constraints(cs);
translates into:
sage: from sage.libs.ppl import Variable, Constraint_System, C_Polyhedron
sage: x = Variable(0)
sage: y = Variable(1)
sage: cs = Constraint_System()
sage: cs.insert(x >= 0)
sage: cs.insert(x <= 3)
sage: cs.insert(y >= 0)
sage: cs.insert(y <= 3)
sage: poly_from_constraints = C_Polyhedron(cs)
The same polyhedron constructed from generators:
sage: from sage.libs.ppl import Variable, Generator_System, C_Polyhedron, point
sage: gs = Generator_System()
sage: gs.insert(point(0*x + 0*y))
sage: gs.insert(point(0*x + 3*y))
sage: gs.insert(point(3*x + 0*y))
sage: gs.insert(point(3*x + 3*y))
sage: poly_from_generators = C_Polyhedron(gs)
Rich comparisons test equality/inequality and strict/non-strict containment:
sage: poly_from_generators == poly_from_constraints
True
sage: poly_from_generators >= poly_from_constraints
True
sage: poly_from_generators < poly_from_constraints
False
sage: poly_from_constraints.minimized_generators()
Generator_System {point(0/1, 0/1), point(0/1, 3/1), point(3/1, 0/1), point(3/1, 3/1)}
sage: poly_from_constraints.minimized_constraints()
Constraint_System {-x0+3>=0, -x1+3>=0, x0>=0, x1>=0}
As we see above, the library is generally easy to use. There are a few pitfalls that are not entirely obvious without consulting the documentation, in particular:
There are no vectors used to describe
Generator
(points, closure points, rays, lines) orConstraint
(strict inequalities, non-strict inequalities, or equations). Coordinates are always specified via linear polynomials inVariable
All coordinates of rays and lines as well as all coefficients of constraint relations are (arbitrary precision) integers. Only the generators
point()
andclosure_point()
allow one to specify an overall divisor of the otherwise integral coordinates. For example:sage: from sage.libs.ppl import Variable, point sage: x = Variable(0); y = Variable(1) sage: p = point( 2*x+3*y, 5 ); p point(2/5, 3/5) sage: p.coefficient(x) 2 sage: p.coefficient(y) 3 sage: p.divisor() 5
PPL supports (topologically) closed polyhedra (
C_Polyhedron
) as well as not neccesarily closed polyhedra (NNC_Polyhedron
). Only the latter allows closure points (=points of the closure but not of the actual polyhedron) and strict inequalities (>
and<
)
The naming convention for the C++ classes is that they start with
PPL_
, for example, the original Linear_Expression
becomes
PPL_Linear_Expression
. The Python wrapper has the same name as the
original library class, that is, just Linear_Expression
. In short:
- If you are using the Python wrapper (if in doubt: thats you), then you use the same names as the PPL C++ class library.
- If you are writing your own Cython code, you can access the
underlying C++ classes by adding the prefix
PPL_
.
Finally, PPL is fast. For example, here is the permutahedron of 5 basis vectors:
sage: from sage.libs.ppl import Variable, Generator_System, point, C_Polyhedron
sage: basis = range(0,5)
sage: x = [ Variable(i) for i in basis ]
sage: gs = Generator_System();
sage: for coeff in Permutations(basis):
....: gs.insert(point( sum( (coeff[i]+1)*x[i] for i in basis ) ))
sage: C_Polyhedron(gs)
A 4-dimensional polyhedron in QQ^5 defined as the convex hull of 120 points
The above computation (using PPL) finishes without noticeable delay (timeit measures it to be 90 microseconds on sage.math). Below we do the same computation with cddlib, which needs more than 3 seconds on the same hardware:
sage: basis = range(0,5)
sage: gs = [ tuple(coeff) for coeff in Permutations(basis) ]
sage: Polyhedron(vertices=gs, backend='cdd') # long time (3s on sage.math, 2011)
A 4-dimensional polyhedron in QQ^5 defined as the convex hull of 120 vertices
DIFFERENCES VS. C++
Since Python and C++ syntax are not always compatible, there are necessarily some differences. The main ones are:
- The
Linear_Expression
also accepts an iterable as input for the homogeneous cooefficients. Polyhedron
and its subclasses as well asGenerator_System
andConstraint_System
can be set immutable via aset_immutable()
method. This is the analog of declaring a C++ instanceconst
. All other classes are immutable by themselves.
AUTHORS:
- Volker Braun (2010-10-08): initial version.
- Risan (2012-02-19): extension for MIP_Problem class
-
class
sage.libs.ppl.
C_Polyhedron
¶ Bases:
sage.libs.ppl.Polyhedron
Wrapper for PPL’s
C_Polyhedron
class.An object of the class
C_Polyhedron
represents a topologically closed convex polyhedron in the vector space. SeeNNC_Polyhedron
for more general (not necessarily closed) polyhedra.When building a closed polyhedron starting from a system of constraints, an exception is thrown if the system contains a strict inequality constraint. Similarly, an exception is thrown when building a closed polyhedron starting from a system of generators containing a closure point.
INPUT:
arg
– the defining data of the polyhedron. Any one of the following is accepted:- A non-negative integer. Depending on
degenerate_element
, either the space-filling or the empty polytope in the given dimensionarg
is constructed. - A
Constraint_System
. - A
Generator_System
. - A single
Constraint
. - A single
Generator
. - A
C_Polyhedron
.
- A non-negative integer. Depending on
degenerate_element
– string, either'universe'
or'empty'
. Only used ifarg
is an integer.
OUTPUT:
A
C_Polyhedron
.EXAMPLES:
sage: from sage.libs.ppl import Constraint, Constraint_System, Generator, Generator_System, Variable, C_Polyhedron, point, ray sage: x = Variable(0) sage: y = Variable(1) sage: C_Polyhedron( 5*x-2*y >= x+y-1 ) A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point, 1 ray, 1 line sage: cs = Constraint_System() sage: cs.insert( x >= 0 ) sage: cs.insert( y >= 0 ) sage: C_Polyhedron(cs) A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point, 2 rays sage: C_Polyhedron( point(x+y) ) A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point sage: gs = Generator_System() sage: gs.insert( point(-x-y) ) sage: gs.insert( ray(x) ) sage: C_Polyhedron(gs) A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point, 1 ray
The empty and universe polyhedra are constructed like this:
sage: C_Polyhedron(3, 'empty') The empty polyhedron in QQ^3 sage: C_Polyhedron(3, 'empty').constraints() Constraint_System {-1==0} sage: C_Polyhedron(3, 'universe') The space-filling polyhedron in QQ^3 sage: C_Polyhedron(3, 'universe').constraints() Constraint_System {}
Note that, by convention, the generator system of a polyhedron is either empty or contains at least one point. In particular, if you define a polyhedron via a non-empty
Generator_System
it must contain a point (at any position). If you start with a single generator, this generator must be a point:sage: C_Polyhedron( ray(x) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::C_Polyhedron(gs): *this is an empty polyhedron and the non-empty generator system gs contains no points.
-
class
sage.libs.ppl.
Constraint
¶ Bases:
object
Wrapper for PPL’s
Constraint
class.An object of the class
Constraint
is either:- an equality \(\sum_{i=0}^{n-1} a_i x_i + b = 0\)
- a non-strict inequality \(\sum_{i=0}^{n-1} a_i x_i + b \geq 0\)
- a strict inequality \(\sum_{i=0}^{n-1} a_i x_i + b > 0\)
where \(n\) is the dimension of the space, \(a_i\) is the integer coefficient of variable \(x_i\), and \(b_i\) is the integer inhomogeneous term.
INPUT/OUTPUT:
You construct constraints by writing inequalities in
Linear_Expression
. Do not attempt to manually construct constraints.EXAMPLES:
sage: from sage.libs.ppl import Constraint, Variable, Linear_Expression sage: x = Variable(0) sage: y = Variable(1) sage: 5*x-2*y > x+y-1 4*x0-3*x1+1>0 sage: 5*x-2*y >= x+y-1 4*x0-3*x1+1>=0 sage: 5*x-2*y == x+y-1 4*x0-3*x1+1==0 sage: 5*x-2*y <= x+y-1 -4*x0+3*x1-1>=0 sage: 5*x-2*y < x+y-1 -4*x0+3*x1-1>0 sage: x > 0 x0>0
Special care is needed if the left hand side is a constant:
sage: 0 == 1 # watch out! False sage: Linear_Expression(0) == 1 -1==0
-
OK
()¶ Check if all the invariants are satisfied.
EXAMPLES:
sage: from sage.libs.ppl import Linear_Expression, Variable sage: x = Variable(0) sage: y = Variable(1) sage: ineq = (3*x+2*y+1>=0) sage: ineq.OK() True
-
ascii_dump
()¶ Write an ASCII dump to stderr.
EXAMPLES:
sage: sage_cmd = 'from sage.libs.ppl import Linear_Expression, Variable\n' sage: sage_cmd += 'x = Variable(0)\n' sage: sage_cmd += 'y = Variable(1)\n' sage: sage_cmd += 'e = (3*x+2*y+1 > 0)\n' sage: sage_cmd += 'e.ascii_dump()\n' sage: from sage.tests.cmdline import test_executable sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd], timeout=100) # long time, indirect doctest sage: print(err) # long time size 4 1 3 2 -1 > (NNC)
-
coefficient
(v)¶ Return the coefficient of the variable
v
.INPUT:
v
– aVariable
.
OUTPUT:
An integer.
EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(0) sage: ineq = (3*x+1 > 0) sage: ineq.coefficient(x) 3
-
coefficients
()¶ Return the coefficients of the constraint.
See also
coefficient()
.OUTPUT:
A tuple of integers of length
space_dimension()
.EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(0); y = Variable(1) sage: ineq = ( 3*x+5*y+1 == 2); ineq 3*x0+5*x1-1==0 sage: ineq.coefficients() (3, 5)
-
inhomogeneous_term
()¶ Return the inhomogeneous term of the constraint.
OUTPUT:
Integer.
EXAMPLES:
sage: from sage.libs.ppl import Variable sage: y = Variable(1) sage: ineq = ( 10+y > 9 ) sage: ineq x1+1>0 sage: ineq.inhomogeneous_term() 1
-
is_equality
()¶ Test whether
self
is an equality.OUTPUT:
Boolean. Returns
True
if and only ifself
is an equality constraint.EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(0) sage: (x==0).is_equality() True sage: (x>=0).is_equality() False sage: (x>0).is_equality() False
-
is_equivalent_to
(c)¶ Test whether
self
andc
are equivalent.INPUT:
c
– aConstraint
.
OUTPUT:
Boolean. Returns
True
if and only ifself
andc
are equivalent constraints.Note that constraints having different space dimensions are not equivalent. However, constraints having different types may nonetheless be equivalent, if they both are tautologies or inconsistent.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Linear_Expression sage: x = Variable(0) sage: y = Variable(1) sage: ( x>0 ).is_equivalent_to( Linear_Expression(0)<x ) True sage: ( x>0 ).is_equivalent_to( 0*y<x ) False sage: ( 0*x>1 ).is_equivalent_to( 0*x==-2 ) True
-
is_inconsistent
()¶ Test whether
self
is an inconsistent constraint, that is, always false.An inconsistent constraint can have either one of the following forms:
- an equality: \(\sum 0 x_i + b = 0\) with \(b\not=0\),
- a non-strict inequality: \(\sum 0 x_i + b \geq 0\) with \(b< 0\), or
- a strict inequality: \(\sum 0 x_i + b > 0\) with \(b\leq 0\).
OUTPUT:
Boolean. Returns
True
if and only ifself
is an inconsistent constraint.EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(0) sage: (x==1).is_inconsistent() False sage: (0*x>=1).is_inconsistent() True
-
is_inequality
()¶ Test whether
self
is an inequality.OUTPUT:
Boolean. Returns
True
if and only ifself
is an inequality constraint, either strict or non-strict.EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(0) sage: (x==0).is_inequality() False sage: (x>=0).is_inequality() True sage: (x>0).is_inequality() True
-
is_nonstrict_inequality
()¶ Test whether
self
is a non-strict inequality.OUTPUT:
Boolean. Returns
True
if and only ifself
is an non-strict inequality constraint.EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(0) sage: (x==0).is_nonstrict_inequality() False sage: (x>=0).is_nonstrict_inequality() True sage: (x>0).is_nonstrict_inequality() False
-
is_strict_inequality
()¶ Test whether
self
is a strict inequality.OUTPUT:
Boolean. Returns
True
if and only ifself
is an strict inequality constraint.EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(0) sage: (x==0).is_strict_inequality() False sage: (x>=0).is_strict_inequality() False sage: (x>0).is_strict_inequality() True
-
is_tautological
()¶ Test whether
self
is a tautological constraint.A tautology can have either one of the following forms:
- an equality: \(\sum 0 x_i + 0 = 0\),
- a non-strict inequality: \(\sum 0 x_i + b \geq 0\) with \(b\geq 0\), or
- a strict inequality: \(\sum 0 x_i + b > 0\) with \(b> 0\).
OUTPUT:
Boolean. Returns
True
if and only ifself
is a tautological constraint.EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(0) sage: (x==0).is_tautological() False sage: (0*x>=0).is_tautological() True
-
space_dimension
()¶ Return the dimension of the vector space enclosing
self
.OUTPUT:
Integer.
EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(0) sage: y = Variable(1) sage: (x>=0).space_dimension() 1 sage: (y==1).space_dimension() 2
-
type
()¶ Return the constraint type of
self
.OUTPUT:
String. One of
'equality'
,'nonstrict_inequality'
, or'strict_inequality'
.EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(0) sage: (x==0).type() 'equality' sage: (x>=0).type() 'nonstrict_inequality' sage: (x>0).type() 'strict_inequality'
-
class
sage.libs.ppl.
Constraint_System
¶ Bases:
sage.libs.ppl._mutable_or_immutable
Wrapper for PPL’s
Constraint_System
class.An object of the class Constraint_System is a system of constraints, i.e., a multiset of objects of the class Constraint. When inserting constraints in a system, space dimensions are automatically adjusted so that all the constraints in the system are defined on the same vector space.
EXAMPLES:
sage: from sage.libs.ppl import Constraint_System, Variable sage: x = Variable(0) sage: y = Variable(1) sage: cs = Constraint_System( 5*x-2*y > 0 ) sage: cs.insert( 6*x<3*y ) sage: cs.insert( x >= 2*x-7*y ) sage: cs Constraint_System {5*x0-2*x1>0, -2*x0+x1>0, -x0+7*x1>=0}
-
OK
()¶ Check if all the invariants are satisfied.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System sage: x = Variable(0) sage: y = Variable(1) sage: cs = Constraint_System( 3*x+2*y+1 <= 10 ) sage: cs.OK() True
-
ascii_dump
()¶ Write an ASCII dump to stderr.
EXAMPLES:
sage: sage_cmd = 'from sage.libs.ppl import Constraint_System, Variable\n' sage: sage_cmd += 'x = Variable(0)\n' sage: sage_cmd += 'y = Variable(1)\n' sage: sage_cmd += 'cs = Constraint_System( 3*x > 2*y+1 )\n' sage: sage_cmd += 'cs.ascii_dump()\n' sage: from sage.tests.cmdline import test_executable sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd], timeout=100) # long time, indirect doctest sage: print(err) # long time topology NOT_NECESSARILY_CLOSED 1 x 2 SPARSE (sorted) index_first_pending 1 size 4 -1 3 -2 -1 > (NNC)
-
clear
()¶ Removes all constraints from the constraint system and sets its space dimension to 0.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System sage: x = Variable(0) sage: cs = Constraint_System(x>0) sage: cs Constraint_System {x0>0} sage: cs.clear() sage: cs Constraint_System {}
-
empty
()¶ Return
True
if and only ifself
has no constraints.OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System, point sage: x = Variable(0) sage: cs = Constraint_System() sage: cs.empty() True sage: cs.insert( x>0 ) sage: cs.empty() False
-
has_equalities
()¶ Tests whether
self
contains one or more equality constraints.OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System sage: x = Variable(0) sage: cs = Constraint_System() sage: cs.insert( x>0 ) sage: cs.insert( x<0 ) sage: cs.has_equalities() False sage: cs.insert( x==0 ) sage: cs.has_equalities() True
-
has_strict_inequalities
()¶ Tests whether
self
contains one or more strict inequality constraints.OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System sage: x = Variable(0) sage: cs = Constraint_System() sage: cs.insert( x>=0 ) sage: cs.insert( x==-1 ) sage: cs.has_strict_inequalities() False sage: cs.insert( x>0 ) sage: cs.has_strict_inequalities() True
-
insert
(c)¶ Insert
c
into the constraint system.INPUT:
c
– aConstraint
.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System sage: x = Variable(0) sage: cs = Constraint_System() sage: cs.insert( x>0 ) sage: cs Constraint_System {x0>0}
-
space_dimension
()¶ Return the dimension of the vector space enclosing
self
.OUTPUT:
Integer.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System sage: x = Variable(0) sage: cs = Constraint_System( x>0 ) sage: cs.space_dimension() 1
-
-
class
sage.libs.ppl.
Constraint_System_iterator
¶ Bases:
object
Wrapper for PPL’s
Constraint_System::const_iterator
class.EXAMPLES:
sage: from sage.libs.ppl import Constraint_System, Variable, Constraint_System_iterator sage: x = Variable(0) sage: y = Variable(1) sage: cs = Constraint_System( 5*x < 2*y ) sage: cs.insert( 6*x-3*y==0 ) sage: cs.insert( x >= 2*x-7*y ) sage: next(Constraint_System_iterator(cs)) -5*x0+2*x1>0 sage: list(cs) [-5*x0+2*x1>0, 2*x0-x1==0, -x0+7*x1>=0]
-
next
()¶ x.next() -> the next value, or raise StopIteration
-
-
class
sage.libs.ppl.
Generator
¶ Bases:
object
Wrapper for PPL’s
Generator
class.An object of the class Generator is one of the following:
- a line \(\ell = (a_0, \dots, a_{n-1})^T\)
- a ray \(r = (a_0, \dots, a_{n-1})^T\)
- a point \(p = (\tfrac{a_0}{d}, \dots, \tfrac{a_{n-1}}{d})^T\)
- a closure point \(c = (\tfrac{a_0}{d}, \dots, \tfrac{a_{n-1}}{d})^T\)
where \(n\) is the dimension of the space and, for points and closure points, \(d\) is the divisor.
INPUT/OUTPUT:
Use the helper functions
line()
,ray()
,point()
, andclosure_point()
to construct generators. Analogous class methods are also available, seeGenerator.line()
,Generator.ray()
,Generator.point()
,Generator.closure_point()
. Do not attempt to construct generators manually.Note
The generators are constructed from linear expressions. The inhomogeneous term is always silently discarded.
EXAMPLES:
sage: from sage.libs.ppl import Generator, Variable sage: x = Variable(0) sage: y = Variable(1) sage: Generator.line(5*x-2*y) line(5, -2) sage: Generator.ray(5*x-2*y) ray(5, -2) sage: Generator.point(5*x-2*y, 7) point(5/7, -2/7) sage: Generator.closure_point(5*x-2*y, 7) closure_point(5/7, -2/7)
-
OK
()¶ Check if all the invariants are satisfied.
EXAMPLES:
sage: from sage.libs.ppl import Linear_Expression, Variable sage: x = Variable(0) sage: y = Variable(1) sage: e = 3*x+2*y+1 sage: e.OK() True
-
ascii_dump
()¶ Write an ASCII dump to stderr.
EXAMPLES:
sage: sage_cmd = 'from sage.libs.ppl import Linear_Expression, Variable, point\n' sage: sage_cmd += 'x = Variable(0)\n' sage: sage_cmd += 'y = Variable(1)\n' sage: sage_cmd += 'p = point(3*x+2*y)\n' sage: sage_cmd += 'p.ascii_dump()\n' sage: from sage.tests.cmdline import test_executable sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd], timeout=100) # long time, indirect doctest sage: print(err) # long time size 3 1 3 2 P (C)
-
static
closure_point
(expression=0, divisor=1)¶ Construct a closure point.
A closure point is a point of the topological closure of a polyhedron that is not a point of the polyhedron itself.
INPUT:
expression
– aLinear_Expression
or something convertible to it (Variable
or integer).divisor
– an integer.
OUTPUT:
A new
Generator
representing the point.Raises a
ValueError` if ``divisor==0
.EXAMPLES:
sage: from sage.libs.ppl import Generator, Variable sage: y = Variable(1) sage: Generator.closure_point(2*y+7, 3) closure_point(0/3, 2/3) sage: Generator.closure_point(y+7, 3) closure_point(0/3, 1/3) sage: Generator.closure_point(7, 3) closure_point() sage: Generator.closure_point(0, 0) Traceback (most recent call last): ... ValueError: PPL::closure_point(e, d): d == 0.
-
coefficient
(v)¶ Return the coefficient of the variable
v
.INPUT:
v
– aVariable
.
OUTPUT:
An integer.
EXAMPLES:
sage: from sage.libs.ppl import Variable, line sage: x = Variable(0) sage: line = line(3*x+1) sage: line line(1) sage: line.coefficient(x) 1
-
coefficients
()¶ Return the coefficients of the generator.
See also
coefficient()
.OUTPUT:
A tuple of integers of length
space_dimension()
.EXAMPLES:
sage: from sage.libs.ppl import Variable, point sage: x = Variable(0); y = Variable(1) sage: p = point(3*x+5*y+1, 2); p point(3/2, 5/2) sage: p.coefficients() (3, 5)
-
divisor
()¶ If
self
is either a point or a closure point, return its divisor.OUTPUT:
An integer. If
self
is a ray or a line, raisesValueError
.EXAMPLES:
sage: from sage.libs.ppl import Generator, Variable sage: x = Variable(0) sage: y = Variable(1) sage: point = Generator.point(2*x-y+5) sage: point.divisor() 1 sage: line = Generator.line(2*x-y+5) sage: line.divisor() Traceback (most recent call last): ... ValueError: PPL::Generator::divisor(): *this is neither a point nor a closure point.
-
is_closure_point
()¶ Test whether
self
is a closure point.OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.libs.ppl import Variable, point, closure_point, ray, line sage: x = Variable(0) sage: line(x).is_closure_point() False sage: ray(x).is_closure_point() False sage: point(x,2).is_closure_point() False sage: closure_point(x,2).is_closure_point() True
-
is_equivalent_to
(g)¶ Test whether
self
andg
are equivalent.INPUT:
g
– aGenerator
.
OUTPUT:
Boolean. Returns
True
if and only ifself
andg
are equivalent generators.Note that generators having different space dimensions are not equivalent.
EXAMPLES:
sage: from sage.libs.ppl import Generator, Variable, point, line sage: x = Variable(0) sage: y = Variable(1) sage: point(2*x , 2).is_equivalent_to( point(x) ) True sage: point(2*x+0*y, 2).is_equivalent_to( point(x) ) False sage: line(4*x).is_equivalent_to(line(x)) True
-
is_line
()¶ Test whether
self
is a line.OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.libs.ppl import Variable, point, closure_point, ray, line sage: x = Variable(0) sage: line(x).is_line() True sage: ray(x).is_line() False sage: point(x,2).is_line() False sage: closure_point(x,2).is_line() False
-
is_line_or_ray
()¶ Test whether
self
is a line or a ray.OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.libs.ppl import Variable, point, closure_point, ray, line sage: x = Variable(0) sage: line(x).is_line_or_ray() True sage: ray(x).is_line_or_ray() True sage: point(x,2).is_line_or_ray() False sage: closure_point(x,2).is_line_or_ray() False
-
is_point
()¶ Test whether
self
is a point.OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.libs.ppl import Variable, point, closure_point, ray, line sage: x = Variable(0) sage: line(x).is_point() False sage: ray(x).is_point() False sage: point(x,2).is_point() True sage: closure_point(x,2).is_point() False
-
is_ray
()¶ Test whether
self
is a ray.OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.libs.ppl import Variable, point, closure_point, ray, line sage: x = Variable(0) sage: line(x).is_ray() False sage: ray(x).is_ray() True sage: point(x,2).is_ray() False sage: closure_point(x,2).is_ray() False
-
static
line
(expression)¶ Construct a line.
INPUT:
expression
– aLinear_Expression
or something convertible to it (Variable
or integer).
OUTPUT:
A new
Generator
representing the line.Raises a
ValueError` if the homogeneous part of ``expression
represents the origin of the vector space.EXAMPLES:
sage: from sage.libs.ppl import Generator, Variable sage: y = Variable(1) sage: Generator.line(2*y) line(0, 1) sage: Generator.line(y) line(0, 1) sage: Generator.line(1) Traceback (most recent call last): ... ValueError: PPL::line(e): e == 0, but the origin cannot be a line.
-
static
point
(expression=0, divisor=1)¶ Construct a point.
INPUT:
expression
– aLinear_Expression
or something convertible to it (Variable
or integer).divisor
– an integer.
OUTPUT:
A new
Generator
representing the point.Raises a
ValueError` if ``divisor==0
.EXAMPLES:
sage: from sage.libs.ppl import Generator, Variable sage: y = Variable(1) sage: Generator.point(2*y+7, 3) point(0/3, 2/3) sage: Generator.point(y+7, 3) point(0/3, 1/3) sage: Generator.point(7, 3) point() sage: Generator.point(0, 0) Traceback (most recent call last): ... ValueError: PPL::point(e, d): d == 0.
-
static
ray
(expression)¶ Construct a ray.
INPUT:
expression
– aLinear_Expression
or something convertible to it (Variable
or integer).
OUTPUT:
A new
Generator
representing the ray.Raises a
ValueError` if the homogeneous part of ``expression
represents the origin of the vector space.EXAMPLES:
sage: from sage.libs.ppl import Generator, Variable sage: y = Variable(1) sage: Generator.ray(2*y) ray(0, 1) sage: Generator.ray(y) ray(0, 1) sage: Generator.ray(1) Traceback (most recent call last): ... ValueError: PPL::ray(e): e == 0, but the origin cannot be a ray.
-
space_dimension
()¶ Return the dimension of the vector space enclosing
self
.OUTPUT:
Integer.
EXAMPLES:
sage: from sage.libs.ppl import Variable, point sage: x = Variable(0) sage: y = Variable(1) sage: point(x).space_dimension() 1 sage: point(y).space_dimension() 2
-
type
()¶ Return the generator type of
self
.OUTPUT:
String. One of
'line'
,'ray'
,'point'
, or'closure_point'
.EXAMPLES:
sage: from sage.libs.ppl import Variable, point, closure_point, ray, line sage: x = Variable(0) sage: line(x).type() 'line' sage: ray(x).type() 'ray' sage: point(x,2).type() 'point' sage: closure_point(x,2).type() 'closure_point'
-
class
sage.libs.ppl.
Generator_System
¶ Bases:
sage.libs.ppl._mutable_or_immutable
Wrapper for PPL’s
Generator_System
class.An object of the class Generator_System is a system of generators, i.e., a multiset of objects of the class Generator (lines, rays, points and closure points). When inserting generators in a system, space dimensions are automatically adjusted so that all the generators in the system are defined on the same vector space. A system of generators which is meant to define a non-empty polyhedron must include at least one point: the reason is that lines, rays and closure points need a supporting point (lines and rays only specify directions while closure points only specify points in the topological closure of the NNC polyhedron).
EXAMPLES:
sage: from sage.libs.ppl import Generator_System, Variable, line, ray, point, closure_point sage: x = Variable(0) sage: y = Variable(1) sage: gs = Generator_System( line(5*x-2*y) ) sage: gs.insert( ray(6*x-3*y) ) sage: gs.insert( point(2*x-7*y, 5) ) sage: gs.insert( closure_point(9*x-1*y, 2) ) sage: gs Generator_System {line(5, -2), ray(2, -1), point(2/5, -7/5), closure_point(9/2, -1/2)}
-
OK
()¶ Check if all the invariants are satisfied.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Generator_System, point sage: x = Variable(0) sage: y = Variable(1) sage: gs = Generator_System( point(3*x+2*y+1) ) sage: gs.OK() True
-
ascii_dump
()¶ Write an ASCII dump to stderr.
EXAMPLES:
sage: sage_cmd = 'from sage.libs.ppl import Generator_System, point, Variable\n' sage: sage_cmd += 'x = Variable(0)\n' sage: sage_cmd += 'y = Variable(1)\n' sage: sage_cmd += 'gs = Generator_System( point(3*x+2*y+1) )\n' sage: sage_cmd += 'gs.ascii_dump()\n' sage: from sage.tests.cmdline import test_executable sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd], timeout=100) # long time, indirect doctest sage: print(err) # long time topology NECESSARILY_CLOSED 1 x 2 SPARSE (sorted) index_first_pending 1 size 3 1 3 2 P (C)
-
clear
()¶ Removes all generators from the generator system and sets its space dimension to 0.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Generator_System, point sage: x = Variable(0) sage: gs = Generator_System( point(3*x) ); gs Generator_System {point(3/1)} sage: gs.clear() sage: gs Generator_System {}
-
empty
()¶ Return
True
if and only ifself
has no generators.OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Generator_System, point sage: x = Variable(0) sage: gs = Generator_System() sage: gs.empty() True sage: gs.insert( point(-3*x) ) sage: gs.empty() False
-
insert
(g)¶ Insert
g
into the generator system.The number of space dimensions of
self
is increased, if needed.INPUT:
g
– aGenerator
.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Generator_System, point sage: x = Variable(0) sage: gs = Generator_System( point(3*x) ) sage: gs.insert( point(-3*x) ) sage: gs Generator_System {point(3/1), point(-3/1)}
-
space_dimension
()¶ Return the dimension of the vector space enclosing
self
.OUTPUT:
Integer.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Generator_System, point sage: x = Variable(0) sage: gs = Generator_System( point(3*x) ) sage: gs.space_dimension() 1
-
-
class
sage.libs.ppl.
Generator_System_iterator
¶ Bases:
object
Wrapper for PPL’s
Generator_System::const_iterator
class.EXAMPLES:
sage: from sage.libs.ppl import Generator_System, Variable, line, ray, point, closure_point, Generator_System_iterator sage: x = Variable(0) sage: y = Variable(1) sage: gs = Generator_System( line(5*x-2*y) ) sage: gs.insert( ray(6*x-3*y) ) sage: gs.insert( point(2*x-7*y, 5) ) sage: gs.insert( closure_point(9*x-1*y, 2) ) sage: next(Generator_System_iterator(gs)) line(5, -2) sage: list(gs) [line(5, -2), ray(2, -1), point(2/5, -7/5), closure_point(9/2, -1/2)]
-
next
()¶ x.next() -> the next value, or raise StopIteration
-
-
class
sage.libs.ppl.
Linear_Expression
¶ Bases:
object
Wrapper for PPL’s
PPL_Linear_Expression
class.INPUT:
The constructor accepts zero, one, or two arguments.
If there are two arguments
Linear_Expression(a,b)
, they are interpreted asa
– an iterable of integer coefficients, for example a list.b
– an integer. The inhomogeneous term.
A single argument
Linear_Expression(arg)
is interpreted asarg
– something that determines a linear expression. Possibilities are:- a
Variable
: The linear expression given by that variable. - a
Linear_Expression
: The copy constructor. - an integer: Constructs the constant linear expression.
- a
No argument is the default constructor and returns the zero linear expression.
OUTPUT:
EXAMPLES:
sage: from sage.libs.ppl import Variable, Linear_Expression sage: Linear_Expression([1,2,3,4],5) x0+2*x1+3*x2+4*x3+5 sage: Linear_Expression(10) 10 sage: Linear_Expression() 0 sage: Linear_Expression(10).inhomogeneous_term() 10 sage: x = Variable(123) sage: expr = x+1; expr x123+1 sage: expr.OK() True sage: expr.coefficient(x) 1 sage: expr.coefficient( Variable(124) ) 0
-
OK
()¶ Check if all the invariants are satisfied.
EXAMPLES:
sage: from sage.libs.ppl import Linear_Expression, Variable sage: x = Variable(0) sage: y = Variable(1) sage: e = 3*x+2*y+1 sage: e.OK() True
-
all_homogeneous_terms_are_zero
()¶ Test if
self
is a constant linear expression.OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Linear_Expression sage: Linear_Expression(10).all_homogeneous_terms_are_zero() True
-
ascii_dump
()¶ Write an ASCII dump to stderr.
EXAMPLES:
sage: sage_cmd = 'from sage.libs.ppl import Linear_Expression, Variable\n' sage: sage_cmd += 'x = Variable(0)\n' sage: sage_cmd += 'y = Variable(1)\n' sage: sage_cmd += 'e = 3*x+2*y+1\n' sage: sage_cmd += 'e.ascii_dump()\n' sage: from sage.tests.cmdline import test_executable sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd], timeout=100) # long time, indirect doctest sage: print(err) # long time size 3 1 3 2
-
coefficient
(v)¶ Return the coefficient of the variable
v
.INPUT:
v
– aVariable
.
OUTPUT:
An integer.
EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(0) sage: e = 3*x+1 sage: e.coefficient(x) 3
-
coefficients
()¶ Return the coefficients of the linear expression.
OUTPUT:
A tuple of integers of length
space_dimension()
.EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(0); y = Variable(1) sage: e = 3*x+5*y+1 sage: e.coefficients() (3, 5)
-
inhomogeneous_term
()¶ Return the inhomogeneous term of the linear expression.
OUTPUT:
Integer.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Linear_Expression sage: Linear_Expression(10).inhomogeneous_term() 10
-
is_zero
()¶ Test if
self
is the zero linear expression.OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Linear_Expression sage: Linear_Expression(0).is_zero() True sage: Linear_Expression(10).is_zero() False
-
space_dimension
()¶ Return the dimension of the vector space necessary for the linear expression.
OUTPUT:
Integer.
EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(0) sage: y = Variable(1) sage: ( x+y+1 ).space_dimension() 2 sage: ( x+y ).space_dimension() 2 sage: ( y+1 ).space_dimension() 2 sage: ( x +1 ).space_dimension() 1 sage: ( y+1-y ).space_dimension() 2
-
class
sage.libs.ppl.
MIP_Problem
¶ Bases:
sage.libs.ppl._mutable_or_immutable
wrapper for PPL’s MIP_Problem class
An object of the class MIP_Problem represents a Mixed Integer (Linear) Program problem.
INPUT:
dim
– integerargs
– an array of the defining data of the MIP_Problem. For each element, any one of the following is accepted:
OUTPUT:
A
MIP_Problem
.EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem sage: x = Variable(0) sage: y = Variable(1) sage: cs = Constraint_System() sage: cs.insert( x >= 0) sage: cs.insert( y >= 0 ) sage: cs.insert( 3 * x + 5 * y <= 10 ) sage: m = MIP_Problem(2, cs, x + y) sage: m.optimal_value() 10/3 sage: m.optimizing_point() point(10/3, 0/3)
-
OK
()¶ Check if all the invariants are satisfied.
OUTPUT:
True
if and only ifself
satisfies all the invariants.EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem sage: x = Variable(0) sage: y = Variable(1) sage: m = MIP_Problem() sage: m.add_space_dimensions_and_embed(2) sage: m.add_constraint(x >= 0) sage: m.OK() True
-
add_constraint
(c)¶ Adds a copy of constraint c to the MIP problem.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem sage: x = Variable(0) sage: y = Variable(1) sage: m = MIP_Problem() sage: m.add_space_dimensions_and_embed(2) sage: m.add_constraint(x >= 0) sage: m.add_constraint(y >= 0) sage: m.add_constraint(3 * x + 5 * y <= 10) sage: m.set_objective_function(x + y) sage: m.optimal_value() 10/3
TESTS:
sage: z = Variable(2) sage: m.add_constraint(z >= -3) Traceback (most recent call last): ... ValueError: PPL::MIP_Problem::add_constraint(c): c.space_dimension() == 3 exceeds this->space_dimension == 2.
-
add_constraints
(cs)¶ Adds a copy of the constraints in cs to the MIP problem.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem sage: x = Variable(0) sage: y = Variable(1) sage: cs = Constraint_System() sage: cs.insert( x >= 0) sage: cs.insert( y >= 0 ) sage: cs.insert( 3 * x + 5 * y <= 10 ) sage: m = MIP_Problem(2) sage: m.set_objective_function(x + y) sage: m.add_constraints(cs) sage: m.optimal_value() 10/3
TESTS:
sage: p = Variable(9) sage: cs.insert(p >= -3) sage: m.add_constraints(cs) Traceback (most recent call last): ... ValueError: PPL::MIP_Problem::add_constraints(cs): cs.space_dimension() == 10 exceeds this->space_dimension() == 2.
-
add_space_dimensions_and_embed
(m)¶ Adds m new space dimensions and embeds the old MIP problem in the new vector space.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem sage: x = Variable(0) sage: y = Variable(1) sage: cs = Constraint_System() sage: cs.insert( x >= 0) sage: cs.insert( y >= 0 ) sage: cs.insert( 3 * x + 5 * y <= 10 ) sage: m = MIP_Problem(2, cs, x + y) sage: m.add_space_dimensions_and_embed(5) sage: m.space_dimension() 7
-
add_to_integer_space_dimensions
(i_vars)¶ Sets the variables whose indexes are in set \(i_vars\) to be integer space dimensions.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Variables_Set, Constraint_System, MIP_Problem sage: x = Variable(0) sage: y = Variable(1) sage: cs = Constraint_System() sage: cs.insert( x >= 0) sage: cs.insert( y >= 0 ) sage: cs.insert( 3 * x + 5 * y <= 10 ) sage: m = MIP_Problem(2) sage: m.set_objective_function(x + y) sage: m.add_constraints(cs) sage: i_vars = Variables_Set(x, y) sage: m.add_to_integer_space_dimensions(i_vars) sage: m.optimal_value() 3
-
clear
()¶ Reset the MIP_Problem to be equal to the trivial MIP_Problem.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem sage: x = Variable(0) sage: y = Variable(1) sage: cs = Constraint_System() sage: cs.insert( x >= 0) sage: cs.insert( y >= 0 ) sage: cs.insert( 3 * x + 5 * y <= 10 ) sage: m = MIP_Problem(2, cs, x + y) sage: m.objective_function() x0+x1 sage: m.clear() sage: m.objective_function() 0
-
evaluate_objective_function
(evaluating_point)¶ Return the result of evaluating the objective function on evaluating_point. ValueError thrown if self and evaluating_point are dimension-incompatible or if the generator evaluating_point is not a point.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem, Generator sage: x = Variable(0) sage: y = Variable(1) sage: m = MIP_Problem() sage: m.add_space_dimensions_and_embed(2) sage: m.add_constraint(x >= 0) sage: m.add_constraint(y >= 0) sage: m.add_constraint(3 * x + 5 * y <= 10) sage: m.set_objective_function(x + y) sage: g = Generator.point(5 * x - 2 * y, 7) sage: m.evaluate_objective_function(g) 3/7 sage: z = Variable(2) sage: g = Generator.point(5 * x - 2 * z, 7) sage: m.evaluate_objective_function(g) Traceback (most recent call last): ... ValueError: PPL::MIP_Problem::evaluate_objective_function(p, n, d): *this and p are dimension incompatible.
-
is_satisfiable
()¶ Check if the MIP_Problem is satisfiable
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem sage: x = Variable(0) sage: y = Variable(1) sage: m = MIP_Problem() sage: m.add_space_dimensions_and_embed(2) sage: m.add_constraint(x >= 0) sage: m.add_constraint(y >= 0) sage: m.add_constraint(3 * x + 5 * y <= 10) sage: m.is_satisfiable() True
-
objective_function
()¶ Return the optimal value of the MIP_Problem.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem sage: x = Variable(0) sage: y = Variable(1) sage: cs = Constraint_System() sage: cs.insert( x >= 0) sage: cs.insert( y >= 0 ) sage: cs.insert( 3 * x + 5 * y <= 10 ) sage: m = MIP_Problem(2, cs, x + y) sage: m.objective_function() x0+x1
-
optimal_value
()¶ Return the optimal value of the MIP_Problem. ValueError thrown if self does not have an optimizing point, i.e., if the MIP problem is unbounded or not satisfiable.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem sage: x = Variable(0) sage: y = Variable(1) sage: cs = Constraint_System() sage: cs.insert( x >= 0 ) sage: cs.insert( y >= 0 ) sage: cs.insert( 3 * x + 5 * y <= 10 ) sage: m = MIP_Problem(2, cs, x + y) sage: m.optimal_value() 10/3 sage: cs = Constraint_System() sage: cs.insert( x >= 0 ) sage: m = MIP_Problem(1, cs, x + x ) sage: m.optimal_value() Traceback (most recent call last): ... ValueError: PPL::MIP_Problem::optimizing_point(): *this does not have an optimizing point.
-
optimization_mode
()¶ Return the optimization mode used in the MIP_Problem.
It will return “maximization” if the MIP_Problem was set to MAXIMIZATION mode, and “minimization” otherwise.
EXAMPLES:
sage: from sage.libs.ppl import MIP_Problem sage: m = MIP_Problem() sage: m.optimization_mode() 'maximization'
-
optimizing_point
()¶ Returns an optimal point for the MIP_Problem, if it exists.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem sage: x = Variable(0) sage: y = Variable(1) sage: m = MIP_Problem() sage: m.add_space_dimensions_and_embed(2) sage: m.add_constraint(x >= 0) sage: m.add_constraint(y >= 0) sage: m.add_constraint(3 * x + 5 * y <= 10) sage: m.set_objective_function(x + y) sage: m.optimizing_point() point(10/3, 0/3)
-
set_objective_function
(obj)¶ Sets the objective function to obj.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem sage: x = Variable(0) sage: y = Variable(1) sage: m = MIP_Problem() sage: m.add_space_dimensions_and_embed(2) sage: m.add_constraint(x >= 0) sage: m.add_constraint(y >= 0) sage: m.add_constraint(3 * x + 5 * y <= 10) sage: m.set_objective_function(x + y) sage: m.optimal_value() 10/3
TESTS:
sage: z = Variable(2) sage: m.set_objective_function(x + y + z) Traceback (most recent call last): ... ValueError: PPL::MIP_Problem::set_objective_function(obj): obj.space_dimension() == 3 exceeds this->space_dimension == 2.
-
set_optimization_mode
(mode)¶ Sets the optimization mode to mode.
EXAMPLES:
sage: from sage.libs.ppl import MIP_Problem sage: m = MIP_Problem() sage: m.optimization_mode() 'maximization' sage: m.set_optimization_mode('minimization') sage: m.optimization_mode() 'minimization'
TESTS:
sage: m.set_optimization_mode('max') Traceback (most recent call last): ... ValueError: Unknown value: mode=max.
-
solve
()¶ Optimizes the MIP_Problem
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem sage: x = Variable(0) sage: y = Variable(1) sage: m = MIP_Problem() sage: m.add_space_dimensions_and_embed(2) sage: m.add_constraint(x >= 0) sage: m.add_constraint(y >= 0) sage: m.add_constraint(3 * x + 5 * y <= 10) sage: m.set_objective_function(x + y) sage: m.solve() {'status': 'optimized'}
-
space_dimension
()¶ Return the space dimension of the MIP_Problem.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Constraint_System, MIP_Problem sage: x = Variable(0) sage: y = Variable(1) sage: cs = Constraint_System() sage: cs.insert( x >= 0) sage: cs.insert( y >= 0 ) sage: cs.insert( 3 * x + 5 * y <= 10 ) sage: m = MIP_Problem(2, cs, x + y) sage: m.space_dimension() 2
-
class
sage.libs.ppl.
NNC_Polyhedron
¶ Bases:
sage.libs.ppl.Polyhedron
Wrapper for PPL’s
NNC_Polyhedron
class.An object of the class
NNC_Polyhedron
represents a not necessarily closed (NNC) convex polyhedron in the vector space.Note: Since NNC polyhedra are a generalization of closed polyhedra, any object of the class
C_Polyhedron
can be (explicitly) converted into an object of the classNNC_Polyhedron
. The reason for defining two different classes is that objects of the classC_Polyhedron
are characterized by a more efficient implementation, requiring less time and memory resources.INPUT:
arg
– the defining data of the polyhedron. Any one of the following is accepted:- An non-negative integer. Depending on
degenerate_element
, either the space-filling or the empty polytope in the given dimensionarg
is constructed. - A
Constraint_System
. - A
Generator_System
. - A single
Constraint
. - A single
Generator
. - A
NNC_Polyhedron
. - A
C_Polyhedron
.
- An non-negative integer. Depending on
degenerate_element
– string, either'universe'
or'empty'
. Only used ifarg
is an integer.
OUTPUT:
A
C_Polyhedron
.EXAMPLES:
sage: from sage.libs.ppl import Constraint, Constraint_System, Generator, Generator_System, Variable, NNC_Polyhedron, point, ray, closure_point sage: x = Variable(0) sage: y = Variable(1) sage: NNC_Polyhedron( 5*x-2*y > x+y-1 ) A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point, 1 closure_point, 1 ray, 1 line sage: cs = Constraint_System() sage: cs.insert( x > 0 ) sage: cs.insert( y > 0 ) sage: NNC_Polyhedron(cs) A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point, 1 closure_point, 2 rays sage: NNC_Polyhedron( point(x+y) ) A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point sage: gs = Generator_System() sage: gs.insert( point(-y) ) sage: gs.insert( closure_point(-x-y) ) sage: gs.insert( ray(x) ) sage: p = NNC_Polyhedron(gs); p A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point, 1 closure_point, 1 ray sage: p.minimized_constraints() Constraint_System {x1+1==0, x0+1>0}
Note that, by convention, every polyhedron must contain a point:
sage: NNC_Polyhedron( closure_point(x+y) ) Traceback (most recent call last): ... ValueError: PPL::NNC_Polyhedron::NNC_Polyhedron(gs): *this is an empty polyhedron and the non-empty generator system gs contains no points.
-
class
sage.libs.ppl.
Poly_Con_Relation
¶ Bases:
object
Wrapper for PPL’s
Poly_Con_Relation
class.INPUT/OUTPUT:
You must not construct
Poly_Con_Relation
objects manually. You will usually get them fromrelation_with()
. You can also get pre-defined relations from the class methodsnothing()
,is_disjoint()
,strictly_intersects()
,is_included()
, andsaturates()
.EXAMPLES:
sage: from sage.libs.ppl import Poly_Con_Relation sage: saturates = Poly_Con_Relation.saturates(); saturates saturates sage: is_included = Poly_Con_Relation.is_included(); is_included is_included sage: is_included.implies(saturates) False sage: saturates.implies(is_included) False sage: rels = [] sage: rels.append( Poly_Con_Relation.nothing() ) sage: rels.append( Poly_Con_Relation.is_disjoint() ) sage: rels.append( Poly_Con_Relation.strictly_intersects() ) sage: rels.append( Poly_Con_Relation.is_included() ) sage: rels.append( Poly_Con_Relation.saturates() ) sage: rels [nothing, is_disjoint, strictly_intersects, is_included, saturates] sage: from sage.matrix.constructor import matrix sage: m = matrix(5,5) sage: for i, rel_i in enumerate(rels): ... for j, rel_j in enumerate(rels): ... m[i,j] = rel_i.implies(rel_j) sage: m [1 0 0 0 0] [1 1 0 0 0] [1 0 1 0 0] [1 0 0 1 0] [1 0 0 0 1]
-
OK
(check_non_empty=False)¶ Check if all the invariants are satisfied.
EXAMPLES:
sage: from sage.libs.ppl import Poly_Con_Relation sage: Poly_Con_Relation.nothing().OK() True
-
ascii_dump
()¶ Write an ASCII dump to stderr.
EXAMPLES:
sage: sage_cmd = 'from sage.libs.ppl import Poly_Con_Relation\n' sage: sage_cmd += 'Poly_Con_Relation.nothing().ascii_dump()\n' sage: from sage.tests.cmdline import test_executable sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd], timeout=100) # long time, indirect doctest sage: print(err) # long time NOTHING
-
implies
(y)¶ Test whether
self
impliesy
.INPUT:
y
– aPoly_Con_Relation
.
OUTPUT:
Boolean.
True
if and only ifself
impliesy
.EXAMPLES:
sage: from sage.libs.ppl import Poly_Con_Relation sage: nothing = Poly_Con_Relation.nothing() sage: nothing.implies( nothing ) True
-
static
is_disjoint
()¶ Return the assertion “The polyhedron and the set of points satisfying the constraint are disjoint”.
OUTPUT:
EXAMPLES:
sage: from sage.libs.ppl import Poly_Con_Relation sage: Poly_Con_Relation.is_disjoint() is_disjoint
-
static
is_included
()¶ Return the assertion “The polyhedron is included in the set of points satisfying the constraint”.
OUTPUT:
EXAMPLES:
sage: from sage.libs.ppl import Poly_Con_Relation sage: Poly_Con_Relation.is_included() is_included
-
static
nothing
()¶ Return the assertion that says nothing.
OUTPUT:
EXAMPLES:
sage: from sage.libs.ppl import Poly_Con_Relation sage: Poly_Con_Relation.nothing() nothing
-
static
saturates
()¶ Return the assertion “”.
OUTPUT:
EXAMPLES:
sage: from sage.libs.ppl import Poly_Con_Relation sage: Poly_Con_Relation.saturates() saturates
-
static
strictly_intersects
()¶ Return the assertion “The polyhedron intersects the set of points satisfying the constraint, but it is not included in it”.
OUTPUT:
EXAMPLES:
sage: from sage.libs.ppl import Poly_Con_Relation sage: Poly_Con_Relation.strictly_intersects() strictly_intersects
-
-
class
sage.libs.ppl.
Poly_Gen_Relation
¶ Bases:
object
Wrapper for PPL’s
Poly_Con_Relation
class.INPUT/OUTPUT:
You must not construct
Poly_Gen_Relation
objects manually. You will usually get them fromrelation_with()
. You can also get pre-defined relations from the class methodsnothing()
andsubsumes()
.EXAMPLES:
sage: from sage.libs.ppl import Poly_Gen_Relation sage: nothing = Poly_Gen_Relation.nothing(); nothing nothing sage: subsumes = Poly_Gen_Relation.subsumes(); subsumes subsumes sage: nothing.implies( subsumes ) False sage: subsumes.implies( nothing ) True
-
OK
(check_non_empty=False)¶ Check if all the invariants are satisfied.
EXAMPLES:
sage: from sage.libs.ppl import Poly_Gen_Relation sage: Poly_Gen_Relation.nothing().OK() True
-
ascii_dump
()¶ Write an ASCII dump to stderr.
EXAMPLES:
sage: sage_cmd = 'from sage.libs.ppl import Poly_Gen_Relation\n' sage: sage_cmd += 'Poly_Gen_Relation.nothing().ascii_dump()\n' sage: from sage.tests.cmdline import test_executable sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd], timeout=100) # long time, indirect doctest sage: print(err) # long time NOTHING
-
implies
(y)¶ Test whether
self
impliesy
.INPUT:
y
– aPoly_Gen_Relation
.
OUTPUT:
Boolean.
True
if and only ifself
impliesy
.EXAMPLES:
sage: from sage.libs.ppl import Poly_Gen_Relation sage: nothing = Poly_Gen_Relation.nothing() sage: nothing.implies( nothing ) True
-
static
nothing
()¶ Return the assertion that says nothing.
OUTPUT:
EXAMPLES:
sage: from sage.libs.ppl import Poly_Gen_Relation sage: Poly_Gen_Relation.nothing() nothing
-
static
subsumes
()¶ Return the assertion “Adding the generator would not change the polyhedron”.
OUTPUT:
EXAMPLES:
sage: from sage.libs.ppl import Poly_Gen_Relation sage: Poly_Gen_Relation.subsumes() subsumes
-
-
class
sage.libs.ppl.
Polyhedron
¶ Bases:
sage.libs.ppl._mutable_or_immutable
Wrapper for PPL’s
Polyhedron
class.An object of the class Polyhedron represents a convex polyhedron in the vector space.
A polyhedron can be specified as either a finite system of constraints or a finite system of generators (see Section Representations of Convex Polyhedra) and it is always possible to obtain either representation. That is, if we know the system of constraints, we can obtain from this the system of generators that define the same polyhedron and vice versa. These systems can contain redundant members: in this case we say that they are not in the minimal form.
INPUT/OUTPUT:
This is an abstract base for
C_Polyhedron
andNNC_Polyhedron
. You cannot instantiate this class.-
OK
(check_non_empty=False)¶ Check if all the invariants are satisfied.
The check is performed so as to intrude as little as possible. If the library has been compiled with run-time assertions enabled, error messages are written on std::cerr in case invariants are violated. This is useful for the purpose of debugging the library.
INPUT:
check_not_empty
– boolean.True
if and only if, in addition to checking the invariants,self
must be checked to be not empty.
OUTPUT:
True
if and only ifself
satisfies all the invariants and eithercheck_not_empty
isFalse
orself
is not empty.EXAMPLES:
sage: from sage.libs.ppl import Linear_Expression, Variable sage: x = Variable(0) sage: y = Variable(1) sage: e = 3*x+2*y+1 sage: e.OK() True
-
add_constraint
(c)¶ Add a constraint to the polyhedron.
Adds a copy of constraint
c
to the system of constraints ofself
, without minimizing the result.See alse
add_constraints()
.INPUT:
c
– theConstraint
that will be added to the system of constraints ofself
.
OUTPUT:
This method modifies the polyhedron
self
and does not return anything.Raises a
ValueError
ifself
and the constraintc
are topology-incompatible or dimension-incompatible.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron sage: x = Variable(0) sage: y = Variable(1) sage: p = C_Polyhedron( y>=0 ) sage: p.add_constraint( x>=0 ) We just added a 1-d constraint to a 2-d polyhedron, this is fine. The other way is not:: sage: p = C_Polyhedron( x>=0 ) sage: p.add_constraint( y>=0 ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::add_constraint(c): this->space_dimension() == 1, c.space_dimension() == 2. The constraint must also be topology-compatible, that is, :class:`C_Polyhedron` only allows non-strict inequalities:: sage: p = C_Polyhedron( x>=0 ) sage: p.add_constraint( x< 1 ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::add_constraint(c): c is a strict inequality.
-
add_constraints
(cs)¶ Add constraints to the polyhedron.
Adds a copy of constraints in
cs
to the system of constraints ofself
, without minimizing the result.See alse
add_constraint()
.INPUT:
cs
– theConstraint_System
that will be added to the system of constraints ofself
.
OUTPUT:
This method modifies the polyhedron
self
and does not return anything.Raises a
ValueError
ifself
and the constraints incs
are topology-incompatible or dimension-incompatible.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, Constraint_System sage: x = Variable(0) sage: y = Variable(1) sage: cs = Constraint_System() sage: cs.insert(x>=0) sage: cs.insert(y>=0) sage: p = C_Polyhedron( y<=1 ) sage: p.add_constraints(cs) We just added a 1-d constraint to a 2-d polyhedron, this is fine. The other way is not:: sage: p = C_Polyhedron( x<=1 ) sage: p.add_constraints(cs) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::add_recycled_constraints(cs): this->space_dimension() == 1, cs.space_dimension() == 2. The constraints must also be topology-compatible, that is, :class:`C_Polyhedron` only allows non-strict inequalities:: sage: p = C_Polyhedron( x>=0 ) sage: p.add_constraints( Constraint_System(x<0) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::add_recycled_constraints(cs): cs contains strict inequalities.
-
add_generator
(g)¶ Add a generator to the polyhedron.
Adds a copy of constraint
c
to the system of generators ofself
, without minimizing the result.INPUT:
g
– theGenerator
that will be added to the system of Generators ofself
.
OUTPUT:
This method modifies the polyhedron
self
and does not return anything.Raises a
ValueError
ifself
and the generatorg
are topology-incompatible or dimension-incompatible, or ifself
is an empty polyhedron andg
is not a point.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, point, closure_point, ray sage: x = Variable(0) sage: y = Variable(1) sage: p = C_Polyhedron(1, 'empty') sage: p.add_generator( point(0*x) ) We just added a 1-d generator to a 2-d polyhedron, this is fine. The other way is not:: sage: p = C_Polyhedron(1, 'empty') sage: p.add_generator( point(0*y) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::add_generator(g): this->space_dimension() == 1, g.space_dimension() == 2. The constraint must also be topology-compatible, that is, :class:`C_Polyhedron` does not allow :func:`closure_point` generators:: sage: p = C_Polyhedron( point(0*x+0*y) ) sage: p.add_generator( closure_point(0*x) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::add_generator(g): g is a closure point.
Finally, ever non-empty polyhedron must have at least one point generator:
sage: p = C_Polyhedron(3, 'empty') sage: p.add_generator( ray(x) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::add_generator(g): *this is an empty polyhedron and g is not a point.
-
add_generators
(gs)¶ Add generators to the polyhedron.
Adds a copy of the generators in
gs
to the system of generators ofself
, without minimizing the result.See alse
add_generator()
.INPUT:
gs
– theGenerator_System
that will be added to the system of constraints ofself
.
OUTPUT:
This method modifies the polyhedron
self
and does not return anything.Raises a
ValueError
ifself
and one of the generators ings
are topology-incompatible or dimension-incompatible, or ifself
is an empty polyhedron andgs
does not contain a point.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, Generator_System, point, ray, closure_point sage: x = Variable(0) sage: y = Variable(1) sage: gs = Generator_System() sage: gs.insert(point(0*x+0*y)) sage: gs.insert(point(1*x+1*y)) sage: p = C_Polyhedron(2, 'empty') sage: p.add_generators(gs) We just added a 1-d constraint to a 2-d polyhedron, this is fine. The other way is not:: sage: p = C_Polyhedron(1, 'empty') sage: p.add_generators(gs) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::add_recycled_generators(gs): this->space_dimension() == 1, gs.space_dimension() == 2. The constraints must also be topology-compatible, that is, :class:`C_Polyhedron` does not allow :func:`closure_point` generators:: sage: p = C_Polyhedron( point(0*x+0*y) ) sage: p.add_generators( Generator_System(closure_point(x) )) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::add_recycled_generators(gs): gs contains closure points.
-
add_space_dimensions_and_embed
(m)¶ Add
m
new space dimensions and embedself
in the new vector space.The new space dimensions will be those having the highest indexes in the new polyhedron, which is characterized by a system of constraints in which the variables running through the new dimensions are not constrained. For instance, when starting from the polyhedron \(P\) and adding a third space dimension, the result will be the polyhedron
\[\Big\{ (x,y,z)^T \in \RR^3 \Big| (x,y)^T \in P \Big\}\]INPUT:
m
– integer.
OUTPUT:
This method assigns the embedded polyhedron to
self
and does not return anything.Raises a
ValueError
if addingm
new space dimensions would cause the vector space to exceed dimensionself.max_space_dimension()
.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, point sage: x = Variable(0) sage: p = C_Polyhedron( point(3*x) ) sage: p.add_space_dimensions_and_embed(1) sage: p.minimized_generators() Generator_System {line(0, 1), point(3/1, 0/1)} sage: p.add_space_dimensions_and_embed( p.max_space_dimension() ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::add_space_dimensions_and_embed(m): adding m new space dimensions exceeds the maximum allowed space dimension.
-
add_space_dimensions_and_project
(m)¶ Add
m
new space dimensions and embedself
in the new vector space.The new space dimensions will be those having the highest indexes in the new polyhedron, which is characterized by a system of constraints in which the variables running through the new dimensions are all constrained to be equal to \(0\). For instance, when starting from the polyhedron \(P\) and adding a third space dimension, the result will be the polyhedron
\[\Big\{ (x,y,0)^T \in \RR^3 \Big| (x,y)^T \in P \Big\}\]INPUT:
m
– integer.
OUTPUT:
This method assigns the projected polyhedron to
self
and does not return anything.Raises a
ValueError
if addingm
new space dimensions would cause the vector space to exceed dimensionself.max_space_dimension()
.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, point sage: x = Variable(0) sage: p = C_Polyhedron( point(3*x) ) sage: p.add_space_dimensions_and_project(1) sage: p.minimized_generators() Generator_System {point(3/1, 0/1)} sage: p.add_space_dimensions_and_project( p.max_space_dimension() ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::add_space_dimensions_and_project(m): adding m new space dimensions exceeds the maximum allowed space dimension.
-
affine_dimension
()¶ Return the affine dimension of
self
.OUTPUT:
An integer. Returns 0 if
self
is empty. Otherwise, returns the affine dimension ofself
.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron sage: x = Variable(0) sage: y = Variable(1) sage: p = C_Polyhedron( 5*x-2*y == x+y-1 ) sage: p.affine_dimension() 1
-
ascii_dump
()¶ Write an ASCII dump to stderr.
EXAMPLES:
sage: sage_cmd = 'from sage.libs.ppl import C_Polyhedron, Variable\n' sage: sage_cmd += 'x = Variable(0)\n' sage: sage_cmd += 'y = Variable(1)\n' sage: sage_cmd += 'p = C_Polyhedron(3*x+2*y==1)\n' sage: sage_cmd += 'p.minimized_generators()\n' sage: sage_cmd += 'p.ascii_dump()\n' sage: from sage.tests.cmdline import test_executable sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd], timeout=100) # long time, indirect doctest sage: print(err) # long time space_dim 2 -ZE -EM +CM +GM +CS +GS -CP -GP -SC +SG con_sys (up-to-date) topology NECESSARILY_CLOSED 2 x 2 SPARSE (sorted) index_first_pending 2 size 3 -1 3 2 = (C) size 3 1 0 0 >= (C) <BLANKLINE> gen_sys (up-to-date) topology NECESSARILY_CLOSED 2 x 2 DENSE (not_sorted) index_first_pending 2 size 3 0 2 -3 L (C) size 3 2 0 1 P (C) <BLANKLINE> sat_c 0 x 0 <BLANKLINE> sat_g 2 x 2 0 0 0 1
-
bounds_from_above
(expr)¶ Test whether the
expr
is bounded from above.INPUT:
expr
– aLinear_Expression
OUTPUT:
Boolean. Returns
True
if and only ifexpr
is bounded from above inself
.Raises a
ValueError
ifexpr
andthis
are dimension-incompatible.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, Linear_Expression sage: x = Variable(0); y = Variable(1) sage: p = C_Polyhedron(y<=0) sage: p.bounds_from_above(x+1) False sage: p.bounds_from_above(Linear_Expression(y)) True sage: p = C_Polyhedron(x<=0) sage: p.bounds_from_above(y+1) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::bounds_from_above(e): this->space_dimension() == 1, e.space_dimension() == 2.
-
bounds_from_below
(expr)¶ Test whether the
expr
is bounded from above.INPUT:
expr
– aLinear_Expression
OUTPUT:
Boolean. Returns
True
if and only ifexpr
is bounded from above inself
.Raises a
ValueError
ifexpr
andthis
are dimension-incompatible.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, Linear_Expression sage: x = Variable(0); y = Variable(1) sage: p = C_Polyhedron(y>=0) sage: p.bounds_from_below(x+1) False sage: p.bounds_from_below(Linear_Expression(y)) True sage: p = C_Polyhedron(x<=0) sage: p.bounds_from_below(y+1) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::bounds_from_below(e): this->space_dimension() == 1, e.space_dimension() == 2.
-
concatenate_assign
(y)¶ Assign to
self
the concatenation ofself
andy
.This functions returns the Cartiesian product of
self
andy
.Viewing a polyhedron as a set of tuples (its points), it is sometimes useful to consider the set of tuples obtained by concatenating an ordered pair of polyhedra. Formally, the concatenation of the polyhedra \(P\) and \(Q\) (taken in this order) is the polyhedron such that
\[R = \Big\{ (x_0,\dots,x_{n-1},y_0,\dots,y_{m-1})^T \in \RR^{n+m} \Big| (x_0,\dots,x_{n-1})^T \in P ,~ (y_0,\dots,y_{m-1})^T \in Q \Big\}\]Another way of seeing it is as follows: first embed polyhedron \(P\) into a vector space of dimension \(n+m\) and then add a suitably renamed-apart version of the constraints defining \(Q\).
INPUT:
m
– integer.
OUTPUT:
This method assigns the concatenated polyhedron to
self
and does not return anything.Raises a
ValueError
ifself
andy
are topology-incompatible or if addingy.space_dimension()
new space dimensions would cause the vector space to exceed dimensionself.max_space_dimension()
.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, NNC_Polyhedron, point sage: x = Variable(0) sage: p1 = C_Polyhedron( point(1*x) ) sage: p2 = C_Polyhedron( point(2*x) ) sage: p1.concatenate_assign(p2) sage: p1.minimized_generators() Generator_System {point(1/1, 2/1)}
The polyhedra must be topology-compatible and not exceed the maximum space dimension:
sage: p1.concatenate_assign( NNC_Polyhedron(1, 'universe') ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::concatenate_assign(y): y is a NNC_Polyhedron. sage: p1.concatenate_assign( C_Polyhedron(p1.max_space_dimension(), 'empty') ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::concatenate_assign(y): concatenation exceeds the maximum allowed space dimension.
-
constrains
(var)¶ Test whether
var
is constrained inself
.INPUT:
var
– aVariable
.
OUTPUT:
Boolean. Returns
True
if and only ifvar
is constrained inself
.Raises a
ValueError
ifvar
is not a space dimension ofself
.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron sage: x = Variable(0) sage: p = C_Polyhedron(1, 'universe') sage: p.constrains(x) False sage: p = C_Polyhedron(x>=0) sage: p.constrains(x) True sage: y = Variable(1) sage: p.constrains(y) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::constrains(v): this->space_dimension() == 1, v.space_dimension() == 2.
-
constraints
()¶ Returns the system of constraints.
See also
minimized_constraints()
.OUTPUT:
EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron sage: x = Variable(0) sage: y = Variable(1) sage: p = C_Polyhedron( y>=0 ) sage: p.add_constraint( x>=0 ) sage: p.add_constraint( x+y>=0 ) sage: p.constraints() Constraint_System {x1>=0, x0>=0, x0+x1>=0} sage: p.minimized_constraints() Constraint_System {x1>=0, x0>=0}
-
contains
(y)¶ Test whether
self
containsy
.INPUT:
y
– aPolyhedron
.
OUTPUT:
Boolean. Returns
True
if and only ifself
containsy
.Raises a
ValueError
ifself
andy
are topology-incompatible or dimension-incompatible.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, NNC_Polyhedron sage: x = Variable(0) sage: y = Variable(1) sage: p0 = C_Polyhedron( x>=0 ) sage: p1 = C_Polyhedron( x>=1 ) sage: p0.contains(p1) True sage: p1.contains(p0) False
Errors are raised if the dimension or topology is not compatible:
sage: p0.contains(C_Polyhedron(y>=0)) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::contains(y): this->space_dimension() == 1, y.space_dimension() == 2. sage: p0.contains(NNC_Polyhedron(x>0)) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::contains(y): y is a NNC_Polyhedron.
-
contains_integer_point
()¶ Test whether
self
contains an integer point.OUTPUT:
Boolean. Returns
True
if and only ifself
contains an integer point.EXAMPLES:
sage: from sage.libs.ppl import Variable, NNC_Polyhedron sage: x = Variable(0) sage: p = NNC_Polyhedron(x>0) sage: p.add_constraint(x<1) sage: p.contains_integer_point() False sage: p.topological_closure_assign() sage: p.contains_integer_point() True
-
difference_assign
(y)¶ Assign to
self
the poly-difference ofself
andy
.For any pair of NNC polyhedra \(P_1\) and \(P_2\) the convex polyhedral difference (or poly-difference) of \(P_1\) and \(P_2\) is defined as the smallest convex polyhedron containing the set-theoretic difference \(P_1\setminus P_2\) of \(P_1\) and \(P_2\).
In general, even if \(P_1\) and \(P_2\) are topologically closed polyhedra, their poly-difference may be a convex polyhedron that is not topologically closed. For this reason, when computing the poly-difference of two
C_Polyhedron
, the library will enforce the topological closure of the result.INPUT:
y
– aPolyhedron
OUTPUT:
This method assigns the poly-difference to
self
and does not return anything.Raises a
ValueError
ifself
and andy
are topology-incompatible or dimension-incompatible.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, point, closure_point, NNC_Polyhedron sage: x = Variable(0) sage: p = NNC_Polyhedron( point(0*x) ) sage: p.add_generator( point(1*x) ) sage: p.poly_difference_assign(NNC_Polyhedron( point(0*x) )) sage: p.minimized_constraints() Constraint_System {-x0+1>=0, x0>0}
The poly-difference of
C_polyhedron
is really its closure:sage: p = C_Polyhedron( point(0*x) ) sage: p.add_generator( point(1*x) ) sage: p.poly_difference_assign(C_Polyhedron( point(0*x) )) sage: p.minimized_constraints() Constraint_System {x0>=0, -x0+1>=0}
self
andy
must be dimension- and topology-compatible, or an exception is raised:sage: y = Variable(1) sage: p.poly_difference_assign( C_Polyhedron(y>=0) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::poly_difference_assign(y): this->space_dimension() == 1, y.space_dimension() == 2. sage: p.poly_difference_assign( NNC_Polyhedron(x+y<1) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::poly_difference_assign(y): y is a NNC_Polyhedron.
-
drop_some_non_integer_points
()¶ Possibly tighten
self
by dropping some points with non-integer coordinates.The modified polyhedron satisfies:
- it is (not necessarily strictly) contained in the original polyhedron.
- integral vertices (generating points with integer coordinates) of the original polyhedron are not removed.
Note
The modified polyhedron is not neccessarily a lattice polyhedron; Some vertices will, in general, still be rational. Lattice points interior to the polyhedron may be lost in the process.
EXAMPLES:
sage: from sage.libs.ppl import Variable, NNC_Polyhedron, Constraint_System sage: x = Variable(0) sage: y = Variable(1) sage: cs = Constraint_System() sage: cs.insert( x>=0 ) sage: cs.insert( y>=0 ) sage: cs.insert( 3*x+2*y<5 ) sage: p = NNC_Polyhedron(cs) sage: p.minimized_generators() Generator_System {point(0/1, 0/1), closure_point(0/2, 5/2), closure_point(5/3, 0/3)} sage: p.drop_some_non_integer_points() sage: p.minimized_generators() Generator_System {point(0/1, 0/1), point(0/1, 2/1), point(4/3, 0/3)}
-
generators
()¶ Returns the system of generators.
See also
minimized_generators()
.OUTPUT:
EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, point sage: x = Variable(0) sage: y = Variable(1) sage: p = C_Polyhedron(3,'empty') sage: p.add_generator( point(-x-y) ) sage: p.add_generator( point(0) ) sage: p.add_generator( point(+x+y) ) sage: p.generators() Generator_System {point(-1/1, -1/1, 0/1), point(0/1, 0/1, 0/1), point(1/1, 1/1, 0/1)} sage: p.minimized_generators() Generator_System {point(-1/1, -1/1, 0/1), point(1/1, 1/1, 0/1)}
-
intersection_assign
(y)¶ Assign to
self
the intersection ofself
andy
.INPUT:
y
– aPolyhedron
OUTPUT:
This method assigns the intersection to
self
and does not return anything.Raises a
ValueError
ifself
and andy
are topology-incompatible or dimension-incompatible.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, NNC_Polyhedron sage: x = Variable(0) sage: y = Variable(1) sage: p = C_Polyhedron( 1*x+0*y >= 0 ) sage: p.intersection_assign( C_Polyhedron(y>=0) ) sage: p.constraints() Constraint_System {x0>=0, x1>=0} sage: z = Variable(2) sage: p.intersection_assign( C_Polyhedron(z>=0) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::intersection_assign(y): this->space_dimension() == 2, y.space_dimension() == 3. sage: p.intersection_assign( NNC_Polyhedron(x+y<1) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::intersection_assign(y): y is a NNC_Polyhedron.
-
is_bounded
()¶ Test whether
self
is bounded.OUTPUT:
Boolean. Returns
True
if and only ifself
is a bounded polyhedron.EXAMPLES:
sage: from sage.libs.ppl import Variable, NNC_Polyhedron, point, closure_point, ray sage: x = Variable(0) sage: p = NNC_Polyhedron( point(0*x) ) sage: p.add_generator( closure_point(1*x) ) sage: p.is_bounded() True sage: p.add_generator( ray(1*x) ) sage: p.is_bounded() False
-
is_discrete
()¶ Test whether
self
is discrete.OUTPUT:
Boolean. Returns
True
if and only ifself
is discrete.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, point, ray sage: x = Variable(0); y = Variable(1) sage: p = C_Polyhedron( point(1*x+2*y) ) sage: p.is_discrete() True sage: p.add_generator( point(x) ) sage: p.is_discrete() False
-
is_disjoint_from
(y)¶ Tests whether
self
andy
are disjoint.INPUT:
y
– aPolyhedron
.
OUTPUT:
Boolean. Returns
True
if and only ifself
andy
are disjoint.Rayises a
ValueError
ifself
andy
are topology-incompatible or dimension-incompatible.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, NNC_Polyhedron sage: x = Variable(0); y = Variable(1) sage: C_Polyhedron(x<=0).is_disjoint_from( C_Polyhedron(x>=1) ) True
This is not allowed:
sage: x = Variable(0); y = Variable(1) sage: poly_1d = C_Polyhedron(x<=0) sage: poly_2d = C_Polyhedron(x+0*y>=1) sage: poly_1d.is_disjoint_from(poly_2d) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::intersection_assign(y): this->space_dimension() == 1, y.space_dimension() == 2.
Nor is this:
sage: x = Variable(0); y = Variable(1) sage: c_poly = C_Polyhedron( x<=0 ) sage: nnc_poly = NNC_Polyhedron( x >0 ) sage: c_poly.is_disjoint_from(nnc_poly) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::intersection_assign(y): y is a NNC_Polyhedron. sage: NNC_Polyhedron(c_poly).is_disjoint_from(nnc_poly) True
-
is_empty
()¶ Test if
self
is an empty polyhedron.OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.libs.ppl import C_Polyhedron sage: C_Polyhedron(3, 'empty').is_empty() True sage: C_Polyhedron(3, 'universe').is_empty() False
-
is_topologically_closed
()¶ Tests if
self
is topologically closed.OUTPUT:
Returns
True
if and only ifself
is a topologically closed subset of the ambient vector space.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, NNC_Polyhedron sage: x = Variable(0); y = Variable(1) sage: C_Polyhedron(3, 'universe').is_topologically_closed() True sage: C_Polyhedron( x>=1 ).is_topologically_closed() True sage: NNC_Polyhedron( x>1 ).is_topologically_closed() False
-
is_universe
()¶ Test if
self
is a universe (space-filling) polyhedron.OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.libs.ppl import C_Polyhedron sage: C_Polyhedron(3, 'empty').is_universe() False sage: C_Polyhedron(3, 'universe').is_universe() True
-
max_space_dimension
()¶ Return the maximum space dimension all kinds of Polyhedron can handle.
OUTPUT:
Integer.
EXAMPLES:
sage: from sage.libs.ppl import C_Polyhedron sage: C_Polyhedron(1, 'empty').max_space_dimension() # random output 1152921504606846974 sage: C_Polyhedron(1, 'empty').max_space_dimension() 357913940 # 32-bit 1152921504606846974 # 64-bit
-
maximize
(expr)¶ Maximize
expr
.INPUT:
expr
– aLinear_Expression
.
OUTPUT:
A dictionary with the following keyword:value pair:
'bounded'
: Boolean. Whether the linear expressionexpr
is bounded from above onself
.
If
expr
is bounded from above, the following additional keyword:value pairs are set to provide information about the supremum:'sup_n'
: Integer. The numerator of the supremum value.'sup_d'
: Non-zero integer. The denominator of the supremum value.'maximum'
: Boolean.True
if and only if the supremum is also the maximum value.'generator'
: aGenerator
. A point or closure point where expr reaches its supremum value.
EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, NNC_Polyhedron, Constraint_System, Linear_Expression sage: x = Variable(0); y = Variable(1) sage: cs = Constraint_System() sage: cs.insert( x>=0 ) sage: cs.insert( y>=0 ) sage: cs.insert( 3*x+5*y<=10 ) sage: p = C_Polyhedron(cs) sage: p.maximize( x+y ) {'bounded': True, 'generator': point(10/3, 0/3), 'maximum': True, 'sup_d': 3, 'sup_n': 10}
Unbounded case:
sage: cs = Constraint_System() sage: cs.insert( x>0 ) sage: p = NNC_Polyhedron(cs) sage: p.maximize( +x ) {'bounded': False} sage: p.maximize( -x ) {'bounded': True, 'generator': closure_point(0/1), 'maximum': False, 'sup_d': 1, 'sup_n': 0}
-
minimize
(expr)¶ Minimize
expr
.INPUT:
expr
– aLinear_Expression
.
OUTPUT:
A dictionary with the following keyword:value pair:
'bounded'
: Boolean. Whether the linear expressionexpr
is bounded from below onself
.
If
expr
is bounded from below, the following additional keyword:value pairs are set to provide information about the infimum:'inf_n'
: Integer. The numerator of the infimum value.'inf_d'
: Non-zero integer. The denominator of the infimum value.'minimum'
: Boolean.True
if and only if the infimum is also the minimum value.'generator'
: aGenerator
. A point or closure point where expr reaches its infimum value.
EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, NNC_Polyhedron, Constraint_System, Linear_Expression sage: x = Variable(0); y = Variable(1) sage: cs = Constraint_System() sage: cs.insert( x>=0 ) sage: cs.insert( y>=0 ) sage: cs.insert( 3*x+5*y<=10 ) sage: p = C_Polyhedron(cs) sage: p.minimize( x+y ) {'bounded': True, 'generator': point(0/1, 0/1), 'inf_d': 1, 'inf_n': 0, 'minimum': True}
Unbounded case:
sage: cs = Constraint_System() sage: cs.insert( x>0 ) sage: p = NNC_Polyhedron(cs) sage: p.minimize( +x ) {'bounded': True, 'generator': closure_point(0/1), 'inf_d': 1, 'inf_n': 0, 'minimum': False} sage: p.minimize( -x ) {'bounded': False}
-
minimized_constraints
()¶ Returns the minimized system of constraints.
See also
constraints()
.OUTPUT:
EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron sage: x = Variable(0) sage: y = Variable(1) sage: p = C_Polyhedron( y>=0 ) sage: p.add_constraint( x>=0 ) sage: p.add_constraint( x+y>=0 ) sage: p.constraints() Constraint_System {x1>=0, x0>=0, x0+x1>=0} sage: p.minimized_constraints() Constraint_System {x1>=0, x0>=0}
-
minimized_generators
()¶ Returns the minimized system of generators.
See also
generators()
.OUTPUT:
EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, point sage: x = Variable(0) sage: y = Variable(1) sage: p = C_Polyhedron(3,'empty') sage: p.add_generator( point(-x-y) ) sage: p.add_generator( point(0) ) sage: p.add_generator( point(+x+y) ) sage: p.generators() Generator_System {point(-1/1, -1/1, 0/1), point(0/1, 0/1, 0/1), point(1/1, 1/1, 0/1)} sage: p.minimized_generators() Generator_System {point(-1/1, -1/1, 0/1), point(1/1, 1/1, 0/1)}
-
poly_difference_assign
(y)¶ Assign to
self
the poly-difference ofself
andy
.For any pair of NNC polyhedra \(P_1\) and \(P_2\) the convex polyhedral difference (or poly-difference) of \(P_1\) and \(P_2\) is defined as the smallest convex polyhedron containing the set-theoretic difference \(P_1\setminus P_2\) of \(P_1\) and \(P_2\).
In general, even if \(P_1\) and \(P_2\) are topologically closed polyhedra, their poly-difference may be a convex polyhedron that is not topologically closed. For this reason, when computing the poly-difference of two
C_Polyhedron
, the library will enforce the topological closure of the result.INPUT:
y
– aPolyhedron
OUTPUT:
This method assigns the poly-difference to
self
and does not return anything.Raises a
ValueError
ifself
and andy
are topology-incompatible or dimension-incompatible.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, point, closure_point, NNC_Polyhedron sage: x = Variable(0) sage: p = NNC_Polyhedron( point(0*x) ) sage: p.add_generator( point(1*x) ) sage: p.poly_difference_assign(NNC_Polyhedron( point(0*x) )) sage: p.minimized_constraints() Constraint_System {-x0+1>=0, x0>0}
The poly-difference of
C_polyhedron
is really its closure:sage: p = C_Polyhedron( point(0*x) ) sage: p.add_generator( point(1*x) ) sage: p.poly_difference_assign(C_Polyhedron( point(0*x) )) sage: p.minimized_constraints() Constraint_System {x0>=0, -x0+1>=0}
self
andy
must be dimension- and topology-compatible, or an exception is raised:sage: y = Variable(1) sage: p.poly_difference_assign( C_Polyhedron(y>=0) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::poly_difference_assign(y): this->space_dimension() == 1, y.space_dimension() == 2. sage: p.poly_difference_assign( NNC_Polyhedron(x+y<1) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::poly_difference_assign(y): y is a NNC_Polyhedron.
-
poly_hull_assign
(y)¶ Assign to
self
the poly-hull ofself
andy
.For any pair of NNC polyhedra \(P_1\) and \(P_2\), the convex polyhedral hull (or poly-hull) of is the smallest NNC polyhedron that includes both \(P_1\) and \(P_2\). The poly-hull of any pair of closed polyhedra in is also closed.
INPUT:
y
– aPolyhedron
OUTPUT:
This method assigns the poly-hull to
self
and does not return anything.Raises a
ValueError
ifself
and andy
are topology-incompatible or dimension-incompatible.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, point, NNC_Polyhedron sage: x = Variable(0) sage: y = Variable(1) sage: p = C_Polyhedron( point(1*x+0*y) ) sage: p.poly_hull_assign(C_Polyhedron( point(0*x+1*y) )) sage: p.generators() Generator_System {point(0/1, 1/1), point(1/1, 0/1)}
self
andy
must be dimension- and topology-compatible, or an exception is raised:sage: z = Variable(2) sage: p.poly_hull_assign( C_Polyhedron(z>=0) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::poly_hull_assign(y): this->space_dimension() == 2, y.space_dimension() == 3. sage: p.poly_hull_assign( NNC_Polyhedron(x+y<1) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::poly_hull_assign(y): y is a NNC_Polyhedron.
-
relation_with
(arg)¶ Return the relations holding between the polyhedron
self
and the generator or constraintarg
.INPUT:
arg
– aGenerator
or aConstraint
.
OUTPUT:
A
Poly_Gen_Relation
or aPoly_Con_Relation
according to the type of the input.Raises
ValueError
ifself
and the generator/constraintarg
are dimension-incompatible.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, point, ray, Poly_Con_Relation sage: x = Variable(0); y = Variable(1) sage: p = C_Polyhedron(2, 'empty') sage: p.add_generator( point(1*x+0*y) ) sage: p.add_generator( point(0*x+1*y) ) sage: p.minimized_constraints() Constraint_System {x0+x1-1==0, -x1+1>=0, x1>=0} sage: p.relation_with( point(1*x+1*y) ) nothing sage: p.relation_with( point(1*x+1*y, 2) ) subsumes sage: p.relation_with( x+y==-1 ) is_disjoint sage: p.relation_with( x==y ) strictly_intersects sage: p.relation_with( x+y<=1 ) is_included, saturates sage: p.relation_with( x+y<1 ) is_disjoint, saturates
In a Sage program you will usually use
relation_with()
together withimplies()
orimplies()
, for example:sage: p.relation_with( x+y<1 ).implies(Poly_Con_Relation.saturates()) True
You can only get relations with dimension-compatible generators or constraints:
sage: z = Variable(2) sage: p.relation_with( point(x+y+z) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::relation_with(g): this->space_dimension() == 2, g.space_dimension() == 3. sage: p.relation_with( z>0 ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::relation_with(c): this->space_dimension() == 2, c.space_dimension() == 3.
-
remove_higher_space_dimensions
(new_dimension)¶ Remove the higher dimensions of the vector space so that the resulting space will have dimension
new_dimension
.OUTPUT:
This method modifies
self
and does not return anything.Raises a
ValueError
ifnew_dimensions
is greater than the space dimension ofself
.EXAMPLES:
sage: from sage.libs.ppl import C_Polyhedron, Variable sage: x = Variable(0) sage: y = Variable(1) sage: p = C_Polyhedron(3*x+0*y==2) sage: p.remove_higher_space_dimensions(1) sage: p.minimized_constraints() Constraint_System {3*x0-2==0} sage: p.remove_higher_space_dimensions(2) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::remove_higher_space_dimensions(nd): this->space_dimension() == 1, required space dimension == 2.
-
space_dimension
()¶ Return the dimension of the vector space enclosing
self
.OUTPUT:
Integer.
EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron sage: x = Variable(0) sage: y = Variable(1) sage: p = C_Polyhedron( 5*x-2*y >= x+y-1 ) sage: p.space_dimension() 2
-
strictly_contains
(y)¶ Test whether
self
strictly containsy
.INPUT:
y
– aPolyhedron
.
OUTPUT:
Boolean. Returns
True
if and only ifself
containsy
andself
does not equaly
.Raises a
ValueError
ifself
andy
are topology-incompatible or dimension-incompatible.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, NNC_Polyhedron sage: x = Variable(0) sage: y = Variable(1) sage: p0 = C_Polyhedron( x>=0 ) sage: p1 = C_Polyhedron( x>=1 ) sage: p0.strictly_contains(p1) True sage: p1.strictly_contains(p0) False
Errors are raised if the dimension or topology is not compatible:
sage: p0.strictly_contains(C_Polyhedron(y>=0)) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::contains(y): this->space_dimension() == 1, y.space_dimension() == 2. sage: p0.strictly_contains(NNC_Polyhedron(x>0)) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::contains(y): y is a NNC_Polyhedron.
-
topological_closure_assign
()¶ Assign to
self
its topological closure.EXAMPLES:
sage: from sage.libs.ppl import Variable, NNC_Polyhedron sage: x = Variable(0) sage: p = NNC_Polyhedron(x>0) sage: p.is_topologically_closed() False sage: p.topological_closure_assign() sage: p.is_topologically_closed() True sage: p.minimized_constraints() Constraint_System {x0>=0}
-
unconstrain
(var)¶ Compute the cylindrification of
self
with respect to space dimensionvar
.INPUT:
var
– aVariable
. The space dimension that will be unconstrained. Exceptions:
OUTPUT:
This method assigns the cylindrification to
self
and does not return anything.Raises a
ValueError
ifvar
is not a space dimension ofself
.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, point sage: x = Variable(0) sage: y = Variable(1) sage: p = C_Polyhedron( point(x+y) ); p A 0-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point sage: p.unconstrain(x); p A 1-dimensional polyhedron in QQ^2 defined as the convex hull of 1 point, 1 line sage: z = Variable(2) sage: p.unconstrain(z) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::unconstrain(var): this->space_dimension() == 2, required space dimension == 3.
-
upper_bound_assign
(y)¶ Assign to
self
the poly-hull ofself
andy
.For any pair of NNC polyhedra \(P_1\) and \(P_2\), the convex polyhedral hull (or poly-hull) of is the smallest NNC polyhedron that includes both \(P_1\) and \(P_2\). The poly-hull of any pair of closed polyhedra in is also closed.
INPUT:
y
– aPolyhedron
OUTPUT:
This method assigns the poly-hull to
self
and does not return anything.Raises a
ValueError
ifself
and andy
are topology-incompatible or dimension-incompatible.EXAMPLES:
sage: from sage.libs.ppl import Variable, C_Polyhedron, point, NNC_Polyhedron sage: x = Variable(0) sage: y = Variable(1) sage: p = C_Polyhedron( point(1*x+0*y) ) sage: p.poly_hull_assign(C_Polyhedron( point(0*x+1*y) )) sage: p.generators() Generator_System {point(0/1, 1/1), point(1/1, 0/1)}
self
andy
must be dimension- and topology-compatible, or an exception is raised:sage: z = Variable(2) sage: p.poly_hull_assign( C_Polyhedron(z>=0) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::poly_hull_assign(y): this->space_dimension() == 2, y.space_dimension() == 3. sage: p.poly_hull_assign( NNC_Polyhedron(x+y<1) ) Traceback (most recent call last): ... ValueError: PPL::C_Polyhedron::poly_hull_assign(y): y is a NNC_Polyhedron.
-
-
class
sage.libs.ppl.
Variable
¶ Bases:
object
Wrapper for PPL’s
Variable
class.A dimension of the vector space.
An object of the class Variable represents a dimension of the space, that is one of the Cartesian axes. Variables are used as basic blocks in order to build more complex linear expressions. Each variable is identified by a non-negative integer, representing the index of the corresponding Cartesian axis (the first axis has index 0). The space dimension of a variable is the dimension of the vector space made by all the Cartesian axes having an index less than or equal to that of the considered variable; thus, if a variable has index \(i\), its space dimension is \(i+1\).
INPUT:
i
– integer. The index of the axis.
OUTPUT:
A
Variable
EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(123) sage: x.id() 123 sage: x x123
Note that the “meaning” of an object of the class Variable is completely specified by the integer index provided to its constructor: be careful not to be mislead by C++ language variable names. For instance, in the following example the linear expressions
e1
ande2
are equivalent, since the two variablesx
andz
denote the same Cartesian axis:sage: x = Variable(0) sage: y = Variable(1) sage: z = Variable(0) sage: e1 = x + y; e1 x0+x1 sage: e2 = y + z; e2 x0+x1 sage: e1 - e2 0
-
OK
()¶ Checks if all the invariants are satisfied.
OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(0) sage: x.OK() True
-
id
()¶ Return the index of the Cartesian axis associated to the variable.
EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(123) sage: x.id() 123
-
space_dimension
()¶ Return the dimension of the vector space enclosing
self
.OUTPUT:
Integer. The returned value is
self.id()+1
.EXAMPLES:
sage: from sage.libs.ppl import Variable sage: x = Variable(0) sage: x.space_dimension() 1
-
class
sage.libs.ppl.
Variables_Set
¶ Bases:
object
Wrapper for PPL’s
Variables_Set
class.A set of variables’ indexes.
EXAMPLES:
Build the empty set of variable indexes:
sage: from sage.libs.ppl import Variable, Variables_Set sage: Variables_Set() Variables_Set of cardinality 0
Build the singleton set of indexes containing the index of the variable:
sage: v123 = Variable(123) sage: Variables_Set(v123) Variables_Set of cardinality 1
Build the set of variables’ indexes in the range from one variable to another variable:
sage: v127 = Variable(127) sage: Variables_Set(v123,v127) Variables_Set of cardinality 5
-
OK
()¶ Checks if all the invariants are satisfied.
OUTPUT:
Boolean.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Variables_Set sage: v123 = Variable(123) sage: S = Variables_Set(v123) sage: S.OK() True
-
ascii_dump
()¶ Write an ASCII dump to stderr.
EXAMPLES:
sage: sage_cmd = 'from sage.libs.ppl import Variable, Variables_Set\n' sage: sage_cmd += 'v123 = Variable(123)\n' sage: sage_cmd += 'S = Variables_Set(v123)\n' sage: sage_cmd += 'S.ascii_dump()\n' sage: from sage.tests.cmdline import test_executable sage: (out, err, ret) = test_executable(['sage', '-c', sage_cmd], timeout=100) # long time, indirect doctest sage: print(err) # long time <BLANKLINE> variables( 1 ) 123
-
insert
(v)¶ Inserts the index of variable \(v\) into the set.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Variables_Set sage: S = Variables_Set() sage: v123 = Variable(123) sage: S.insert(v123) sage: S.space_dimension() 124
-
space_dimension
()¶ Returns the dimension of the smallest vector space enclosing all the variables whose indexes are in the set.
OUTPUT:
Integer.
EXAMPLES:
sage: from sage.libs.ppl import Variable, Variables_Set sage: v123 = Variable(123) sage: S = Variables_Set(v123) sage: S.space_dimension() 124
-
-
sage.libs.ppl.
closure_point
(expression=0, divisor=1)¶ Constuct a closure point.
See
Generator.closure_point()
for documentation.EXAMPLES:
sage: from sage.libs.ppl import Variable, closure_point sage: y = Variable(1) sage: closure_point(2*y, 5) closure_point(0/5, 2/5)
-
sage.libs.ppl.
equation
(expression)¶ Constuct an equation.
INPUT:
expression
– aLinear_Expression
.
OUTPUT:
The equation
expression
== 0.EXAMPLES:
sage: from sage.libs.ppl import Variable, equation sage: y = Variable(1) sage: 2*y+1 == 0 2*x1+1==0 sage: equation(2*y+1) 2*x1+1==0
-
sage.libs.ppl.
inequality
(expression)¶ Constuct an inequality.
INPUT:
expression
– aLinear_Expression
.
OUTPUT:
The inequality
expression
>= 0.EXAMPLES:
sage: from sage.libs.ppl import Variable, inequality sage: y = Variable(1) sage: 2*y+1 >= 0 2*x1+1>=0 sage: inequality(2*y+1) 2*x1+1>=0
-
sage.libs.ppl.
line
(expression)¶ Constuct a line.
See
Generator.line()
for documentation.EXAMPLES:
sage: from sage.libs.ppl import Variable, line sage: y = Variable(1) sage: line(2*y) line(0, 1)
-
sage.libs.ppl.
point
(expression=0, divisor=1)¶ Constuct a point.
See
Generator.point()
for documentation.EXAMPLES:
sage: from sage.libs.ppl import Variable, point sage: y = Variable(1) sage: point(2*y, 5) point(0/5, 2/5)
-
sage.libs.ppl.
ray
(expression)¶ Constuct a ray.
See
Generator.ray()
for documentation.EXAMPLES:
sage: from sage.libs.ppl import Variable, ray sage: y = Variable(1) sage: ray(2*y) ray(0, 1)
-
sage.libs.ppl.
strict_inequality
(expression)¶ Constuct a strict inequality.
INPUT:
expression
– aLinear_Expression
.
OUTPUT:
The inequality
expression
> 0.EXAMPLES:
sage: from sage.libs.ppl import Variable, strict_inequality sage: y = Variable(1) sage: 2*y+1 > 0 2*x1+1>0 sage: strict_inequality(2*y+1) 2*x1+1>0