Linear Assignment Problem solver (LAPJV/LAPMOD).

Navigation

Verified details

These details have been verified by PyPI
Maintainers
Avatar for rathaROG from gravatar.com rathaROG

Unverified details

These details have not been verified by PyPI
Project links
GitHub Statistics

View statistics for this project via Libraries.io, or by using our public dataset on Google BigQuery

Meta

License: BSD License (BSD-2-Clause)

Author: rathaROG

Tags Linear Assignment, LAPJV, LAPMOD, lap

Requires: Python >=3.7

Classifiers

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.8/3.9/3.10/3.11/3.12.

💽 Installation:

  • Install from PyPI:

    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

    ¹ Windows ARM64 is experimental.
    ² Linux now includes both manylinux and musllinux.

  • 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):

    Click here to expand! 
    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

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

Click here to show more...

lap: Linear Assignment Problem solver

lap is a linear 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)
[2] A. Volgenant, "Linear and Semi-Assignment Problems: A Core Oriented Approach", Computer Ops Res. 23, 917-932 (1996)
[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 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

Verified details

These details have been verified by PyPI
Maintainers
Avatar for rathaROG from gravatar.com rathaROG

Unverified details

These details have not been verified by PyPI
Project links
GitHub Statistics

View statistics for this project via Libraries.io, or by using our public dataset on Google BigQuery

Meta

License: BSD License (BSD-2-Clause)

Author: rathaROG

Tags Linear Assignment, LAPJV, LAPMOD, lap

Requires: Python >=3.7

Classifiers

Release history Release notifications | RSS feed

This version

0.5.8

0.5.7

0.5.6 yanked

Reason this release was yanked:

Wrong info in LONG_DESCRIPTION

0.5.5

0.5.4

0.5.3

0.5.2.post1

0.5.2 yanked

Reason this release was yanked:

Wrong info in LONG_DESCRIPTION

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.8.tar.gz (1.5 MB view hashes)

Uploaded Source

Built Distributions

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

Uploaded CPython 3.12 Windows ARM64

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

Uploaded CPython 3.12 Windows x86-64

lapx-0.5.8-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.8-cp312-cp312-musllinux_1_1_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.12 musllinux: musl 1.1+ ARM64

lapx-0.5.8-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.8-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.8-cp312-cp312-macosx_11_0_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.12 macOS 11.0+ ARM64

lapx-0.5.8-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.8-cp311-cp311-win_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.11 Windows ARM64

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

Uploaded CPython 3.11 Windows x86-64

lapx-0.5.8-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.8-cp311-cp311-musllinux_1_1_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.11 musllinux: musl 1.1+ ARM64

lapx-0.5.8-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.8-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.8-cp311-cp311-macosx_11_0_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.11 macOS 11.0+ ARM64

lapx-0.5.8-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.8-cp310-cp310-win_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.10 Windows ARM64

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

Uploaded CPython 3.10 Windows x86-64

lapx-0.5.8-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.8-cp310-cp310-musllinux_1_1_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.10 musllinux: musl 1.1+ ARM64

lapx-0.5.8-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.8-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.8-cp310-cp310-macosx_11_0_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.10 macOS 11.0+ ARM64

lapx-0.5.8-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.8-cp39-cp39-win_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.9 Windows ARM64

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

Uploaded CPython 3.9 Windows x86-64

lapx-0.5.8-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.8-cp39-cp39-musllinux_1_1_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.9 musllinux: musl 1.1+ ARM64

lapx-0.5.8-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.8-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.8-cp39-cp39-macosx_11_0_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.9 macOS 11.0+ ARM64

lapx-0.5.8-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.8-cp38-cp38-win_amd64.whl (1.5 MB view hashes)

Uploaded CPython 3.8 Windows x86-64

lapx-0.5.8-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.8-cp38-cp38-musllinux_1_1_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.8 musllinux: musl 1.1+ ARM64

lapx-0.5.8-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.8-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.8-cp38-cp38-macosx_11_0_arm64.whl (1.5 MB view hashes)

Uploaded CPython 3.8 macOS 11.0+ ARM64

lapx-0.5.8-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.8-cp37-cp37m-win_amd64.whl (1.5 MB view hashes)

Uploaded CPython 3.7m Windows x86-64

lapx-0.5.8-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.8-cp37-cp37m-musllinux_1_1_aarch64.whl (1.7 MB view hashes)

Uploaded CPython 3.7m musllinux: musl 1.1+ ARM64

lapx-0.5.8-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.8-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.8-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