8 *Symbols* are the basic components to build expressions and constraints.
9 They correspond to mathematical variables.
11 .. class:: Symbol(name)
13 Return a symbol with the name string given in argument.
14 Alternatively, the function :func:`symbols` allows to create several symbols at once.
15 Symbols are instances of class :class:`LinExpr` and inherit its functionalities.
21 Two instances of :class:`Symbol` are equal if they have the same name.
25 The name of the symbol.
29 Return a new :class:`Dummy` symbol instance with the same name.
33 Return a sorting key for the symbol.
34 It is useful to sort a list of symbols in a consistent order, as comparison functions are overridden (see the documentation of class :class:`LinExpr`).
36 >>> sort(symbols, key=Symbol.sortkey)
39 .. function:: symbols(names)
41 This function returns a tuple of symbols whose names are taken from a comma or whitespace delimited string, or a sequence of strings.
42 It is useful to define several symbols at once.
44 >>> x, y = symbols('x y')
45 >>> x, y = symbols('x, y')
46 >>> x, y = symbols(['x', 'y'])
49 Sometimes you need to have a unique symbol. For example, you might need a temporary one in some calculation, which is going to be substituted for something else at the end anyway.
50 This is achieved using ``Dummy('x')``.
52 .. class:: Dummy(name=None)
54 A variation of :class:`Symbol` in which all symbols are unique and identified by an internal count index.
55 If a name is not supplied then a string value of the count index will be used.
56 This is useful when a unique, temporary variable is needed and the name of the variable used in the expression is not important.
58 Unlike :class:`Symbol`, :class:`Dummy` instances with the same name are not equal:
61 >>> x1, x2 = Dummy('x'), Dummy('x')
73 A *linear expression* consists of a list of coefficient-variable pairs that capture the linear terms, plus a constant term.
74 Linear expressions are used to build constraints. They are temporary objects that typically have short lifespans.
76 Linear expressions are generally built using overloaded operators.
77 For example, if ``x`` is a :class:`Symbol`, then ``x + 1`` is an instance of :class:`LinExpr`.
79 .. class:: LinExpr(coefficients=None, constant=0)
82 Return a linear expression from a dictionary or a sequence, that maps symbols to their coefficients, and a constant term.
83 The coefficients and the constant term must be rational numbers.
85 For example, the linear expression ``x + 2y + 1`` can be constructed using one of the following instructions:
87 >>> x, y = symbols('x y')
88 >>> LinExpr({x: 1, y: 2}, 1)
89 >>> LinExpr([(x, 1), (y, 2)], 1)
91 However, it may be easier to use overloaded operators:
93 >>> x, y = symbols('x y')
96 Alternatively, linear expressions can be constructed from a string:
98 >>> LinExpr('x + 2*y + 1')
100 :class:`LinExpr` instances are hashable, and should be treated as immutable.
102 A linear expression with a single symbol of coefficient 1 and no constant term is automatically subclassed as a :class:`Symbol` instance.
103 A linear expression with no symbol, only a constant term, is automatically subclassed as a :class:`Rational` instance.
105 .. method:: coefficient(symbol)
108 Return the coefficient value of the given symbol, or ``0`` if the symbol does not appear in the expression.
110 .. method:: coefficients()
112 Iterate over the pairs ``(symbol, value)`` of linear terms in the expression.
113 The constant term is ignored.
115 .. attribute:: constant
117 The constant term of the expression.
119 .. attribute:: symbols
121 The tuple of symbols present in the expression, sorted according to :meth:`Symbol.sortkey`.
123 .. attribute:: dimension
125 The dimension of the expression, i.e. the number of symbols present in it.
127 .. method:: isconstant()
129 Return ``True`` if the expression only consists of a constant term.
130 In this case, it is a :class:`Rational` instance.
132 .. method:: issymbol()
134 Return ``True`` if an expression only consists of a symbol with coefficient ``1``.
135 In this case, it is a :class:`Symbol` instance.
139 Iterate over the coefficient values in the expression, and the constant term.
141 .. method:: __add__(expr)
143 Return the sum of two linear expressions.
145 .. method:: __sub__(expr)
147 Return the difference between two linear expressions.
149 .. method:: __mul__(value)
151 Return the product of the linear expression as a rational.
153 .. method:: __truediv__(value)
155 Return the quotient of the linear expression as a rational.
157 .. method:: __eq__(expr)
159 Test whether two linear expressions are equal.
161 As explained below, it is possible to create polyhedra from linear expressions using comparison methods.
163 .. method:: __lt__(expr)
168 Create a new :class:`Polyhedron` instance whose unique constraint is the comparison between two linear expressions.
169 As an alternative, functions :func:`Lt`, :func:`Le`, :func:`Ge` and :func:`Gt` can be used.
171 >>> x, y = symbols('x y')
176 .. method:: scaleint()
178 Return the expression multiplied by its lowest common denominator to make all values integer.
180 .. method:: subs(symbol, expression)
183 Substitute the given symbol by an expression and return the resulting expression.
184 Raise :exc:`TypeError` if the resulting expression is not linear.
186 >>> x, y = symbols('x y')
191 To perform multiple substitutions at once, pass a sequence or a dictionary of ``(old, new)`` pairs to ``subs``.
193 >>> e.subs({x: y, y: x})
196 .. classmethod:: fromstring(string)
198 Create an expression from a string.
199 Raise :exc:`SyntaxError` if the string is not properly formatted.
201 There are also methods to convert linear expressions to and from `SymPy <http://sympy.org>`_ expressions:
203 .. classmethod:: fromsympy(expr)
205 Create a linear expression from a :mod:`sympy` expression.
206 Raise :exc:`ValueError` is the :mod:`sympy` expression is not linear.
208 .. method:: tosympy()
210 Convert the linear expression to a sympy expression.
213 Apart from :mod:`Symbol`, a particular case of linear expressions are rational values, i.e. linear expressions consisting only of a constant term, with no symbol.
214 They are implemented by the :class:`Rational` class, that inherits from both :class:`LinExpr` and :class:`fractions.Fraction` classes.
216 .. class:: Rational(numerator, denominator=1)
219 The first version requires that the *numerator* and *denominator* are instances of :class:`numbers.Rational` and returns a new :class:`Rational` instance with the value ``numerator/denominator``.
220 If the denominator is ``0``, it raises a :exc:`ZeroDivisionError`.
221 The other version of the constructor expects a string.
222 The usual form for this instance is::
224 [sign] numerator ['/' denominator]
226 where the optional ``sign`` may be either '+' or '-' and the ``numerator`` and ``denominator`` (if present) are strings of decimal digits.
228 See the documentation of :class:`fractions.Fraction` for more information and examples.
233 A *convex polyhedron* (or simply polyhedron) is the space defined by a system of linear equalities and inequalities.
234 This space can be unbounded.
236 .. class:: Polyhedron(equalities, inequalities)
238 Polyhedron(geometric object)
240 Return a polyhedron from two sequences of linear expressions: *equalities* is a list of expressions equal to ``0``, and *inequalities* is a list of expressions greater or equal to ``0``.
241 For example, the polyhedron ``0 <= x <= 2, 0 <= y <= 2`` can be constructed with:
243 >>> x, y = symbols('x y')
244 >>> square = Polyhedron([], [x, 2 - x, y, 2 - y])
246 It may be easier to use comparison operators :meth:`LinExpr.__lt__`, :meth:`LinExpr.__le__`, :meth:`LinExpr.__ge__`, :meth:`LinExpr.__gt__`, or functions :func:`Lt`, :func:`Le`, :func:`Eq`, :func:`Ge` and :func:`Gt`, using one of the following instructions:
248 >>> x, y = symbols('x y')
249 >>> square = (0 <= x) & (x <= 2) & (0 <= y) & (y <= 2)
250 >>> square = Le(0, x, 2) & Le(0, y, 2)
252 It is also possible to build a polyhedron from a string.
254 >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
256 Finally, a polyhedron can be constructed from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.aspolyedron` method.
257 This way, it is possible to compute the polyhedral hull of a :class:`Domain` instance, i.e., the convex hull of two polyhedra:
259 >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
260 >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
261 >>> Polyhedron(square | square2)
263 A polyhedron is a :class:`Domain` instance, and, therefore, inherits the functionalities of this class.
264 It is also a :class:`GeometricObject` instance.
266 .. attribute:: equalities
268 The tuple of equalities.
269 This is a list of :class:`LinExpr` instances that are equal to ``0`` in the polyhedron.
271 .. attribute:: inequalities
273 The tuple of inequalities.
274 This is a list of :class:`LinExpr` instances that are greater or equal to ``0`` in the polyhedron.
276 .. attribute:: constraints
278 The tuple of constraints, i.e., equalities and inequalities.
279 This is semantically equivalent to: ``equalities + inequalities``.
281 .. method:: widen(polyhedron)
283 Compute the standard widening of two polyhedra, à la Halbwachs.
288 The empty polyhedron, whose set of constraints is not satisfiable.
292 The universe polyhedron, whose set of constraints is always satisfiable, i.e. is empty.
297 A *domain* is a union of polyhedra.
298 Unlike polyhedra, domains allow exact computation of union and complementary operations.
300 .. class:: Domain(*polyhedra)
302 Domain(geometric object)
304 Return a domain from a sequence of polyhedra.
306 >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
307 >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
308 >>> dom = Domain([square, square2])
310 It is also possible to build domains from polyhedra using arithmetic operators :meth:`Domain.__and__`, :meth:`Domain.__or__` or functions :func:`And` and :func:`Or`, using one of the following instructions:
312 >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
313 >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
314 >>> dom = square | square2
315 >>> dom = Or(square, square2)
317 Alternatively, a domain can be built from a string:
319 >>> dom = Domain('0 <= x <= 2, 0 <= y <= 2; 2 <= x <= 4, 2 <= y <= 4')
321 Finally, a domain can be built from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.asdomain` method.
323 A domain is also a :class:`GeometricObject` instance.
324 A domain with a unique polyhedron is automatically subclassed as a :class:`Polyhedron` instance.
326 .. attribute:: polyhedra
328 The tuple of polyhedra present in the domain.
330 .. attribute:: symbols
332 The tuple of symbols present in the domain expression, sorted according to :meth:`Symbol.sortkey`.
334 .. attribute:: dimension
336 The dimension of the domain, i.e. the number of symbols present in it.
338 .. method:: isempty()
340 Return ``True`` if the domain is empty, that is, equal to :data:`Empty`.
342 .. method:: __bool__()
344 Return ``True`` if the domain is non-empty.
346 .. method:: isuniverse()
348 Return ``True`` if the domain is universal, that is, equal to :data:`Universe`.
350 .. method:: isbounded()
352 Return ``True`` is the domain is bounded.
354 .. method:: __eq__(domain)
356 Return ``True`` if two domains are equal.
358 .. method:: isdisjoint(domain)
360 Return ``True`` if two domains have a null intersection.
362 .. method:: issubset(domain)
365 Report whether another domain contains the domain.
367 .. method:: __lt__(domain)
369 Report whether another domain is contained within the domain.
371 .. method:: complement()
374 Return the complementary domain of the domain.
376 .. method:: make_disjoint()
378 Return an equivalent domain, whose polyhedra are disjoint.
380 .. method:: coalesce()
382 Simplify the representation of the domain by trying to combine pairs of polyhedra into a single polyhedron, and return the resulting domain.
384 .. method:: detect_equalities()
386 Simplify the representation of the domain by detecting implicit equalities, and return the resulting domain.
388 .. method:: remove_redundancies()
390 Remove redundant constraints in the domain, and return the resulting domain.
392 .. method:: project(symbols)
394 Project out the sequence of symbols given in arguments, and return the resulting domain.
398 Return a sample of the domain, as an integer instance of :class:`Point`.
399 If the domain is empty, a :exc:`ValueError` exception is raised.
401 .. method:: intersection(domain[, ...])
404 Return the intersection of two or more domains as a new domain.
405 As an alternative, function :func:`And` can be used.
407 .. method:: union(domain[, ...])
411 Return the union of two or more domains as a new domain.
412 As an alternative, function :func:`Or` can be used.
414 .. method:: difference(domain)
417 Return the difference between two domains as a new domain.
421 Return the lexicographic minimum of the elements in the domain.
425 Return the lexicographic maximum of the elements in the domain.
427 .. method:: vertices()
429 Return the vertices of the domain, as a list of rational instances of :class:`Point`.
433 Return the integer points of a bounded domain, as a list of integer instances of :class:`Point`.
434 If the domain is not bounded, a :exc:`ValueError` exception is raised.
436 .. method:: __contains__(point)
438 Return ``True`` if the :class:`Point` is contained within the domain.
442 Return the list of faces of a bounded domain.
443 Each face is represented by a list of vertices, in the form of rational instances of :class:`Point`.
444 If the domain is not bounded, a :exc:`ValueError` exception is raised.
446 .. method:: plot(plot=None, **options)
448 Plot a 2D or 3D domain using `matplotlib <http://matplotlib.org/>`_.
449 Draw it to the current *plot* object if present, otherwise create a new one.
450 *options* are keyword arguments passed to the matplotlib drawing functions, they can be used to set the drawing color for example.
451 Raise :exc:`ValueError` is the domain is not 2D or 3D.
453 .. method:: subs(symbol, expression)
456 Substitute the given symbol by an expression in the domain constraints.
457 To perform multiple substitutions at once, pass a sequence or a dictionary of ``(old, new)`` pairs to ``subs``.
458 The syntax of this function is similar to :func:`LinExpr.subs`.
460 .. classmethod:: fromstring(string)
462 Create a domain from a string.
463 Raise :exc:`SyntaxError` if the string is not properly formatted.
465 There are also methods to convert a domain to and from `SymPy <http://sympy.org>`_ expressions:
467 .. classmethod:: fromsympy(expr)
469 Create a domain from a sympy expression.
471 .. method:: tosympy()
473 Convert the domain to a sympy expression.
476 Comparison and Logic Operators
477 ------------------------------
479 The following functions create :class:`Polyhedron` or :class:`Domain` instances by comparison of :class:`LinExpr` instances:
481 .. function:: Lt(expr1, expr2[, expr3, ...])
483 Create the polyhedron with constraints ``expr1 < expr2 < expr3 ...``.
485 .. function:: Le(expr1, expr2[, expr3, ...])
487 Create the polyhedron with constraints ``expr1 <= expr2 <= expr3 ...``.
489 .. function:: Eq(expr1, expr2[, expr3, ...])
491 Create the polyhedron with constraints ``expr1 == expr2 == expr3 ...``.
493 .. function:: Ne(expr1, expr2[, expr3, ...])
495 Create the domain such that ``expr1 != expr2 != expr3 ...``.
496 The result is a :class:`Domain`, not a :class:`Polyhedron`.
498 .. function:: Ge(expr1, expr2[, expr3, ...])
500 Create the polyhedron with constraints ``expr1 >= expr2 >= expr3 ...``.
502 .. function:: Gt(expr1, expr2[, expr3, ...])
504 Create the polyhedron with constraints ``expr1 > expr2 > expr3 ...``.
506 The following functions combine :class:`Polyhedron` or :class:`Domain` instances using logic operators:
508 .. function:: Or(domain1, domain2[, ...])
510 Create the union domain of the domains given in arguments.
512 .. function:: And(domain1, domain2[, ...])
514 Create the intersection domain of the domains given in arguments.
516 .. function:: Not(domain)
518 Create the complementary domain of the domain given in argument.
524 .. class:: GeometricObject
526 :class:`GeometricObject` is an abstract class to represent objects with a geometric representation in space.
527 Subclasses of :class:`GeometricObject` are :class:`Polyhedron`, :class:`Domain` and :class:`Point`.
528 The following elements must be provided:
530 .. attribute:: symbols
532 The tuple of symbols present in the object expression, sorted according to :class:`Symbol.sortkey()`.
534 .. attribute:: dimension
536 The dimension of the object, i.e. the number of symbols present in it.
538 .. method:: aspolyedron()
540 Return a :class:`Polyhedron` object that approximates the geometric object.
542 .. method:: asdomain()
544 Return a :class:`Domain` object that approximates the geometric object.
546 .. class:: Point(coordinates)
548 Create a point from a dictionary or a sequence that maps the symbols to their coordinates.
549 Coordinates must be rational numbers.
551 For example, the point ``(x: 1, y: 2)`` can be constructed using one of the following instructions:
553 >>> x, y = symbols('x y')
554 >>> p = Point({x: 1, y: 2})
555 >>> p = Point([(x, 1), (y, 2)])
557 :class:`Point` instances are hashable and should be treated as immutable.
559 A point is a :class:`GeometricObject` instance.
561 .. attribute:: symbols
563 The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.
565 .. attribute:: dimension
567 The dimension of the point, i.e. the number of symbols present in it.
569 .. method:: coordinate(symbol)
572 Return the coordinate value of the given symbol.
573 Raise :exc:`KeyError` if the symbol is not involved in the point.
575 .. method:: coordinates()
577 Iterate over the pairs ``(symbol, value)`` of coordinates in the point.
581 Iterate over the coordinate values in the point.
583 .. method:: isorigin()
585 Return ``True`` if all coordinates are ``0``.
587 .. method:: __bool__()
589 Return ``True`` if not all coordinates are ``0``.
591 .. method:: __add__(vector)
593 Translate the point by a :class:`Vector` instance and return the resulting point.
595 .. method:: __sub__(point)
598 The first version substracts a point from another and returns the resulting vector.
599 The second version translates the point by the opposite vector of *vector* and returns the resulting point.
601 .. method:: __eq__(point)
603 Test whether two points are equal.
606 .. class:: Vector(coordinates)
608 Create a point from a dictionary or a sequence that maps the symbols to their coordinates, similar to :meth:`Point`.
609 Coordinates must be rational numbers.
611 :class:`Vector` instances are hashable and should be treated as immutable.
613 .. attribute:: symbols
615 The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.
617 .. attribute:: dimension
619 The dimension of the point, i.e. the number of symbols present in it.
621 .. method:: coordinate(symbol)
624 Return the coordinate value of the given symbol.
625 Raise :exc:`KeyError` if the symbol is not involved in the point.
627 .. method:: coordinates()
629 Iterate over the pairs ``(symbol, value)`` of coordinates in the point.
633 Iterate over the coordinate values in the point.
637 Return ``True`` if all coordinates are ``0``.
639 .. method:: __bool__()
641 Return ``True`` if not all coordinates are ``0``.
643 .. method:: __add__(point)
646 The first version translates the point *point* to the vector and returns the resulting point.
647 The second version adds vector *vector* to the vector and returns the resulting vector.
649 .. method:: __sub__(point)
652 The first version substracts a point from a vector and returns the resulting point.
653 The second version returns the difference vector between two vectors.
655 .. method:: __neg__()
657 Return the opposite vector.
659 .. method:: angle(vector)
661 Retrieve the angle required to rotate the vector into the vector passed in argument.
662 The result is an angle in radians, ranging between ``-pi`` and ``pi``.
664 .. method:: cross(vector)
666 Compute the cross product of two 3D vectors.
667 If either one of the vectors is not tridimensional, a :exc:`ValueError` exception is raised.
669 .. method:: dot(vector)
671 Compute the dot product of two vectors.
673 .. method:: __eq__(vector)
675 Test whether two vectors are equal.
677 .. method:: __mul__(value)
679 Multiply the vector by a scalar value and return the resulting vector.
681 .. method:: __truediv__(value)
683 Divide the vector by a scalar value and return the resulting vector.
687 Return the norm of the vector.
691 Return the square norm of the vector.
695 Return the normalized vector, i.e. the vector of same direction but with norm 1.