Mention that we use Z-polyhedra
[linpy.git] / doc / reference.rst
1
2 .. _reference:
3
4 Module Reference
5 ================
6
7
8 .. _reference_symbols:
9
10 Symbols
11 -------
12
13 *Symbols* are the basic components to build expressions and constraints.
14 They correspond to mathematical variables.
15
16 .. class:: Symbol(name)
17
18 Return a symbol with the name string given in argument.
19 Alternatively, the function :func:`symbols` allows to create several symbols at once.
20 Symbols are instances of class :class:`LinExpr` and inherit its functionalities.
21
22 >>> x = Symbol('x')
23 >>> x
24 x
25
26 Two instances of :class:`Symbol` are equal if they have the same name.
27
28 .. attribute:: name
29
30 The name of the symbol.
31
32 .. method:: asdummy()
33
34 Return a new :class:`Dummy` symbol instance with the same name.
35
36 .. method:: sortkey()
37
38 Return a sorting key for the symbol.
39 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`).
40
41 >>> sort(symbols, key=Symbol.sortkey)
42
43
44 .. function:: symbols(names)
45
46 This function returns a tuple of symbols whose names are taken from a comma or whitespace delimited string, or a sequence of strings.
47 It is useful to define several symbols at once.
48
49 >>> x, y = symbols('x y')
50 >>> x, y = symbols('x, y')
51 >>> x, y = symbols(['x', 'y'])
52
53
54 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.
55 This is achieved using ``Dummy('x')``.
56
57 .. class:: Dummy(name=None)
58
59 A variation of :class:`Symbol` in which all symbols are unique and identified by an internal count index.
60 If a name is not supplied then a string value of the count index will be used.
61 This is useful when a unique, temporary variable is needed and the name of the variable used in the expression is not important.
62
63 Unlike :class:`Symbol`, :class:`Dummy` instances with the same name are not equal:
64
65 >>> x = Symbol('x')
66 >>> x1, x2 = Dummy('x'), Dummy('x')
67 >>> x == x1
68 False
69 >>> x1 == x2
70 False
71 >>> x1 == x1
72 True
73
74
75 .. _reference_linexprs:
76
77 Linear Expressions
78 ------------------
79
80 A *linear expression* consists of a list of coefficient-variable pairs that capture the linear terms, plus a constant term.
81 Linear expressions are used to build constraints. They are temporary objects that typically have short lifespans.
82
83 Linear expressions are generally built using overloaded operators.
84 For example, if ``x`` is a :class:`Symbol`, then ``x + 1`` is an instance of :class:`LinExpr`.
85
86 .. class:: LinExpr(coefficients=None, constant=0)
87 LinExpr(string)
88
89 Return a linear expression from a dictionary or a sequence, that maps symbols to their coefficients, and a constant term.
90 The coefficients and the constant term must be rational numbers.
91
92 For example, the linear expression ``x + 2*y + 1`` can be constructed using one of the following instructions:
93
94 >>> x, y = symbols('x y')
95 >>> LinExpr({x: 1, y: 2}, 1)
96 >>> LinExpr([(x, 1), (y, 2)], 1)
97
98 However, it may be easier to use overloaded operators:
99
100 >>> x, y = symbols('x y')
101 >>> x + 2*y + 1
102
103 Alternatively, linear expressions can be constructed from a string:
104
105 >>> LinExpr('x + 2y + 1')
106
107 :class:`LinExpr` instances are hashable, and should be treated as immutable.
108
109 A linear expression with a single symbol of coefficient 1 and no constant term is automatically subclassed as a :class:`Symbol` instance.
110 A linear expression with no symbol, only a constant term, is automatically subclassed as a :class:`Rational` instance.
111
112 .. method:: coefficient(symbol)
113 __getitem__(symbol)
114
115 Return the coefficient value of the given symbol, or ``0`` if the symbol does not appear in the expression.
116
117 .. method:: coefficients()
118
119 Iterate over the pairs ``(symbol, value)`` of linear terms in the expression.
120 The constant term is ignored.
121
122 .. attribute:: constant
123
124 The constant term of the expression.
125
126 .. attribute:: symbols
127
128 The tuple of symbols present in the expression, sorted according to :meth:`Symbol.sortkey`.
129
130 .. attribute:: dimension
131
132 The dimension of the expression, i.e. the number of symbols present in it.
133
134 .. method:: isconstant()
135
136 Return ``True`` if the expression only consists of a constant term.
137 In this case, it is a :class:`Rational` instance.
138
139 .. method:: issymbol()
140
141 Return ``True`` if an expression only consists of a symbol with coefficient ``1``.
142 In this case, it is a :class:`Symbol` instance.
143
144 .. method:: values()
145
146 Iterate over the coefficient values in the expression, and the constant term.
147
148 .. method:: __add__(expr)
149
150 Return the sum of two linear expressions.
151
152 .. method:: __sub__(expr)
153
154 Return the difference between two linear expressions.
155
156 .. method:: __mul__(value)
157
158 Return the product of the linear expression by a rational.
159
160 .. method:: __truediv__(value)
161
162 Return the quotient of the linear expression by a rational.
163
164 .. method:: __eq__(expr)
165
166 Test whether two linear expressions are equal.
167 Unlike methods :meth:`LinExpr.__lt__`, :meth:`LinExpr.__le__`, :meth:`LinExpr.__ge__`, :meth:`LinExpr.__gt__`, the result is a boolean value, not a polyhedron.
168 To express that two linear expressions are equal or not equal, use functions :func:`Eq` and :func:`Ne` instead.
169
170 As explained below, it is possible to create polyhedra from linear expressions using comparison methods.
171
172 .. method:: __lt__(expr)
173 __le__(expr)
174 __ge__(expr)
175 __gt__(expr)
176
177 Create a new :class:`Polyhedron` instance whose unique constraint is the comparison between two linear expressions.
178 As an alternative, functions :func:`Lt`, :func:`Le`, :func:`Ge` and :func:`Gt` can be used.
179
180 >>> x, y = symbols('x y')
181 >>> x < y
182 x + 1 <= y
183
184 .. method:: scaleint()
185
186 Return the expression multiplied by its lowest common denominator to make all values integer.
187
188 .. method:: subs(symbol, expression)
189 subs(pairs)
190
191 Substitute the given symbol by an expression and return the resulting expression.
192 Raise :exc:`TypeError` if the resulting expression is not linear.
193
194 >>> x, y = symbols('x y')
195 >>> e = x + 2*y + 1
196 >>> e.subs(y, x - 1)
197 3*x - 1
198
199 To perform multiple substitutions at once, pass a sequence or a dictionary of ``(old, new)`` pairs to ``subs``.
200
201 >>> e.subs({x: y, y: x})
202 2*x + y + 1
203
204 .. classmethod:: fromstring(string)
205
206 Create an expression from a string.
207 Raise :exc:`SyntaxError` if the string is not properly formatted.
208
209 There are also methods to convert linear expressions to and from `SymPy <http://sympy.org>`_ expressions:
210
211 .. classmethod:: fromsympy(expr)
212
213 Create a linear expression from a :mod:`sympy` expression.
214 Raise :exc:`TypeError` is the :mod:`sympy` expression is not linear.
215
216 .. method:: tosympy()
217
218 Convert the linear expression to a sympy expression.
219
220
221 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.
222 They are implemented by the :class:`Rational` class, that inherits from both :class:`LinExpr` and :class:`fractions.Fraction` classes.
223
224 .. class:: Rational(numerator, denominator=1)
225 Rational(string)
226
227 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``.
228 If the denominator is ``0``, it raises a :exc:`ZeroDivisionError`.
229 The other version of the constructor expects a string.
230 The usual form for this instance is::
231
232 [sign] numerator ['/' denominator]
233
234 where the optional ``sign`` may be either '+' or '-' and the ``numerator`` and ``denominator`` (if present) are strings of decimal digits.
235
236 See the documentation of :class:`fractions.Fraction` for more information and examples.
237
238
239 .. _reference_polyhedra:
240
241 Polyhedra
242 ---------
243
244 A *convex polyhedron* (or simply "polyhedron") is the space defined by a system of linear equalities and inequalities.
245 This space can be unbounded.
246 A *Z-polyhedron* (simply called "polyhedron" in LinPy) is the set of integer points in a convex polyhedron.
247
248 .. class:: Polyhedron(equalities, inequalities)
249 Polyhedron(string)
250 Polyhedron(geometric object)
251
252 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``.
253 For example, the polyhedron ``0 <= x <= 2, 0 <= y <= 2`` can be constructed with:
254
255 >>> x, y = symbols('x y')
256 >>> square1 = Polyhedron([], [x, 2 - x, y, 2 - y])
257 >>> square1
258 And(0 <= x, x <= 2, 0 <= y, y <= 2)
259
260 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:
261
262 >>> x, y = symbols('x y')
263 >>> square1 = (0 <= x) & (x <= 2) & (0 <= y) & (y <= 2)
264 >>> square1 = Le(0, x, 2) & Le(0, y, 2)
265
266 It is also possible to build a polyhedron from a string.
267
268 >>> square1 = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
269
270 Finally, a polyhedron can be constructed from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.aspolyedron` method.
271 This way, it is possible to compute the polyhedral hull of a :class:`Domain` instance, i.e., the convex hull of two polyhedra:
272
273 >>> square1 = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
274 >>> square2 = Polyhedron('1 <= x <= 3, 1 <= y <= 3')
275 >>> Polyhedron(square1 | square2)
276 And(0 <= x, 0 <= y, x <= y + 2, y <= x + 2, x <= 3, y <= 3)
277
278 A polyhedron is a :class:`Domain` instance, and, therefore, inherits the functionalities of this class.
279 It is also a :class:`GeometricObject` instance.
280
281 .. attribute:: equalities
282
283 The tuple of equalities.
284 This is a list of :class:`LinExpr` instances that are equal to ``0`` in the polyhedron.
285
286 .. attribute:: inequalities
287
288 The tuple of inequalities.
289 This is a list of :class:`LinExpr` instances that are greater or equal to ``0`` in the polyhedron.
290
291 .. attribute:: constraints
292
293 The tuple of constraints, i.e., equalities and inequalities.
294 This is semantically equivalent to: ``equalities + inequalities``.
295
296 .. method:: convex_union(polyhedron[, ...])
297
298 Return the convex union of two or more polyhedra.
299
300 .. method:: asinequalities()
301
302 Express the polyhedron using inequalities, given as a list of expressions greater or equal to 0.
303
304 .. method:: widen(polyhedron)
305
306 Compute the *standard widening* of two polyhedra, à la Halbwachs.
307
308 In its current implementation, this method is slow and should not be used on large polyhedra.
309
310
311 .. data:: Empty
312
313 The empty polyhedron, whose set of constraints is not satisfiable.
314
315 .. data:: Universe
316
317 The universe polyhedron, whose set of constraints is always satisfiable, i.e. is empty.
318
319
320 .. _reference_domains:
321
322 Domains
323 -------
324
325 A *domain* is a union of polyhedra.
326 Unlike polyhedra, domains allow exact computation of union, subtraction and complementary operations.
327
328 .. class:: Domain(*polyhedra)
329 Domain(string)
330 Domain(geometric object)
331
332 Return a domain from a sequence of polyhedra.
333
334 >>> square1 = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
335 >>> square2 = Polyhedron('1 <= x <= 3, 1 <= y <= 3')
336 >>> dom = Domain(square1, square2)
337 >>> dom
338 Or(And(x <= 2, 0 <= x, y <= 2, 0 <= y), And(x <= 3, 1 <= x, y <= 3, 1 <= y))
339
340 It is also possible to build domains from polyhedra using arithmetic operators :meth:`Domain.__or__`, :meth:`Domain.__invert__` or functions :func:`Or` and :func:`Not`, using one of the following instructions:
341
342 >>> dom = square1 | square2
343 >>> dom = Or(square1, square2)
344
345 Alternatively, a domain can be built from a string:
346
347 >>> dom = Domain('0 <= x <= 2, 0 <= y <= 2; 1 <= x <= 3, 1 <= y <= 3')
348
349 Finally, a domain can be built from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.asdomain` method.
350
351 A domain is also a :class:`GeometricObject` instance.
352 A domain with a unique polyhedron is automatically subclassed as a :class:`Polyhedron` instance.
353
354 .. attribute:: polyhedra
355
356 The tuple of polyhedra present in the domain.
357
358 .. attribute:: symbols
359
360 The tuple of symbols present in the domain equations, sorted according to :meth:`Symbol.sortkey`.
361
362 .. attribute:: dimension
363
364 The dimension of the domain, i.e. the number of symbols present in it.
365
366 .. method:: isempty()
367
368 Return ``True`` if the domain is empty, that is, equal to :data:`Empty`.
369
370 .. method:: __bool__()
371
372 Return ``True`` if the domain is non-empty.
373
374 .. method:: isuniverse()
375
376 Return ``True`` if the domain is universal, that is, equal to :data:`Universe`.
377
378 .. method:: isbounded()
379
380 Return ``True`` is the domain is bounded.
381
382 .. method:: __eq__(domain)
383
384 Return ``True`` if two domains are equal.
385
386 .. method:: isdisjoint(domain)
387
388 Return ``True`` if two domains have a null intersection.
389
390 .. method:: issubset(domain)
391 __le__(domain)
392
393 Report whether another domain contains the domain.
394
395 .. method:: __lt__(domain)
396
397 Report whether another domain is contained within the domain.
398
399 .. method:: complement()
400 __invert__()
401
402 Return the complementary domain of the domain.
403
404 .. method:: make_disjoint()
405
406 Return an equivalent domain, whose polyhedra are disjoint.
407
408 .. method:: coalesce()
409
410 Simplify the representation of the domain by trying to combine pairs of polyhedra into a single polyhedron, and return the resulting domain.
411
412 .. method:: detect_equalities()
413
414 Simplify the representation of the domain by detecting implicit equalities, and return the resulting domain.
415
416 .. method:: remove_redundancies()
417
418 Remove redundant constraints in the domain, and return the resulting domain.
419
420 .. method:: project(symbols)
421
422 Project out the sequence of symbols given in arguments, and return the resulting domain.
423
424 .. method:: sample()
425
426 Return a sample of the domain, as an integer instance of :class:`Point`.
427 If the domain is empty, a :exc:`ValueError` exception is raised.
428
429 .. method:: intersection(domain[, ...])
430 __and__(domain)
431
432 Return the intersection of two or more domains as a new domain.
433 As an alternative, function :func:`And` can be used.
434
435 .. method:: union(domain[, ...])
436 __or__(domain)
437 __add__(domain)
438
439 Return the union of two or more domains as a new domain.
440 As an alternative, function :func:`Or` can be used.
441
442 .. method:: difference(domain)
443 __sub__(domain)
444
445 Return the difference between two domains as a new domain.
446
447 .. method:: lexmin()
448
449 Return the lexicographic minimum of the elements in the domain.
450
451 .. method:: lexmax()
452
453 Return the lexicographic maximum of the elements in the domain.
454
455 .. method:: vertices()
456
457 Return the vertices of the domain, as a list of rational instances of :class:`Point`.
458
459 .. method:: points()
460
461 Return the integer points of a bounded domain, as a list of integer instances of :class:`Point`.
462 If the domain is not bounded, a :exc:`ValueError` exception is raised.
463
464 .. method:: __contains__(point)
465
466 Return ``True`` if the point is contained within the domain.
467
468 .. method:: faces()
469
470 Return the list of faces of a bounded domain.
471 Each face is represented by a list of vertices, in the form of rational instances of :class:`Point`.
472 If the domain is not bounded, a :exc:`ValueError` exception is raised.
473
474 .. method:: plot(plot=None, **options)
475
476 Plot a 2D or 3D domain using `matplotlib <http://matplotlib.org/>`_.
477 Draw it to the current *plot* object if present, otherwise create a new one.
478 *options* are keyword arguments passed to the matplotlib drawing functions, they can be used to set the drawing color for example.
479 Raise :exc:`ValueError` is the domain is not 2D or 3D.
480
481 .. method:: subs(symbol, expression)
482 subs(pairs)
483
484 Substitute the given symbol by an expression in the domain constraints.
485 To perform multiple substitutions at once, pass a sequence or a dictionary of ``(old, new)`` pairs to ``subs``.
486 The syntax of this function is similar to :func:`LinExpr.subs`.
487
488 .. classmethod:: fromstring(string)
489
490 Create a domain from a string.
491 Raise :exc:`SyntaxError` if the string is not properly formatted.
492
493 There are also methods to convert a domain to and from `SymPy <http://sympy.org>`_ expressions:
494
495 .. classmethod:: fromsympy(expr)
496
497 Create a domain from a sympy expression.
498
499 .. method:: tosympy()
500
501 Convert the domain to a sympy expression.
502
503
504 .. _reference_operators:
505
506 Comparison and Logic Operators
507 ------------------------------
508
509 The following functions create :class:`Polyhedron` or :class:`Domain` instances using the comparisons of two or more :class:`LinExpr` instances:
510
511 .. function:: Lt(expr1, expr2[, expr3, ...])
512
513 Create the polyhedron with constraints ``expr1 < expr2 < expr3 ...``.
514
515 .. function:: Le(expr1, expr2[, expr3, ...])
516
517 Create the polyhedron with constraints ``expr1 <= expr2 <= expr3 ...``.
518
519 .. function:: Eq(expr1, expr2[, expr3, ...])
520
521 Create the polyhedron with constraints ``expr1 == expr2 == expr3 ...``.
522
523 .. function:: Ne(expr1, expr2[, expr3, ...])
524
525 Create the domain such that ``expr1 != expr2 != expr3 ...``.
526 The result is a :class:`Domain` object, not a :class:`Polyhedron`.
527
528 .. function:: Ge(expr1, expr2[, expr3, ...])
529
530 Create the polyhedron with constraints ``expr1 >= expr2 >= expr3 ...``.
531
532 .. function:: Gt(expr1, expr2[, expr3, ...])
533
534 Create the polyhedron with constraints ``expr1 > expr2 > expr3 ...``.
535
536 The following functions combine :class:`Polyhedron` or :class:`Domain` instances using logic operators:
537
538 .. function:: And(domain1, domain2[, ...])
539
540 Create the intersection domain of the domains given in arguments.
541
542 .. function:: Or(domain1, domain2[, ...])
543
544 Create the union domain of the domains given in arguments.
545
546 .. function:: Not(domain)
547
548 Create the complementary domain of the domain given in argument.
549
550
551 .. _reference_geometry:
552
553 Geometric Objects
554 -----------------
555
556 .. class:: GeometricObject
557
558 :class:`GeometricObject` is an abstract class to represent objects with a geometric representation in space.
559 Subclasses of :class:`GeometricObject` are :class:`Polyhedron`, :class:`Domain` and :class:`Point`.
560 The following elements must be provided:
561
562 .. attribute:: symbols
563
564 The tuple of symbols present in the object expression, sorted according to :class:`Symbol.sortkey()`.
565
566 .. attribute:: dimension
567
568 The dimension of the object, i.e. the number of symbols present in it.
569
570 .. method:: aspolyedron()
571
572 Return a :class:`Polyhedron` object that approximates the geometric object.
573
574 .. method:: asdomain()
575
576 Return a :class:`Domain` object that approximates the geometric object.
577
578 .. class:: Point(coordinates)
579
580 Create a point from a dictionary or a sequence that maps the symbols to their coordinates.
581 Coordinates must be rational numbers.
582
583 For example, the point ``(x: 1, y: 2)`` can be constructed using one of the following instructions:
584
585 >>> x, y = symbols('x y')
586 >>> p = Point({x: 1, y: 2})
587 >>> p = Point([(x, 1), (y, 2)])
588
589 :class:`Point` instances are hashable and should be treated as immutable.
590
591 A point is a :class:`GeometricObject` instance.
592
593 .. attribute:: symbols
594
595 The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.
596
597 .. attribute:: dimension
598
599 The dimension of the point, i.e. the number of symbols present in it.
600
601 .. method:: coordinate(symbol)
602 __getitem__(symbol)
603
604 Return the coordinate value of the given symbol.
605 Raise :exc:`KeyError` if the symbol is not involved in the point.
606
607 .. method:: coordinates()
608
609 Iterate over the pairs ``(symbol, value)`` of coordinates in the point.
610
611 .. method:: values()
612
613 Iterate over the coordinate values in the point.
614
615 .. method:: isorigin()
616
617 Return ``True`` if all coordinates are ``0``.
618
619 .. method:: __bool__()
620
621 Return ``True`` if not all coordinates are ``0``.
622
623 .. method:: __add__(vector)
624
625 Translate the point by a :class:`Vector` object and return the resulting point.
626
627 .. method:: __sub__(point)
628 __sub__(vector)
629
630 The first version substracts a point from another and returns the resulting vector.
631 The second version translates the point by the opposite vector of *vector* and returns the resulting point.
632
633 .. method:: __eq__(point)
634
635 Test whether two points are equal.
636
637
638 .. class:: Vector(coordinates)
639 Vector(point1, point2)
640
641 The first version creates a vector from a dictionary or a sequence that maps the symbols to their coordinates, similarly to :meth:`Point`.
642 The second version creates a vector between two points.
643
644 :class:`Vector` instances are hashable and should be treated as immutable.
645
646 .. attribute:: symbols
647
648 The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.
649
650 .. attribute:: dimension
651
652 The dimension of the point, i.e. the number of symbols present in it.
653
654 .. method:: coordinate(symbol)
655 __getitem__(symbol)
656
657 Return the coordinate value of the given symbol.
658 Raise :exc:`KeyError` if the symbol is not involved in the point.
659
660 .. method:: coordinates()
661
662 Iterate over the pairs ``(symbol, value)`` of coordinates in the point.
663
664 .. method:: values()
665
666 Iterate over the coordinate values in the point.
667
668 .. method:: isnull()
669
670 Return ``True`` if all coordinates are ``0``.
671
672 .. method:: __bool__()
673
674 Return ``True`` if not all coordinates are ``0``.
675
676 .. method:: __add__(point)
677 __add__(vector)
678
679 The first version translates the point *point* to the vector and returns the resulting point.
680 The second version adds vector *vector* to the vector and returns the resulting vector.
681
682 .. method:: __sub__(point)
683 __sub__(vector)
684
685 The first version substracts a point from a vector and returns the resulting point.
686 The second version returns the difference vector between two vectors.
687
688 .. method:: __neg__()
689
690 Return the opposite vector.
691
692 .. method:: __mul__(value)
693
694 Multiply the vector by a scalar value and return the resulting vector.
695
696 .. method:: __truediv__(value)
697
698 Divide the vector by a scalar value and return the resulting vector.
699
700 .. method:: __eq__(vector)
701
702 Test whether two vectors are equal.
703
704 .. method:: angle(vector)
705
706 Retrieve the angle required to rotate the vector into the vector passed in argument.
707 The result is an angle in radians, ranging between ``-pi`` and ``pi``.
708
709 .. method:: cross(vector)
710
711 Compute the cross product of two 3D vectors.
712 If either one of the vectors is not three-dimensional, a :exc:`ValueError` exception is raised.
713
714 .. method:: dot(vector)
715
716 Compute the dot product of two vectors.
717
718 .. method:: norm()
719
720 Return the norm of the vector.
721
722 .. method:: norm2()
723
724 Return the squared norm of the vector.
725
726 .. method:: asunit()
727
728 Return the normalized vector, i.e. the vector of same direction but with norm 1.