Cython wrapper for the Parma Polyhedra Library (PPL)
The Parma Polyhedra Library (PPL) is a library for polyhedral
computations over . 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) or Constraint (strict inequalities, non-strict inequalities, or equations). Coordinates are always specified via linear polynomials in Variable
All coordinates of rays and lines as well as all coefficients of constraint relations are (arbitrary precision) integers. Only the generators point() and closure_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:
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:
AUTHORS:
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. See NNC_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:
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.
Bases: object
Wrapper for PPL’s Constraint class.
An object of the class Constraint is either:
where is the dimension of the space,
is the integer
coefficient of variable
, and
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
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
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 f -RPI_V +RPI -NNC_V +NNC
Return the coefficient of the variable v.
INPUT:
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
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)
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
Test whether self is an equality.
OUTPUT:
Boolean. Returns True if and only if self 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
Test whether self and c are equivalent.
INPUT:
OUTPUT:
Boolean. Returns True if and only if self and c 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
Test whether self is an inconsistent constraint, that is, always false.
An inconsistent constraint can have either one of the following forms:
OUTPUT:
Boolean. Returns True if and only if self 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
Test whether self is an inequality.
OUTPUT:
Boolean. Returns True if and only if self 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
Test whether self is a non-strict inequality.
OUTPUT:
Boolean. Returns True if and only if self 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
Test whether self is a strict inequality.
OUTPUT:
Boolean. Returns True if and only if self 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
Test whether self is a tautological constraint.
A tautology can have either one of the following forms:
OUTPUT:
Boolean. Returns True if and only if self 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
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
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'
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, -6*x0+3*x1>0, -x0+7*x1>=0}
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
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 4 (sorted)
index_first_pending 1
-1 3 -2 -1 >
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 {}
Return True if and only if self 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
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
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 into the constraint system.
INPUT:
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}
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
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: Constraint_System_iterator(cs).next()
-5*x0+2*x1>0
sage: list(cs)
[-5*x0+2*x1>0, 2*x0-x1==0, -x0+7*x1>=0]
x.next() -> the next value, or raise StopIteration
Bases: object
Wrapper for PPL’s Generator class.
An object of the class Generator is one of the following:
- a line
- a ray
- a point
- a closure point
where is the dimension of the space and, for points and
closure points,
is the divisor.
INPUT/OUTPUT:
Use the helper functions line(), ray(), point(), and closure_point() to construct generators. Analogous class methods are also available, see Generator.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)
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
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 f -RPI_V +RPI -NNC_V -NNC
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:
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.
Return the coefficient of the variable v.
INPUT:
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
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)
If self is either a point or a closure point, return its divisor.
OUTPUT:
An integer. If self is a ray or a line, raises ValueError.
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.
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
Test whether self and g are equivalent.
INPUT:
OUTPUT:
Boolean. Returns True if and only if self and g 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
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
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
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
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
Construct a line.
INPUT:
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.
Construct a point.
INPUT:
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.
Construct a ray.
INPUT:
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.
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
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'
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)}
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
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 3 (sorted)
index_first_pending 1
1 3 2 P
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 {}
Return True if and only if self 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 into the generator system.
The number of space dimensions of self is increased, if needed.
INPUT:
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)}
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
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: Generator_System_iterator(gs).next()
line(5, -2)
sage: list(gs)
[line(5, -2), ray(2, -1), point(2/5, -7/5), closure_point(9/2, -1/2)]
x.next() -> the next value, or raise StopIteration
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 as
A single argument Linear_Expression(arg) is interpreted as
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
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
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
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 f -RPI_V -RPI -NNC_V -NNC
Return the coefficient of the variable v.
INPUT:
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
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)
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
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
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
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:
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)
Check if all the invariants are satisfied.
OUTPUT:
True if and only if self 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
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.
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.
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
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
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.
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
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
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 doesn't have an optimizing point.
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'
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)
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.
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.
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'}
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
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 class NNC_Polyhedron. The reason for defining two different classes is that objects of the class C_Polyhedron are characterized by a more efficient implementation, requiring less time and memory resources.
INPUT:
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.
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 from relation_with(). You can also get pre-defined relations from the class methods nothing(), is_disjoint(), strictly_intersects(), is_included(), and saturates().
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]
Check if all the invariants are satisfied.
EXAMPLES:
sage: from sage.libs.ppl import Poly_Con_Relation
sage: Poly_Con_Relation.nothing().OK()
True
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
Test whether self implies y.
INPUT:
OUTPUT:
Boolean. True if and only if self implies y.
EXAMPLES:
sage: from sage.libs.ppl import Poly_Con_Relation
sage: nothing = Poly_Con_Relation.nothing()
sage: nothing.implies( nothing )
True
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
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
Return the assertion that says nothing.
OUTPUT:
EXAMPLES:
sage: from sage.libs.ppl import Poly_Con_Relation
sage: Poly_Con_Relation.nothing()
nothing
Return the assertion “”.
OUTPUT:
EXAMPLES:
sage: from sage.libs.ppl import Poly_Con_Relation
sage: Poly_Con_Relation.saturates()
saturates
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
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 from relation_with(). You can also get pre-defined relations from the class methods nothing() and subsumes().
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
Check if all the invariants are satisfied.
EXAMPLES:
sage: from sage.libs.ppl import Poly_Gen_Relation
sage: Poly_Gen_Relation.nothing().OK()
True
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
Test whether self implies y.
INPUT:
OUTPUT:
Boolean. True if and only if self implies y.
EXAMPLES:
sage: from sage.libs.ppl import Poly_Gen_Relation
sage: nothing = Poly_Gen_Relation.nothing()
sage: nothing.implies( nothing )
True
Return the assertion that says nothing.
OUTPUT:
EXAMPLES:
sage: from sage.libs.ppl import Poly_Gen_Relation
sage: Poly_Gen_Relation.nothing()
nothing
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
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 and NNC_Polyhedron. You cannot instantiate this class.
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:
OUTPUT:
True if and only if self satisfies all the invariants and either check_not_empty is False or self 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 a constraint to the polyhedron.
Adds a copy of constraint c to the system of constraints of self, without minimizing the result.
See alse add_constraints().
INPUT:
OUTPUT:
This method modifies the polyhedron self and does not return anything.
Raises a ValueError if self and the constraint c 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 to the polyhedron.
Adds a copy of constraints in cs to the system of constraints of self, without minimizing the result.
See alse add_constraint().
INPUT:
OUTPUT:
This method modifies the polyhedron self and does not return anything.
Raises a ValueError if self and the constraints in cs 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 a generator to the polyhedron.
Adds a copy of constraint c to the system of generators of self, without minimizing the result.
INPUT:
OUTPUT:
This method modifies the polyhedron self and does not return anything.
Raises a ValueError if self and the generator g are topology-incompatible or dimension-incompatible, or if self is an empty polyhedron and g 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 to the polyhedron.
Adds a copy of the generators in gs to the system of generators of self, without minimizing the result.
See alse add_generator().
INPUT:
OUTPUT:
This method modifies the polyhedron self and does not return anything.
Raises a ValueError if self and one of the generators in gs are topology-incompatible or dimension-incompatible, or if self is an empty polyhedron and gs 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 m new space dimensions and embed self 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 and adding a third space
dimension, the result will be the polyhedron
INPUT:
OUTPUT:
This method assigns the embedded polyhedron to self and does not return anything.
Raises a ValueError if adding m new space dimensions would cause the vector space to exceed dimension self.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 m new space dimensions and embed self 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 .
For instance, when starting from the polyhedron
and adding
a third space dimension, the result will be the polyhedron
INPUT:
OUTPUT:
This method assigns the projected polyhedron to self and does not return anything.
Raises a ValueError if adding m new space dimensions would cause the vector space to exceed dimension self.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.
Return the affine dimension of self.
OUTPUT:
An integer. Returns 0 if self is empty. Otherwise, returns the affine dimension of self.
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
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 3 (sorted)
index_first_pending 2
-1 3 2 =
1 0 0 >=
gen_sys (up-to-date)
topology NECESSARILY_CLOSED
2 x 3 (not_sorted)
index_first_pending 2
0 2 -3 L
2 0 1 P
sat_c
0 x 0
sat_g
2 x 2
0 0
0 1
Test whether the expr is bounded from above.
INPUT:
OUTPUT:
Boolean. Returns True if and only if expr is bounded from above in self.
Raises a ValueError if expr and this 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.
Test whether the expr is bounded from above.
INPUT:
OUTPUT:
Boolean. Returns True if and only if expr is bounded from above in self.
Raises a ValueError if expr and this 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.
Assign to self the concatenation of self and y.
This functions returns the Cartiesian product of self and y.
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 and
(taken in this
order) is the polyhedron such that
Another way of seeing it is as follows: first embed polyhedron
into a vector space of dimension
and then add a
suitably renamed-apart version of the constraints defining
.
INPUT:
OUTPUT:
This method assigns the concatenated polyhedron to self and does not return anything.
Raises a ValueError if self and y are topology-incompatible or if adding y.space_dimension() new space dimensions would cause the vector space to exceed dimension self.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.
Test whether var is constrained in self.
INPUT:
OUTPUT:
Boolean. Returns True if and only if var is constrained in self.
Raises a ValueError if var is not a space dimension of self.
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.
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}
Test whether self contains y.
INPUT:
OUTPUT:
Boolean. Returns True if and only if self contains y.
Raises a ValueError if self and y 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.
Test whether self contains an integer point.
OUTPUT:
Boolean. Returns True if and only if self 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
Assign to self the poly-difference of self and y.
For any pair of NNC polyhedra and
the convex
polyhedral difference (or poly-difference) of
and
is defined as the smallest convex polyhedron containing the
set-theoretic difference
of
and
.
In general, even if and
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:
OUTPUT:
This method assigns the poly-difference to self and does not return anything.
Raises a ValueError if self and and y 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 and y 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.
Possibly tighten self by dropping some points with non-integer coordinates.
The modified polyhedron satisfies:
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)}
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)}
Assign to self the intersection of self and y.
INPUT:
OUTPUT:
This method assigns the intersection to self and does not return anything.
Raises a ValueError if self and and y 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.
Test whether self is bounded.
OUTPUT:
Boolean. Returns True if and only if self 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
Test whether self is discrete.
OUTPUT:
Boolean. Returns True if and only if self 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
Tests whether self and y are disjoint.
INPUT:
OUTPUT:
Boolean. Returns True if and only if self and y are disjoint.
Rayises a ValueError if self and y 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
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
Tests if self is topologically closed.
OUTPUT:
Returns True if and only if self 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
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
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
1152921504606846973
sage: max_dim = C_Polyhedron(1, 'empty').max_space_dimension()
sage: max_dim in (357913939, 1152921504606846973) # 32 or 64 bit
True
Maximize expr.
INPUT:
OUTPUT:
A dictionary with the following keyword:value pair:
If expr is bounded from above, the following additional keyword:value pairs are set to provide information about the supremum:
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 )
{'sup_d': 3, 'sup_n': 10, 'bounded': True, 'maximum': True, 'generator': point(10/3, 0/3)}
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 )
{'sup_d': 1, 'sup_n': 0, 'bounded': True, 'maximum': False, 'generator': closure_point(0/1)}
Minimize expr.
INPUT:
OUTPUT:
A dictionary with the following keyword:value pair:
If expr is bounded from below, the following additional keyword:value pairs are set to provide information about the infimum:
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 )
{'minimum': True, 'bounded': True, 'inf_d': 1, 'generator': point(0/1, 0/1), 'inf_n': 0}
Unbounded case:
sage: cs = Constraint_System()
sage: cs.insert( x>0 )
sage: p = NNC_Polyhedron(cs)
sage: p.minimize( +x )
{'minimum': False, 'bounded': True, 'inf_d': 1, 'generator': closure_point(0/1), 'inf_n': 0}
sage: p.minimize( -x )
{'bounded': False}
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}
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)}
Assign to self the poly-difference of self and y.
For any pair of NNC polyhedra and
the convex
polyhedral difference (or poly-difference) of
and
is defined as the smallest convex polyhedron containing the
set-theoretic difference
of
and
.
In general, even if and
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:
OUTPUT:
This method assigns the poly-difference to self and does not return anything.
Raises a ValueError if self and and y 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 and y 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.
Assign to self the poly-hull of self and y.
For any pair of NNC polyhedra and
, the convex
polyhedral hull (or poly-hull) of is the smallest NNC
polyhedron that includes both
and
. The poly-hull
of any pair of closed polyhedra in is also closed.
INPUT:
OUTPUT:
This method assigns the poly-hull to self and does not return anything.
Raises a ValueError if self and and y 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 and y 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.
Return the relations holding between the polyhedron self and the generator or constraint arg.
INPUT:
OUTPUT:
A Poly_Gen_Relation or a Poly_Con_Relation according to the type of the input.
Raises ValueError if self and the generator/constraint arg 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 with implies() or implies(), 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 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 if new_dimensions is greater than the space dimension of self.
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.
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
Test whether self strictly contains y.
INPUT:
OUTPUT:
Boolean. Returns True if and only if self contains y and self does not equal y.
Raises a ValueError if self and y 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.
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}
Compute the cylindrification of self with respect to space dimension var.
INPUT:
OUTPUT:
This method assigns the cylindrification to self and does not return anything.
Raises a ValueError if var is not a space dimension of self.
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.
Assign to self the poly-hull of self and y.
For any pair of NNC polyhedra and
, the convex
polyhedral hull (or poly-hull) of is the smallest NNC
polyhedron that includes both
and
. The poly-hull
of any pair of closed polyhedra in is also closed.
INPUT:
OUTPUT:
This method assigns the poly-hull to self and does not return anything.
Raises a ValueError if self and and y 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 and y 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.
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 , its space
dimension is
.
INPUT:
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 and e2 are equivalent, since the two variables x and z 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
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
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
Return the dimension of the vector space enclosing self.
OUPUT:
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
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)
Constuct an equation.
INPUT:
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
Constuct an inequality.
INPUT:
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
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)
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)
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)
Constuct a strict inequality.
INPUT:
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