Skip to main content

Linear Assignment Problem solver (LAPJV/LAPMOD).

Project description

Test Simple Benchmark Test PyPI Build Publish to PyPI

Linear Assignment Problem Solver

lapx basically is Tomas Kazmar's gatagat/lap with support for all Windows/Linux/macOS and Python 3.7-3.12.

💽 Installation

Install from PyPI:

PyPI version Downloads Downloads

pip install lapx
Pre-built Wheels 🛞 Windows Linux macOS
Python 3.7 AMD64 x86_64/aarch64 x86_64
Python 3.8 AMD64 x86_64/aarch64 x86_64/arm64
Python 3.9-3.12 AMD64/ARM64 ¹ x86_64/aarch64 x86_64/arm64

¹ Windows ARM64 is experimental.

Click here to expand!

Install from GitHub repo (Require C++ compiler):

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

Build and install (Require C++ compiler):

git clone https://github.com/rathaROG/lapx.git
cd lapx
pip install "setuptools>=67.8.0"
pip install wheel build
python -m build --wheel
cd dist

🧪 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))

🔎 More about LAP

Click here to expand!

Tomas Kazmar's gatagat/lap is a linear assignment problem solver using Jonker-Volgenant algorithm for dense LAPJV ¹ or sparse LAPMOD ² matrices. Both algorithms are implemented from scratch based solely on the papers ¹˒² and the public domain Pascal implementation provided by A. Volgenant ³. 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.

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

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

The function lapjv(C) returns the assignment cost cost and two arrays x and y. If cost matrix C has shape NxM, 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 and lapsolver's solve dense). 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)]

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

lapx-0.5.9.tar.gz (1.5 MB view hashes)

Uploaded Source

Built Distributions

lapx-0.5.9-cp312-cp312-win_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.12 Windows ARM64

lapx-0.5.9-cp312-cp312-win_amd64.whl (1.5 MB view hashes)

Uploaded CPython 3.12 Windows x86-64

lapx-0.5.9-cp312-cp312-musllinux_1_1_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.12 musllinux: musl 1.1+ x86-64

lapx-0.5.9-cp312-cp312-musllinux_1_1_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.12 musllinux: musl 1.1+ ARM64

lapx-0.5.9-cp312-cp312-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.17+ ARM64

lapx-0.5.9-cp312-cp312-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.12 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

lapx-0.5.9-cp312-cp312-macosx_11_0_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.12 macOS 11.0+ ARM64

lapx-0.5.9-cp312-cp312-macosx_10_9_x86_64.whl (1.5 MB view hashes)

Uploaded CPython 3.12 macOS 10.9+ x86-64

lapx-0.5.9-cp311-cp311-win_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.11 Windows ARM64

lapx-0.5.9-cp311-cp311-win_amd64.whl (1.5 MB view hashes)

Uploaded CPython 3.11 Windows x86-64

lapx-0.5.9-cp311-cp311-musllinux_1_1_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ x86-64

lapx-0.5.9-cp311-cp311-musllinux_1_1_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ ARM64

lapx-0.5.9-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ ARM64

lapx-0.5.9-cp311-cp311-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.11 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

lapx-0.5.9-cp311-cp311-macosx_11_0_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.11 macOS 11.0+ ARM64

lapx-0.5.9-cp311-cp311-macosx_10_9_x86_64.whl (1.5 MB view hashes)

Uploaded CPython 3.11 macOS 10.9+ x86-64

lapx-0.5.9-cp310-cp310-win_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.10 Windows ARM64

lapx-0.5.9-cp310-cp310-win_amd64.whl (1.5 MB view hashes)

Uploaded CPython 3.10 Windows x86-64

lapx-0.5.9-cp310-cp310-musllinux_1_1_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ x86-64

lapx-0.5.9-cp310-cp310-musllinux_1_1_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ ARM64

lapx-0.5.9-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ ARM64

lapx-0.5.9-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.10 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

lapx-0.5.9-cp310-cp310-macosx_11_0_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.10 macOS 11.0+ ARM64

lapx-0.5.9-cp310-cp310-macosx_10_9_x86_64.whl (1.5 MB view hashes)

Uploaded CPython 3.10 macOS 10.9+ x86-64

lapx-0.5.9-cp39-cp39-win_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.9 Windows ARM64

lapx-0.5.9-cp39-cp39-win_amd64.whl (1.5 MB view hashes)

Uploaded CPython 3.9 Windows x86-64

lapx-0.5.9-cp39-cp39-musllinux_1_1_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ x86-64

lapx-0.5.9-cp39-cp39-musllinux_1_1_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ ARM64

lapx-0.5.9-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ ARM64

lapx-0.5.9-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.9 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

lapx-0.5.9-cp39-cp39-macosx_11_0_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.9 macOS 11.0+ ARM64

lapx-0.5.9-cp39-cp39-macosx_10_9_x86_64.whl (1.5 MB view hashes)

Uploaded CPython 3.9 macOS 10.9+ x86-64

lapx-0.5.9-cp38-cp38-win_amd64.whl (1.5 MB view hashes)

Uploaded CPython 3.8 Windows x86-64

lapx-0.5.9-cp38-cp38-musllinux_1_1_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ x86-64

lapx-0.5.9-cp38-cp38-musllinux_1_1_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ ARM64

lapx-0.5.9-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ ARM64

lapx-0.5.9-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.8 manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

lapx-0.5.9-cp38-cp38-macosx_11_0_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.8 macOS 11.0+ ARM64

lapx-0.5.9-cp38-cp38-macosx_10_9_x86_64.whl (1.5 MB view hashes)

Uploaded CPython 3.8 macOS 10.9+ x86-64

lapx-0.5.9-cp37-cp37m-win_amd64.whl (1.5 MB view hashes)

Uploaded CPython 3.7m Windows x86-64

lapx-0.5.9-cp37-cp37m-musllinux_1_1_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.1+ x86-64

lapx-0.5.9-cp37-cp37m-musllinux_1_1_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.1+ ARM64

lapx-0.5.9-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ ARM64

lapx-0.5.9-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl (1.7 MB view hashes)

Uploaded CPython 3.7m manylinux: glibc 2.17+ x86-64 manylinux: glibc 2.5+ x86-64

lapx-0.5.9-cp37-cp37m-macosx_10_9_x86_64.whl (1.5 MB view hashes)

Uploaded CPython 3.7m macOS 10.9+ x86-64

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page