Linear Assignment Problem solver (LAPJV/LAPMOD).
Project description
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.
- Based on: [ed04ab7752]
- License: BSD-2-Clause, see
LICENSE
@gatagat
Installation: Windows ✅ | Linux ✅ | macOS ✅
-
Install from PyPI:
pip install lapx
-
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):
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
, useimport 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
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for lapx-0.5.5-cp312-cp312-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8ff0fbc3f5f17539180e592e4670034a2d2a68df73bb568a209390f0cdf30242 |
|
MD5 | 9f87d561f44a6890327dc3d42c0db1c1 |
|
BLAKE2b-256 | 9b9f4f0e9d342d7332ab91995db76d7ed76362e6f9a1157672093ee83e892ae1 |
Hashes for lapx-0.5.5-cp312-cp312-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 09c383490babe88a63e31c78eaf3b800a80160aa9b569d8e781c14136feb503c |
|
MD5 | b49318659e731c04d8379099d3203848 |
|
BLAKE2b-256 | 1a9883e970ee48151c6bb43422ae8e02dd23b3d45242ebd6283ed4e8de3d6f18 |
Hashes for lapx-0.5.5-cp312-cp312-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 724213db8687f4a3d342248ed61c148acdc0f9e8fcaca55f6664b623ea43f1fa |
|
MD5 | c4f7cfd4add10da500aec46aef2ce74f |
|
BLAKE2b-256 | 2dc89329cd7a1f63c9eff3699a6ef0a2f8936348341e3a90a29df1c376cc4df9 |
Hashes for lapx-0.5.5-cp312-cp312-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 23340a3ee0ede9857c2bf335c6d13ee5e7c49259ffcc121835ed63d089347b6f |
|
MD5 | d8e91f249642bad22efba3df71edb8b8 |
|
BLAKE2b-256 | 8f08efa57bfdd3e0acbc0e75231d2ee45cd4e701d41f99963820bac61519f1ce |
Hashes for lapx-0.5.5-cp312-cp312-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b083f7cfa4262dce2ccc5c62815042ad3bc2098b38b3be0af662c3f4693e9156 |
|
MD5 | 28720453f671769f31f3855af4130ac8 |
|
BLAKE2b-256 | bfb3f078a30a8b489c58c74a90d4bc052348f0f039d5f1615eba24bb2862b29a |
Hashes for lapx-0.5.5-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6602284aa37a9dfaa81836689cb88ce8a0ea23e2cd3488cbe55164c8b2a2f5e8 |
|
MD5 | 112125c864983b09fb1805b476c04d79 |
|
BLAKE2b-256 | 8e0884ac2a69c759da1d50743c3f5ffe94f713564110d9039972374f6cd8b22d |
Hashes for lapx-0.5.5-cp311-cp311-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 034713fead7c58f3e11dfbd617614da773bba43aaf3984911ac0a43ee3be2aee |
|
MD5 | 5c3656b8642dfd572efad44eddae1527 |
|
BLAKE2b-256 | 5c56fd4665997836c94c1011926fbef19906bd1a691a93f6d6482b9354b0045d |
Hashes for lapx-0.5.5-cp311-cp311-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c1a2caedae2d2ffc96c8a02f380f72848e5ea6d2d300057d565eb4a243f321b2 |
|
MD5 | 92f5482e8a1e79dfa91eafefe68411c2 |
|
BLAKE2b-256 | edb77b688b7de60eb513dd6f3b53356686c2a6b27da581866a7b5821dc259d19 |
Hashes for lapx-0.5.5-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fcbb35dfc4fad4cc7626b88681a928a3ccc05f0fb5bd17e682f302da2ee63a8e |
|
MD5 | fd876089639cbe159e5e5fc135ea79f4 |
|
BLAKE2b-256 | 3b0f2555d89426cf4fe5d4a8187e259680f93ff92a2217e851a88e1a63e4172f |
Hashes for lapx-0.5.5-cp311-cp311-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 983198d1608253feb54dfcac9bab5d280015daa864e2effb4e7ca07e94584a4e |
|
MD5 | fc00cbbea226c0317349cabf966695d4 |
|
BLAKE2b-256 | 2bb46496aa5fb8b60d63bcca95c8730f7deae1430c030a6d3412bda077ea4a3a |
Hashes for lapx-0.5.5-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8a3cbf1e53c6de54c9e5a523e1f16535aefe251aa71e4d145fe10a014dc55d26 |
|
MD5 | a74f25d3cc8377210c453ceae9abdc41 |
|
BLAKE2b-256 | bcbb56dd2f5f1bcdfb7e46bbdb301f76aa56581e17c9b39a3ddf092f3d370b05 |
Hashes for lapx-0.5.5-cp310-cp310-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 56c57b36802ae0ee47744783cd4f4afef7c94673dd16eea08bd05983b7c5bb0e |
|
MD5 | 011d32fc5d1ad2a170681b06c52b9538 |
|
BLAKE2b-256 | dedf9b89511216fc7b85970172c591b9a5bf54e76211d6719c28e2b455b62461 |
Hashes for lapx-0.5.5-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d0b1376e7be0126fe9d99a4378de4eaa443ec6e131f1f75ce567e076f34a0a0a |
|
MD5 | 9792b67d578cb1fb3e8f29b1c0bdb6a0 |
|
BLAKE2b-256 | b11c1fd887004a4d68b9694e5cfe38cf450758dcf7d7436fbe576f7a5b9293c2 |
Hashes for lapx-0.5.5-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dd323b414004a957444b34bdb9f17145fea9ea6bc3319717c24ae90fa2714de2 |
|
MD5 | a29844037fb481f54164c19be0d57b33 |
|
BLAKE2b-256 | 46eed9ced8570b0c97758f435283be0b4cb4c2ca8368c999689522bb968a7be7 |
Hashes for lapx-0.5.5-cp310-cp310-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 930f2bb426da2c7ec3adda20c5c7c8068f085b9939ab5e1504865226492872c0 |
|
MD5 | 553f622d43f1fb1c806c87524e905587 |
|
BLAKE2b-256 | a93a6765e1d2a0e356d01a8743dee88afd3c20ad1b3499e3beb7e841cecc45dc |
Hashes for lapx-0.5.5-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e179fd5c59dfc161141a159d2455802c6a62ba8cd27f519f8c4057275450bb2b |
|
MD5 | cd3dc9724287739ae4b75cc7616b4493 |
|
BLAKE2b-256 | 7984ddfed45ff86cdc7b17ee020b1494cfb8c0de570444e5a1c7d9aa0d2c749c |
Hashes for lapx-0.5.5-cp39-cp39-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 90c2db38f6c2254926770736e056157b40860115456d0b66471afc52db8d8e80 |
|
MD5 | 3f3334222c2f3d23fd254ef3ce038def |
|
BLAKE2b-256 | 1e26191b502f179cb7e110f5a6171b8e9d41937898ef2d4d52a05ae67921d80f |
Hashes for lapx-0.5.5-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 800e8808d27e0c06c0d0f768ff5788b32112d8d96f5737b808f92c8a48311eec |
|
MD5 | 7a78e546c20f5a94af81945318abf5d8 |
|
BLAKE2b-256 | 45a8bf5ce171f3d334840e28baf5298c5f0dfab0c6d572156d5aefdf7f199137 |
Hashes for lapx-0.5.5-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 28ff1f93ad46cd2d5615c6a6dbd03724ae74216a9dec8fe5625c321f5c100723 |
|
MD5 | 98ff1bce4ab57e689b54515d8af386b7 |
|
BLAKE2b-256 | d261106aafaab79ea16dffb758c72ad6cc36cf47b4c964a62dbb6e920bc9ff72 |
Hashes for lapx-0.5.5-cp39-cp39-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6cac8ae7f049a000ee9167f6b9c66480660e66930a178ec334d092b56cb3e3c9 |
|
MD5 | e343b6357a18f134c4b14befdf97f08f |
|
BLAKE2b-256 | 65959451af74dc7a04e8f81ed88ec44d6c50bcb62b4a8e820fbe9ccf8fdf2a83 |
Hashes for lapx-0.5.5-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f80226b017252b1683de5419df73a54c7858c34f4cff09796dbabb4d1ba6c0fb |
|
MD5 | d3747a9a3b576142664297b783ce3e9e |
|
BLAKE2b-256 | 65e73d588586830fa30a524bf70b2f2a6dabbaddb7e601bf895d39952d2193ff |
Hashes for lapx-0.5.5-cp38-cp38-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3b92dd73a337d92e16782c75cc1b79b41320a718e1ac48c6adf2705ec6803ad8 |
|
MD5 | 29b618a289fd288fd0402cb0c917a305 |
|
BLAKE2b-256 | a982e1766cc7fab145d5821add13e184d92767716e8a608bbe837f1ad29fd701 |
Hashes for lapx-0.5.5-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fe4bcb04920d1258e16227fe4f1b31f6aabf7ddaec5a31028edcdf018a67978f |
|
MD5 | 9db5cfcbf4896bbc2d097339a7c07102 |
|
BLAKE2b-256 | 7f8e0e7c32a0a9cd0634f9189718d270f838084a28b44ffa4f2ea25b0626d884 |
Hashes for lapx-0.5.5-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0d85cc03555bd8594628638b017b92339deccd5696e7cfb8ea294d5a23f05045 |
|
MD5 | 29e578ed0cf63c40782951062bd6ae1b |
|
BLAKE2b-256 | e596aca8554d97577cab4ba7c96044f78f7e6a40455f97f80ffb37c611a56200 |
Hashes for lapx-0.5.5-cp38-cp38-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 66a970fb770f201ad0714d64163bb7061c23c0c5ad09854a648dbed9cf18cf91 |
|
MD5 | cec0b044f0cdd9b6dbceb44ffc185ebd |
|
BLAKE2b-256 | bf95c5bb50ee0985b87617c09c942d498b717cdfe26fd3fd52908f733bf50583 |
Hashes for lapx-0.5.5-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e708bfe24d9cb4f230fa8a68a2d43353cd3ed31ebe3ae105789d1d6d3565b734 |
|
MD5 | d5eb692be668dd6467c13fa1b43cb4f0 |
|
BLAKE2b-256 | 2f2b37eede40b85328587377d5012d0c31f952f14cec4f1b00449770fd73596c |
Hashes for lapx-0.5.5-cp37-cp37m-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 64ae5b29129cf8e895366e0887cec640008ed58fdabdf2b97257e8c9a4adf894 |
|
MD5 | 3c9981e18e37cfe70a0401591e93f89d |
|
BLAKE2b-256 | 8b6b9bd7af9f4da4cac095dca7352210822edbb76532f9ab2504d2483c0f2fb9 |
Hashes for lapx-0.5.5-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dc104eac98c2b79955ed4f12d49d5701fabf38cd247ccdeb217f2406ade916f5 |
|
MD5 | ca05628b58ac34c91c3fc2e07a314201 |
|
BLAKE2b-256 | c62a9e5e3d19023eb229ca1f99f3495bdfc826f73137e4b1de9fe09921bb6a39 |
Hashes for lapx-0.5.5-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bcf9cbf485464972aa6858ddbb09d32db0d7cebcd54ed7965b5576d83d5974da |
|
MD5 | bf11b510928270f9abdb5e5a59e858c8 |
|
BLAKE2b-256 | 4faf9c92b9cfc158f2941905bcc74e8b92629860a88681327c56c2113836cbcb |