Metadata-Version: 2.1
Name: lapx
Version: 0.5.8
Summary: Linear Assignment Problem solver (LAPJV/LAPMOD).
Home-page: https://github.com/rathaROG/lapx
Author: rathaROG
License: BSD-2-Clause
Keywords: Linear Assignment,LAPJV,LAPMOD,lap
Classifier: Development Status :: 4 - Beta
Classifier: Environment :: Console
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Education
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: BSD License
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.7
Classifier: Programming Language :: Python :: 3.8
Classifier: Programming Language :: Python :: 3.9
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Education
Classifier: Topic :: Education :: Testing
Classifier: Topic :: Scientific/Engineering
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Topic :: Software Development
Classifier: Topic :: Software Development :: Libraries
Classifier: Operating System :: Microsoft :: Windows
Classifier: Operating System :: POSIX
Classifier: Operating System :: Unix
Classifier: Operating System :: MacOS
Requires-Python: >=3.7
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: Cython >=0.29.32
Requires-Dist: numpy >=1.21.6

[![Test Simple](https://github.com/rathaROG/lapx/actions/workflows/test_simple.yaml/badge.svg)](https://github.com/rathaROG/lapx/actions/workflows/test_simple.yaml)
[![Benchmark](https://github.com/rathaROG/lapx/actions/workflows/benchmark.yaml/badge.svg)](https://github.com/rathaROG/lapx/actions/workflows/benchmark.yaml)
[![Test PyPI Build](https://github.com/rathaROG/lapx/actions/workflows/prepublish.yaml/badge.svg)](https://github.com/rathaROG/lapx/actions/workflows/prepublish.yaml)
[![Publish to PyPI](https://github.com/rathaROG/lapx/actions/workflows/publish.yaml/badge.svg)](https://github.com/rathaROG/lapx/actions/workflows/publish.yaml)

# Linear Assignment Problem Solver

`lapx` basically is Tomas Kazmar's [`gatagat/lap`](https://github.com/gatagat/lap) with support for all Windows/Linux/macOS and Python 3.7/3.8/3.9/3.10/3.11/3.12.

* Based on: [[ed04ab7752]](https://github.com/gatagat/lap/tree/ed04ab7752c7c9688ddcbae534633f34ce04361f)
* License: BSD-2-Clause, see [`LICENSE`](LICENSE) @[`gatagat`](https://github.com/gatagat)

## 💽 Installation:

* Install from [PyPI](https://pypi.org/project/lapx/):

  ```
  pip install lapx
  ```

  | **Pre-built Wheels** 🛞 | **Windows** ✅ | **Linux** ✅ | **macOS** ✅ |
  |:---:|:---:|:---:|:---:|
  | Python v3.7 | AMD64 | x86_64/aarch64 ² | x86_64 |
  | Python v3.8 | AMD64 | x86_64/aarch64 ² | x86_64/arm64 |
  | Python v3.9 | AMD64/ARM64 ¹ | x86_64/aarch64 ² | x86_64/arm64 |
  | Python v3.10 | AMD64/ARM64 ¹ | x86_64/aarch64 ² | x86_64/arm64 |
  | Python v3.11 | AMD64/ARM64 ¹ | x86_64/aarch64 ² | x86_64/arm64 |
  | Python v3.12 | AMD64/ARM64 ¹ | x86_64/aarch64 ² | x86_64/arm64 |

  <sup>¹ Windows ARM64 is experimental.</sup><br>
  <sup>² Linux now includes both `manylinux` and `musllinux`.</sup><br>

* Or install from GitHub repo directly (Require C++ compiler):

  ```
  pip install git+https://github.com/rathaROG/lapx.git
  ```

* Or clone and build on your local machine (Require C++ compiler):

  <details><summary><ins>Click here to expand!</ins></summary>
  
  ```
  git clone https://github.com/rathaROG/lapx.git
  cd lapx
  python -m pip install --upgrade pip
  pip install "setuptools>=67.2.0"
  pip install wheel build
  python -m build --wheel
  cd dist
  ```
  
  </details>

## 🧪 Usage:

* `lapx` is just the name for package distribution.
* The same as `lap`, use `import lap` to import; for example:

  ```
  import lap
  import numpy as np
  print(lap.lapjv(np.random.rand(4, 5), extend_cost=True))
  ```

<br />

<details><summary>Click here to show more...</summary>

<br />

lap: Linear Assignment Problem solver
=====================================

**lap** is a [linear assignment
problem](https://en.wikipedia.org/wiki/Assignment_problem) solver using
Jonker-Volgenant algorithm for dense (LAPJV [1]) or sparse (LAPMOD [2])
matrices.

Both algorithms are implemented from scratch based solely on the papers [1,2]
and the public domain Pascal implementation provided by A. Volgenant [3].

In my tests the LAPMOD implementation seems to be faster than the LAPJV
implementation for matrices with a side of more than ~5000 and with less than
50% finite coefficients.

[1] R. Jonker and A. Volgenant, "A Shortest Augmenting Path Algorithm for Dense
and Sparse Linear Assignment Problems", Computing 38, 325-340 (1987)<br>
[2] A. Volgenant, "Linear and Semi-Assignment Problems: A Core Oriented
Approach", Computer Ops Res. 23, 917-932 (1996)<br>
[3] http://www.assignmentproblems.com/LAPJV.htm


### Usage

```
cost, x, y = lap.lapjv(C)
```

The function `lapjv(C)` returns the assignment cost (`cost`) and two arrays, `x, y`. If cost matrix `C` has shape N x M, then `x` is a size-N array specifying to which column is row is assigned, and `y` is a size-M array specifying to which row each column is assigned. For example, an output of `x = [1, 0]` indicates that row 0 is assigned to column 1 and row 1 is assigned to column 0. Similarly, an output of `x = [2, 1, 0]` indicates that row 0 is assigned to column 2, row 1 is assigned to column 1, and row 2 is assigned to column 0.

Note that this function *does not* return the assignment matrix (as done by scipy's [`linear_sum_assignment`](https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html) and lapsolver's [`solve dense`](https://github.com/cheind/py-lapsolver)). The assignment matrix can be constructed from `x` as follows:
```
A = np.zeros((N, M))
for i in range(N):
    A[i, x[i]] = 1
```
Equivalently, we could construct the assignment matrix from `y`:
```
A = np.zeros((N, M))
for j in range(M):
    A[y[j], j] = 1
```

Finally, note that the outputs are redundant: we can construct `x` from `y`, and vise versa:
```
x = [np.where(y == i)[0][0] for i in range(N)]
y = [np.where(x == j)[0][0] for j in range(M)]
```

</details>
