e6f291d461f94e1c6f3bc9a58238c5a9561ea793
[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
168 As explained below, it is possible to create polyhedra from linear expressions using comparison methods.
169
170 .. method:: __lt__(expr)
171 __le__(expr)
172 __ge__(expr)
173 __gt__(expr)
174
175 Create a new :class:`Polyhedron` instance whose unique constraint is the comparison between two linear expressions.
176 As an alternative, functions :func:`Lt`, :func:`Le`, :func:`Ge` and :func:`Gt` can be used.
177
178 >>> x, y = symbols('x y')
179 >>> x < y
180 x + 1 <= y
181
182 .. method:: scaleint()
183
184 Return the expression multiplied by its lowest common denominator to make all values integer.
185
186 .. method:: subs(symbol, expression)
187 subs(pairs)
188
189 Substitute the given symbol by an expression and return the resulting expression.
190 Raise :exc:`TypeError` if the resulting expression is not linear.
191
192 >>> x, y = symbols('x y')
193 >>> e = x + 2*y + 1
194 >>> e.subs(y, x - 1)
195 3*x - 1
196
197 To perform multiple substitutions at once, pass a sequence or a dictionary of ``(old, new)`` pairs to ``subs``.
198
199 >>> e.subs({x: y, y: x})
200 2*x + y + 1
201
202 .. classmethod:: fromstring(string)
203
204 Create an expression from a string.
205 Raise :exc:`SyntaxError` if the string is not properly formatted.
206
207 There are also methods to convert linear expressions to and from `SymPy <http://sympy.org>`_ expressions:
208
209 .. classmethod:: fromsympy(expr)
210
211 Create a linear expression from a :mod:`sympy` expression.
212 Raise :exc:`TypeError` is the :mod:`sympy` expression is not linear.
213
214 .. method:: tosympy()
215
216 Convert the linear expression to a sympy expression.
217
218
219 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.
220 They are implemented by the :class:`Rational` class, that inherits from both :class:`LinExpr` and :class:`fractions.Fraction` classes.
221
222 .. class:: Rational(numerator, denominator=1)
223 Rational(string)
224
225 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``.
226 If the denominator is ``0``, it raises a :exc:`ZeroDivisionError`.
227 The other version of the constructor expects a string.
228 The usual form for this instance is::
229
230 [sign] numerator ['/' denominator]
231
232 where the optional ``sign`` may be either '+' or '-' and the ``numerator`` and ``denominator`` (if present) are strings of decimal digits.
233
234 See the documentation of :class:`fractions.Fraction` for more information and examples.
235
236
237 .. _reference_polyhedra:
238
239 Polyhedra
240 ---------
241
242 A *convex polyhedron* (or simply "polyhedron") is the space defined by a system of linear equalities and inequalities.
243 This space can be unbounded.
244
245 .. class:: Polyhedron(equalities, inequalities)
246 Polyhedron(string)
247 Polyhedron(geometric object)
248
249 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``.
250 For example, the polyhedron ``0 <= x <= 2, 0 <= y <= 2`` can be constructed with:
251
252 >>> x, y = symbols('x y')
253 >>> square = Polyhedron([], [x, 2 - x, y, 2 - y])
254 >>> square
255 And(0 <= x, x <= 2, 0 <= y, y <= 2)
256
257 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:
258
259 >>> x, y = symbols('x y')
260 >>> square = (0 <= x) & (x <= 2) & (0 <= y) & (y <= 2)
261 >>> square = Le(0, x, 2) & Le(0, y, 2)
262
263 It is also possible to build a polyhedron from a string.
264
265 >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
266
267 Finally, a polyhedron can be constructed from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.aspolyedron` method.
268 This way, it is possible to compute the polyhedral hull of a :class:`Domain` instance, i.e., the convex hull of two polyhedra:
269
270 >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
271 >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
272 >>> Polyhedron(square | square2)
273 And(x <= 4, 0 <= x, y <= 4, 0 <= y, x <= y + 2, y <= x + 2)
274
275 A polyhedron is a :class:`Domain` instance, and, therefore, inherits the functionalities of this class.
276 It is also a :class:`GeometricObject` instance.
277
278 .. attribute:: equalities
279
280 The tuple of equalities.
281 This is a list of :class:`LinExpr` instances that are equal to ``0`` in the polyhedron.
282
283 .. attribute:: inequalities
284
285 The tuple of inequalities.
286 This is a list of :class:`LinExpr` instances that are greater or equal to ``0`` in the polyhedron.
287
288 .. attribute:: constraints
289
290 The tuple of constraints, i.e., equalities and inequalities.
291 This is semantically equivalent to: ``equalities + inequalities``.
292
293 .. method:: convex_union(polyhedron[, ...])
294
295 Return the convex union of two or more polyhedra.
296
297 .. method:: asinequalities()
298
299 Express the polyhedron using inequalities, given as a list of expressions greater or equal to 0.
300
301 .. method:: widen(polyhedron)
302
303 Compute the *standard widening* of two polyhedra, à la Halbwachs.
304
305 In its current implementation, this method is slow and should not be used on large polyhedra.
306
307
308 .. data:: Empty
309
310 The empty polyhedron, whose set of constraints is not satisfiable.
311
312 .. data:: Universe
313
314 The universe polyhedron, whose set of constraints is always satisfiable, i.e. is empty.
315
316
317 .. _reference_domains:
318
319 Domains
320 -------
321
322 A *domain* is a union of polyhedra.
323 Unlike polyhedra, domains allow exact computation of union, subtraction and complementary operations.
324
325 .. class:: Domain(*polyhedra)
326 Domain(string)
327 Domain(geometric object)
328
329 Return a domain from a sequence of polyhedra.
330
331 >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
332 >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
333 >>> dom = Domain(square, square2)
334 >>> dom
335 Or(And(x <= 2, 0 <= x, y <= 2, 0 <= y), And(x <= 4, 2 <= x, y <= 4, 2 <= y))
336
337 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:
338
339 >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
340 >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
341 >>> dom = square | square2
342 >>> dom = Or(square, square2)
343
344 Alternatively, a domain can be built from a string:
345
346 >>> dom = Domain('0 <= x <= 2, 0 <= y <= 2; 2 <= x <= 4, 2 <= y <= 4')
347
348 Finally, a domain can be built from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.asdomain` method.
349
350 A domain is also a :class:`GeometricObject` instance.
351 A domain with a unique polyhedron is automatically subclassed as a :class:`Polyhedron` instance.
352
353 .. attribute:: polyhedra
354
355 The tuple of polyhedra present in the domain.
356
357 .. attribute:: symbols
358
359 The tuple of symbols present in the domain equations, sorted according to :meth:`Symbol.sortkey`.
360
361 .. attribute:: dimension
362
363 The dimension of the domain, i.e. the number of symbols present in it.
364
365 .. method:: isempty()
366
367 Return ``True`` if the domain is empty, that is, equal to :data:`Empty`.
368
369 .. method:: __bool__()
370
371 Return ``True`` if the domain is non-empty.
372
373 .. method:: isuniverse()
374
375 Return ``True`` if the domain is universal, that is, equal to :data:`Universe`.
376
377 .. method:: isbounded()
378
379 Return ``True`` is the domain is bounded.
380
381 .. method:: __eq__(domain)
382
383 Return ``True`` if two domains are equal.
384
385 .. method:: isdisjoint(domain)
386
387 Return ``True`` if two domains have a null intersection.
388
389 .. method:: issubset(domain)
390 __le__(domain)
391
392 Report whether another domain contains the domain.
393
394 .. method:: __lt__(domain)
395
396 Report whether another domain is contained within the domain.
397
398 .. method:: complement()
399 __invert__()
400
401 Return the complementary domain of the domain.
402
403 .. method:: make_disjoint()
404
405 Return an equivalent domain, whose polyhedra are disjoint.
406
407 .. method:: coalesce()
408
409 Simplify the representation of the domain by trying to combine pairs of polyhedra into a single polyhedron, and return the resulting domain.
410
411 .. method:: detect_equalities()
412
413 Simplify the representation of the domain by detecting implicit equalities, and return the resulting domain.
414
415 .. method:: remove_redundancies()
416
417 Remove redundant constraints in the domain, and return the resulting domain.
418
419 .. method:: project(symbols)
420
421 Project out the sequence of symbols given in arguments, and return the resulting domain.
422
423 .. method:: sample()
424
425 Return a sample of the domain, as an integer instance of :class:`Point`.
426 If the domain is empty, a :exc:`ValueError` exception is raised.
427
428 .. method:: intersection(domain[, ...])
429 __and__(domain)
430
431 Return the intersection of two or more domains as a new domain.
432 As an alternative, function :func:`And` can be used.
433
434 .. method:: union(domain[, ...])
435 __or__(domain)
436 __add__(domain)
437
438 Return the union of two or more domains as a new domain.
439 As an alternative, function :func:`Or` can be used.
440
441 .. method:: difference(domain)
442 __sub__(domain)
443
444 Return the difference between two domains as a new domain.
445
446 .. method:: lexmin()
447
448 Return the lexicographic minimum of the elements in the domain.
449
450 .. method:: lexmax()
451
452 Return the lexicographic maximum of the elements in the domain.
453
454 .. method:: vertices()
455
456 Return the vertices of the domain, as a list of rational instances of :class:`Point`.
457
458 .. method:: points()
459
460 Return the integer points of a bounded domain, as a list of integer instances of :class:`Point`.
461 If the domain is not bounded, a :exc:`ValueError` exception is raised.
462
463 .. method:: __contains__(point)
464
465 Return ``True`` if the point is contained within the domain.
466
467 .. method:: faces()
468
469 Return the list of faces of a bounded domain.
470 Each face is represented by a list of vertices, in the form of rational instances of :class:`Point`.
471 If the domain is not bounded, a :exc:`ValueError` exception is raised.
472
473 .. method:: plot(plot=None, **options)
474
475 Plot a 2D or 3D domain using `matplotlib <http://matplotlib.org/>`_.
476 Draw it to the current *plot* object if present, otherwise create a new one.
477 *options* are keyword arguments passed to the matplotlib drawing functions, they can be used to set the drawing color for example.
478 Raise :exc:`ValueError` is the domain is not 2D or 3D.
479
480 .. method:: subs(symbol, expression)
481 subs(pairs)
482
483 Substitute the given symbol by an expression in the domain constraints.
484 To perform multiple substitutions at once, pass a sequence or a dictionary of ``(old, new)`` pairs to ``subs``.
485 The syntax of this function is similar to :func:`LinExpr.subs`.
486
487 .. classmethod:: fromstring(string)
488
489 Create a domain from a string.
490 Raise :exc:`SyntaxError` if the string is not properly formatted.
491
492 There are also methods to convert a domain to and from `SymPy <http://sympy.org>`_ expressions:
493
494 .. classmethod:: fromsympy(expr)
495
496 Create a domain from a sympy expression.
497
498 .. method:: tosympy()
499
500 Convert the domain to a sympy expression.
501
502
503 .. _reference_operators:
504
505 Comparison and Logic Operators
506 ------------------------------
507
508 The following functions create :class:`Polyhedron` or :class:`Domain` instances using the comparisons of two or more :class:`LinExpr` instances:
509
510 .. function:: Lt(expr1, expr2[, expr3, ...])
511
512 Create the polyhedron with constraints ``expr1 < expr2 < expr3 ...``.
513
514 .. function:: Le(expr1, expr2[, expr3, ...])
515
516 Create the polyhedron with constraints ``expr1 <= expr2 <= expr3 ...``.
517
518 .. function:: Eq(expr1, expr2[, expr3, ...])
519
520 Create the polyhedron with constraints ``expr1 == expr2 == expr3 ...``.
521
522 .. function:: Ne(expr1, expr2[, expr3, ...])
523
524 Create the domain such that ``expr1 != expr2 != expr3 ...``.
525 The result is a :class:`Domain` object, not a :class:`Polyhedron`.
526
527 .. function:: Ge(expr1, expr2[, expr3, ...])
528
529 Create the polyhedron with constraints ``expr1 >= expr2 >= expr3 ...``.
530
531 .. function:: Gt(expr1, expr2[, expr3, ...])
532
533 Create the polyhedron with constraints ``expr1 > expr2 > expr3 ...``.
534
535 The following functions combine :class:`Polyhedron` or :class:`Domain` instances using logic operators:
536
537 .. function:: And(domain1, domain2[, ...])
538
539 Create the intersection domain of the domains given in arguments.
540
541 .. function:: Or(domain1, domain2[, ...])
542
543 Create the union domain of the domains given in arguments.
544
545 .. function:: Not(domain)
546
547 Create the complementary domain of the domain given in argument.
548
549
550 .. _reference_geometry:
551
552 Geometric Objects
553 -----------------
554
555 .. class:: GeometricObject
556
557 :class:`GeometricObject` is an abstract class to represent objects with a geometric representation in space.
558 Subclasses of :class:`GeometricObject` are :class:`Polyhedron`, :class:`Domain` and :class:`Point`.
559 The following elements must be provided:
560
561 .. attribute:: symbols
562
563 The tuple of symbols present in the object expression, sorted according to :class:`Symbol.sortkey()`.
564
565 .. attribute:: dimension
566
567 The dimension of the object, i.e. the number of symbols present in it.
568
569 .. method:: aspolyedron()
570
571 Return a :class:`Polyhedron` object that approximates the geometric object.
572
573 .. method:: asdomain()
574
575 Return a :class:`Domain` object that approximates the geometric object.
576
577 .. class:: Point(coordinates)
578
579 Create a point from a dictionary or a sequence that maps the symbols to their coordinates.
580 Coordinates must be rational numbers.
581
582 For example, the point ``(x: 1, y: 2)`` can be constructed using one of the following instructions:
583
584 >>> x, y = symbols('x y')
585 >>> p = Point({x: 1, y: 2})
586 >>> p = Point([(x, 1), (y, 2)])
587
588 :class:`Point` instances are hashable and should be treated as immutable.
589
590 A point is a :class:`GeometricObject` instance.
591
592 .. attribute:: symbols
593
594 The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.
595
596 .. attribute:: dimension
597
598 The dimension of the point, i.e. the number of symbols present in it.
599
600 .. method:: coordinate(symbol)
601 __getitem__(symbol)
602
603 Return the coordinate value of the given symbol.
604 Raise :exc:`KeyError` if the symbol is not involved in the point.
605
606 .. method:: coordinates()
607
608 Iterate over the pairs ``(symbol, value)`` of coordinates in the point.
609
610 .. method:: values()
611
612 Iterate over the coordinate values in the point.
613
614 .. method:: isorigin()
615
616 Return ``True`` if all coordinates are ``0``.
617
618 .. method:: __bool__()
619
620 Return ``True`` if not all coordinates are ``0``.
621
622 .. method:: __add__(vector)
623
624 Translate the point by a :class:`Vector` object and return the resulting point.
625
626 .. method:: __sub__(point)
627 __sub__(vector)
628
629 The first version substracts a point from another and returns the resulting vector.
630 The second version translates the point by the opposite vector of *vector* and returns the resulting point.
631
632 .. method:: __eq__(point)
633
634 Test whether two points are equal.
635
636
637 .. class:: Vector(coordinates)
638 Vector(point1, point2)
639
640 The first version creates a vector from a dictionary or a sequence that maps the symbols to their coordinates, similarly to :meth:`Point`.
641 The second version creates a vector between two points.
642
643 :class:`Vector` instances are hashable and should be treated as immutable.
644
645 .. attribute:: symbols
646
647 The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.
648
649 .. attribute:: dimension
650
651 The dimension of the point, i.e. the number of symbols present in it.
652
653 .. method:: coordinate(symbol)
654 __getitem__(symbol)
655
656 Return the coordinate value of the given symbol.
657 Raise :exc:`KeyError` if the symbol is not involved in the point.
658
659 .. method:: coordinates()
660
661 Iterate over the pairs ``(symbol, value)`` of coordinates in the point.
662
663 .. method:: values()
664
665 Iterate over the coordinate values in the point.
666
667 .. method:: isnull()
668
669 Return ``True`` if all coordinates are ``0``.
670
671 .. method:: __bool__()
672
673 Return ``True`` if not all coordinates are ``0``.
674
675 .. method:: __add__(point)
676 __add__(vector)
677
678 The first version translates the point *point* to the vector and returns the resulting point.
679 The second version adds vector *vector* to the vector and returns the resulting vector.
680
681 .. method:: __sub__(point)
682 __sub__(vector)
683
684 The first version substracts a point from a vector and returns the resulting point.
685 The second version returns the difference vector between two vectors.
686
687 .. method:: __neg__()
688
689 Return the opposite vector.
690
691 .. method:: __mul__(value)
692
693 Multiply the vector by a scalar value and return the resulting vector.
694
695 .. method:: __truediv__(value)
696
697 Divide the vector by a scalar value and return the resulting vector.
698
699 .. method:: __eq__(vector)
700
701 Test whether two vectors are equal.
702
703 .. method:: angle(vector)
704
705 Retrieve the angle required to rotate the vector into the vector passed in argument.
706 The result is an angle in radians, ranging between ``-pi`` and ``pi``.
707
708 .. method:: cross(vector)
709
710 Compute the cross product of two 3D vectors.
711 If either one of the vectors is not three-dimensional, a :exc:`ValueError` exception is raised.
712
713 .. method:: dot(vector)
714
715 Compute the dot product of two vectors.
716
717 .. method:: norm()
718
719 Return the norm of the vector.
720
721 .. method:: norm2()
722
723 Return the squared norm of the vector.
724
725 .. method:: asunit()
726
727 Return the normalized vector, i.e. the vector of same direction but with norm 1.