83ee9d3964aaa99133e94e00733c09b1a5c94af2
[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:: widen(polyhedron)
288
289 Compute the *standard widening* of two polyhedra, à la Halbwachs.
290
291 In its current implementation, this method is slow and should not be used on large polyhedra.
292
293
294 .. data:: Empty
295
296 The empty polyhedron, whose set of constraints is not satisfiable.
297
298 .. data:: Universe
299
300 The universe polyhedron, whose set of constraints is always satisfiable, i.e. is empty.
301
302 Domains
303 -------
304
305 A *domain* is a union of polyhedra.
306 Unlike polyhedra, domains allow exact computation of union and complementary operations.
307
308 .. class:: Domain(*polyhedra)
309 Domain(string)
310 Domain(geometric object)
311
312 Return a domain from a sequence of polyhedra.
313
314 >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
315 >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
316 >>> dom = Domain([square, square2])
317
318 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:
319
320 >>> square = Polyhedron('0 <= x <= 2, 0 <= y <= 2')
321 >>> square2 = Polyhedron('2 <= x <= 4, 2 <= y <= 4')
322 >>> dom = square | square2
323 >>> dom = Or(square, square2)
324
325 Alternatively, a domain can be built from a string:
326
327 >>> dom = Domain('0 <= x <= 2, 0 <= y <= 2; 2 <= x <= 4, 2 <= y <= 4')
328
329 Finally, a domain can be built from a :class:`GeometricObject` instance, calling the :meth:`GeometricObject.asdomain` method.
330
331 A domain is also a :class:`GeometricObject` instance.
332 A domain with a unique polyhedron is automatically subclassed as a :class:`Polyhedron` instance.
333
334 .. attribute:: polyhedra
335
336 The tuple of polyhedra present in the domain.
337
338 .. attribute:: symbols
339
340 The tuple of symbols present in the domain equations, sorted according to :meth:`Symbol.sortkey`.
341
342 .. attribute:: dimension
343
344 The dimension of the domain, i.e. the number of symbols present in it.
345
346 .. method:: isempty()
347
348 Return ``True`` if the domain is empty, that is, equal to :data:`Empty`.
349
350 .. method:: __bool__()
351
352 Return ``True`` if the domain is non-empty.
353
354 .. method:: isuniverse()
355
356 Return ``True`` if the domain is universal, that is, equal to :data:`Universe`.
357
358 .. method:: isbounded()
359
360 Return ``True`` is the domain is bounded.
361
362 .. method:: __eq__(domain)
363
364 Return ``True`` if two domains are equal.
365
366 .. method:: isdisjoint(domain)
367
368 Return ``True`` if two domains have a null intersection.
369
370 .. method:: issubset(domain)
371 __le__(domain)
372
373 Report whether another domain contains the domain.
374
375 .. method:: __lt__(domain)
376
377 Report whether another domain is contained within the domain.
378
379 .. method:: complement()
380 __invert__()
381
382 Return the complementary domain of the domain.
383
384 .. method:: make_disjoint()
385
386 Return an equivalent domain, whose polyhedra are disjoint.
387
388 .. method:: coalesce()
389
390 Simplify the representation of the domain by trying to combine pairs of polyhedra into a single polyhedron, and return the resulting domain.
391
392 .. method:: detect_equalities()
393
394 Simplify the representation of the domain by detecting implicit equalities, and return the resulting domain.
395
396 .. method:: remove_redundancies()
397
398 Remove redundant constraints in the domain, and return the resulting domain.
399
400 .. method:: project(symbols)
401
402 Project out the sequence of symbols given in arguments, and return the resulting domain.
403
404 .. method:: sample()
405
406 Return a sample of the domain, as an integer instance of :class:`Point`.
407 If the domain is empty, a :exc:`ValueError` exception is raised.
408
409 .. method:: intersection(domain[, ...])
410 __and__(domain)
411
412 Return the intersection of two or more domains as a new domain.
413 As an alternative, function :func:`And` can be used.
414
415 .. method:: union(domain[, ...])
416 __or__(domain)
417 __add__(domain)
418
419 Return the union of two or more domains as a new domain.
420 As an alternative, function :func:`Or` can be used.
421
422 .. method:: difference(domain)
423 __sub__(domain)
424
425 Return the difference between two domains as a new domain.
426
427 .. method:: lexmin()
428
429 Return the lexicographic minimum of the elements in the domain.
430
431 .. method:: lexmax()
432
433 Return the lexicographic maximum of the elements in the domain.
434
435 .. method:: vertices()
436
437 Return the vertices of the domain, as a list of rational instances of :class:`Point`.
438
439 .. method:: points()
440
441 Return the integer points of a bounded domain, as a list of integer instances of :class:`Point`.
442 If the domain is not bounded, a :exc:`ValueError` exception is raised.
443
444 .. method:: __contains__(point)
445
446 Return ``True`` if the point is contained within the domain.
447
448 .. method:: faces()
449
450 Return the list of faces of a bounded domain.
451 Each face is represented by a list of vertices, in the form of rational instances of :class:`Point`.
452 If the domain is not bounded, a :exc:`ValueError` exception is raised.
453
454 .. method:: plot(plot=None, **options)
455
456 Plot a 2D or 3D domain using `matplotlib <http://matplotlib.org/>`_.
457 Draw it to the current *plot* object if present, otherwise create a new one.
458 *options* are keyword arguments passed to the matplotlib drawing functions, they can be used to set the drawing color for example.
459 Raise :exc:`ValueError` is the domain is not 2D or 3D.
460
461 .. method:: subs(symbol, expression)
462 subs(pairs)
463
464 Substitute the given symbol by an expression in the domain constraints.
465 To perform multiple substitutions at once, pass a sequence or a dictionary of ``(old, new)`` pairs to ``subs``.
466 The syntax of this function is similar to :func:`LinExpr.subs`.
467
468 .. classmethod:: fromstring(string)
469
470 Create a domain from a string.
471 Raise :exc:`SyntaxError` if the string is not properly formatted.
472
473 There are also methods to convert a domain to and from `SymPy <http://sympy.org>`_ expressions:
474
475 .. classmethod:: fromsympy(expr)
476
477 Create a domain from a sympy expression.
478
479 .. method:: tosympy()
480
481 Convert the domain to a sympy expression.
482
483
484 Comparison and Logic Operators
485 ------------------------------
486
487 The following functions create :class:`Polyhedron` or :class:`Domain` instances using the comparisons of two or more :class:`LinExpr` instances:
488
489 .. function:: Lt(expr1, expr2[, expr3, ...])
490
491 Create the polyhedron with constraints ``expr1 < expr2 < expr3 ...``.
492
493 .. function:: Le(expr1, expr2[, expr3, ...])
494
495 Create the polyhedron with constraints ``expr1 <= expr2 <= expr3 ...``.
496
497 .. function:: Eq(expr1, expr2[, expr3, ...])
498
499 Create the polyhedron with constraints ``expr1 == expr2 == expr3 ...``.
500
501 .. function:: Ne(expr1, expr2[, expr3, ...])
502
503 Create the domain such that ``expr1 != expr2 != expr3 ...``.
504 The result is a :class:`Domain`, not a :class:`Polyhedron`.
505
506 .. function:: Ge(expr1, expr2[, expr3, ...])
507
508 Create the polyhedron with constraints ``expr1 >= expr2 >= expr3 ...``.
509
510 .. function:: Gt(expr1, expr2[, expr3, ...])
511
512 Create the polyhedron with constraints ``expr1 > expr2 > expr3 ...``.
513
514 The following functions combine :class:`Polyhedron` or :class:`Domain` instances using logic operators:
515
516 .. function:: Or(domain1, domain2[, ...])
517
518 Create the union domain of the domains given in arguments.
519
520 .. function:: And(domain1, domain2[, ...])
521
522 Create the intersection domain of the domains given in arguments.
523
524 .. function:: Not(domain)
525
526 Create the complementary domain of the domain given in argument.
527
528
529 Geometric Objects
530 -----------------
531
532 .. class:: GeometricObject
533
534 :class:`GeometricObject` is an abstract class to represent objects with a geometric representation in space.
535 Subclasses of :class:`GeometricObject` are :class:`Polyhedron`, :class:`Domain` and :class:`Point`.
536 The following elements must be provided:
537
538 .. attribute:: symbols
539
540 The tuple of symbols present in the object expression, sorted according to :class:`Symbol.sortkey()`.
541
542 .. attribute:: dimension
543
544 The dimension of the object, i.e. the number of symbols present in it.
545
546 .. method:: aspolyedron()
547
548 Return a :class:`Polyhedron` object that approximates the geometric object.
549
550 .. method:: asdomain()
551
552 Return a :class:`Domain` object that approximates the geometric object.
553
554 .. class:: Point(coordinates)
555
556 Create a point from a dictionary or a sequence that maps the symbols to their coordinates.
557 Coordinates must be rational numbers.
558
559 For example, the point ``(x: 1, y: 2)`` can be constructed using one of the following instructions:
560
561 >>> x, y = symbols('x y')
562 >>> p = Point({x: 1, y: 2})
563 >>> p = Point([(x, 1), (y, 2)])
564
565 :class:`Point` instances are hashable and should be treated as immutable.
566
567 A point is a :class:`GeometricObject` instance.
568
569 .. attribute:: symbols
570
571 The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.
572
573 .. attribute:: dimension
574
575 The dimension of the point, i.e. the number of symbols present in it.
576
577 .. method:: coordinate(symbol)
578 __getitem__(symbol)
579
580 Return the coordinate value of the given symbol.
581 Raise :exc:`KeyError` if the symbol is not involved in the point.
582
583 .. method:: coordinates()
584
585 Iterate over the pairs ``(symbol, value)`` of coordinates in the point.
586
587 .. method:: values()
588
589 Iterate over the coordinate values in the point.
590
591 .. method:: isorigin()
592
593 Return ``True`` if all coordinates are ``0``.
594
595 .. method:: __bool__()
596
597 Return ``True`` if not all coordinates are ``0``.
598
599 .. method:: __add__(vector)
600
601 Translate the point by a :class:`Vector` object and return the resulting point.
602
603 .. method:: __sub__(point)
604 __sub__(vector)
605
606 The first version substracts a point from another and returns the resulting vector.
607 The second version translates the point by the opposite vector of *vector* and returns the resulting point.
608
609 .. method:: __eq__(point)
610
611 Test whether two points are equal.
612
613
614 .. class:: Vector(coordinates)
615 Vector(point1, point2)
616
617 The first version creates a vector from a dictionary or a sequence that maps the symbols to their coordinates, similarly to :meth:`Point`.
618 The second version creates a vector between two points.
619
620 :class:`Vector` instances are hashable and should be treated as immutable.
621
622 .. attribute:: symbols
623
624 The tuple of symbols present in the point, sorted according to :class:`Symbol.sortkey()`.
625
626 .. attribute:: dimension
627
628 The dimension of the point, i.e. the number of symbols present in it.
629
630 .. method:: coordinate(symbol)
631 __getitem__(symbol)
632
633 Return the coordinate value of the given symbol.
634 Raise :exc:`KeyError` if the symbol is not involved in the point.
635
636 .. method:: coordinates()
637
638 Iterate over the pairs ``(symbol, value)`` of coordinates in the point.
639
640 .. method:: values()
641
642 Iterate over the coordinate values in the point.
643
644 .. method:: isnull()
645
646 Return ``True`` if all coordinates are ``0``.
647
648 .. method:: __bool__()
649
650 Return ``True`` if not all coordinates are ``0``.
651
652 .. method:: __add__(point)
653 __add__(vector)
654
655 The first version translates the point *point* to the vector and returns the resulting point.
656 The second version adds vector *vector* to the vector and returns the resulting vector.
657
658 .. method:: __sub__(point)
659 __sub__(vector)
660
661 The first version substracts a point from a vector and returns the resulting point.
662 The second version returns the difference vector between two vectors.
663
664 .. method:: __neg__()
665
666 Return the opposite vector.
667
668 .. method:: __mul__(value)
669
670 Multiply the vector by a scalar value and return the resulting vector.
671
672 .. method:: __truediv__(value)
673
674 Divide the vector by a scalar value and return the resulting vector.
675
676 .. method:: __eq__(vector)
677
678 Test whether two vectors are equal.
679
680 .. method:: angle(vector)
681
682 Retrieve the angle required to rotate the vector into the vector passed in argument.
683 The result is an angle in radians, ranging between ``-pi`` and ``pi``.
684
685 .. method:: cross(vector)
686
687 Compute the cross product of two 3D vectors.
688 If either one of the vectors is not three-dimensional, a :exc:`ValueError` exception is raised.
689
690 .. method:: dot(vector)
691
692 Compute the dot product of two vectors.
693
694 .. method:: norm()
695
696 Return the norm of the vector.
697
698 .. method:: norm2()
699
700 Return the squared norm of the vector.
701
702 .. method:: asunit()
703
704 Return the normalized vector, i.e. the vector of same direction but with norm 1.