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