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