Metadata-Version: 2.1
Name: dualdesc
Version: 0.2.0
Summary: Dual description of polytopes.
Home-page: https://gitlab.com/valtron/dualdesc
Author: valtron
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Operating System :: OS Independent
Classifier: License :: OSI Approved :: GNU Lesser General Public License v3 or later (LGPLv3+)
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: pyparma (~=0.5.0)
Requires-Dist: numpy (~=1.25.2)

# dualdesc

[![Supported Python versions](https://img.shields.io/pypi/pyversions/dualdesc)](https://gitlab.com/valtron/dualdesc)
[![Build status](https://img.shields.io/gitlab/pipeline-status/valtron/dualdesc?branch=master)](https://gitlab.com/valtron/dualdesc/-/pipelines)
[![Coverage](https://img.shields.io/gitlab/coverage/valtron/dualdesc/master)](https://gitlab.com/valtron/dualdesc/-/pipelines)
[![Downloads](https://static.pepy.tech/badge/dualdesc/month)](https://pepy.tech/project/dualdesc)
[![License](https://img.shields.io/pypi/l/dualdesc)](https://gitlab.com/valtron/dualdesc/-/blob/master/LICENSE)

Dual description for polytopes. A wrapper around [pyparma](https://pypi.org/project/pyparma), which itself wraps [ppl](https://bugseng.com/ppl).
Mainly for easily converting between H- and V-representations. No utilities for facet enumeration, adjacencies, etc.


## Usage

### Constructors

This package contains one class, `Polytope`. Main constructors are:

`Polytope.FromHalfspaces(A, b)` represents the polytope defined by all points `x` s.t. `A @ x <= b`.
If there are `n` halfspaces and the ambient dimension is `d`, the shapes of these matrices are:
- `A`: `(nu, d)`
- `b`: `(d,)`

`Polytope.FromGenerators(V, R)` represents the polytope defined by `conv(V) + nonneg(R)`,
where `conv` is the convex combination of a set of points and `nonneg` is non-negative linear combinations
of a set of points, and `+` is Minkowski addition.

There are also `Polytope.Empty(dim: int)` and `Polytope.Universe(dim: int)` constructors.

All constructors also take a `scale > 0` (default `1e5`) parameter to control quantization, since ppl uses rational arithmetic.
Quantization is done as `q = round(scale * x)` going into ppl, and `x = q / scale` coming out.

### Conversion

There are methods `A, b = poly.get_inequalities()` and `V, R = poly.get_generators()` which return the respective representations.

Note that PPL is lazy, and converting between representations can take a long time, so calling these methods might be slow.


### Incremental construction

Incremental construction is supported via methods `add_halfspace(A, b)`, `add_point(V)`, and `add_ray(R)`.
All are "vectorized", i.e. they support adding a single halfspace/point/ray, or multiple.

Since these mutate, you can also copy polytopes: `poly.copy()`.


### A simple example

The example below defines an unbounded (i.e. non-null cone part) polytope with 3 facets and 2 vertices:

```python
import numpy as np
import dualdesc as dd

M = np.array([
	[1, 0, 1], # x0        <= 1
	[0, 2, 1], #      2 x1 <= 1
	[1, 1, 1], # x0 +   x1 <= 1
], dtype = np.float64)
A = M[:,:2]
b = M[:,-1]
poly = dd.Polytope.FromHalfspaces(A, b)
V, R = poly.to_generators()
# Vertices:
# 	V = [[0.5, 0.5], [1, 0]]
# Cone:
# 	R = [[-1, 0], [0, -1]]
```

## Why ...?

### Why not pypoman?

[pypoman](https://scaron.info/doc/pypoman) has more features, but only supports bounded polytopes.


### Why not use pyparma directly?

It doesn't have a nice interface.


### Why not use pycddlib?

[pycddlib](https://pycddlib.readthedocs.io) has more features (like adjacency lists), but is too low level and doesn't have a nice interface.


### Why not wrap pplpy instead?

I might do this at some point, since there are issues building `pyparma` with Cython 3.
