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.
- License: BSD-2-Clause, see
LICENSE
- Based source code: lap05-0.5.1.tar.gz
- Credits: @
gatagat
@remram44
Installation: Windows ✅ | Linux ✅ | macOS ✅
-
Install from PyPI:
pip install lapx
-
Or install
.tar.gz
or.whl
from GitHub releases or install from GitHub repo directly:pip install git+https://github.com/rathaROG/lapx.git
-
Or clone and build on your local machine:
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(2, 1), 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.3-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f124dea079a16ef02c0680c4327ec7f47e746829562936eee0fab2b14cb16a13 |
|
MD5 | bbf2d11bb9226286315b0fd5c2b8bbe9 |
|
BLAKE2b-256 | 70c3fd35b4d798e88b3ffd875586d587483124531114c1a732b9cb0709e19d61 |
Hashes for lapx-0.5.3-cp311-cp311-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 83628e63cd9a5e157dea00863346633683009d9886934f0b4113df0484646591 |
|
MD5 | c882e3cb41312d6d69000bf19a233436 |
|
BLAKE2b-256 | 3c16c06315a0b641d9106c064f89235ee2248e38d3e08c43039a2aaacf18a4d2 |
Hashes for lapx-0.5.3-cp311-cp311-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 86531cfb5f42ef9994a153c64b951b4796878ce33861043873e286afacef8dbb |
|
MD5 | b0a04106099e44bc3dd998a02ee5d2a9 |
|
BLAKE2b-256 | 9da262c50278f97f8acfcc17bd2c35634fdf91f8c57bcef9463a6291f31e52f5 |
Hashes for lapx-0.5.3-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 22fce90c603219203ab0635496f08657e470c9b5fa1239749c6106ba291cd510 |
|
MD5 | 62eee0d41ec5f9d2e74905101dbf3764 |
|
BLAKE2b-256 | f48adb31677f325d2be0fea3290ce324a8ce8f727d09f1e63b1e488e6bee75cb |
Hashes for lapx-0.5.3-cp311-cp311-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 16b264169bf776fc95bef807dd5052d11453684bdbe6c2893335f623b8432b71 |
|
MD5 | 2d14439c85a8f2a19d23c995d6b47082 |
|
BLAKE2b-256 | 271cf365f113a64dfd0d613476db25d1e1a958f87cbdcb4670dfffae7781e41f |
Hashes for lapx-0.5.3-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | eb847462431b727e9e5d520fe3ebe48f276ef4b711eae4d7184cfbc08fd5b55f |
|
MD5 | 886c5ff76ccb9f3ed82650310a96cc88 |
|
BLAKE2b-256 | 6665e375981eec2821a1e33b22f4fd21fd2944689b7fcff503d4140e2f9c23bd |
Hashes for lapx-0.5.3-cp310-cp310-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 259585dcf788bf8166304665791555fbe9659584ec154947d864070bdd05d5e0 |
|
MD5 | ac3f1f49e56eacfe0ab2f617d65cdbcb |
|
BLAKE2b-256 | 72e25b0c54366802b0ee29b608cb6cde05e8aff6bf6904d66b615d7e83a99039 |
Hashes for lapx-0.5.3-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 85335fd5ba93fb0c3ab64c9cf1f00af4b5dbe0c1a9cc36a248a2f939fc7a4919 |
|
MD5 | 1265eda5af51b738d710e0723baf50ad |
|
BLAKE2b-256 | c1f96a1c5161da230c950e039c8bc61cc442a91d6b21c18577a88ed132572463 |
Hashes for lapx-0.5.3-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a92337765d9bbdd8dc021b7120e4069843ca82817bded593a66897125f0bc335 |
|
MD5 | 63b8afd0f50d54d5598388ce5313c698 |
|
BLAKE2b-256 | 4d8f8eab5638d31438d28e1db8fcb14e0b97392d2800c43868648f4a5d4a6d4c |
Hashes for lapx-0.5.3-cp310-cp310-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | eb3af8957f1cf0a1b4e9512c77d4ee8b3fcd394e2826f3e7c6e341506a07b3e0 |
|
MD5 | 7cba52034347ad80b3b96e3c7394499a |
|
BLAKE2b-256 | cdad7aea442e3b4cccbbeb909c29228dd6137623ca90539726ec5e1cd2074bdf |
Hashes for lapx-0.5.3-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c354b1932f2279d6216954b41cef258eb9ad7b58772cdb65b07262cbd620e8b0 |
|
MD5 | d824bdfcacaf26b42a5338eae1155eeb |
|
BLAKE2b-256 | 70fd23c2495ced9c151c6695d51a9d68bd73974d1f48d8bbe2519d1ce345c844 |
Hashes for lapx-0.5.3-cp39-cp39-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a09302bf967a673c311ec3fab6fbb35d658f1a2e50ba2c233cb2c5dbb6fe821b |
|
MD5 | 44b04867e83fc2bb02408ade7736b9e9 |
|
BLAKE2b-256 | 899c43471b65c7ae990bc95f2ddff4eae4d0b426f674e720867112fd6fcaa3a6 |
Hashes for lapx-0.5.3-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c8711efc5ebb1d8f3dbf51b74cfea2d669d546bf03135e790aeb2d1863046b45 |
|
MD5 | d3090e25cdb34269a22fcafc92b6799d |
|
BLAKE2b-256 | 46427887451fd35d1eb1068ab1d166b68faf10e5a67b1ece480a309569f32876 |
Hashes for lapx-0.5.3-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | cbd3369a283c2e3fdc24dbb953ad7028e48cf457ba95c9ac24991d4ada940e3f |
|
MD5 | 6a67e660412f2dc9ce4d3d801a08e37f |
|
BLAKE2b-256 | f9fea40bfb888c674d90dd788628b1f7d7f783f26d915659d2f6e8b1870dee14 |
Hashes for lapx-0.5.3-cp39-cp39-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3104c6b5bc65ea16bc59ad6ce35df2bacff41f39c7ff973ef4e8fe5cd9487447 |
|
MD5 | 49ddc026384b9614f3dc85a003c79cdc |
|
BLAKE2b-256 | cca9ecf6cfa61d7bb22627bcde02d2883e98e87bdfb29d78bb17bbbedbb89889 |
Hashes for lapx-0.5.3-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1b8f67dbef9a4553ea4ac9fd03b6bbefe018dee3d48707fe4e7a2017b5806db3 |
|
MD5 | 3789e08adec9cfac1a274d3d5fcc8502 |
|
BLAKE2b-256 | b2e8e62919cdde0f9547f2a9ad664e743a94a9510b17080c333dc69a0b37f0ae |
Hashes for lapx-0.5.3-cp38-cp38-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2a9128773d9131ea3c1cda5bb8e542d1b1b1cb421fca794e28cad1843ace8856 |
|
MD5 | 225e0f67be33ff3e8af0eff539cf9f1f |
|
BLAKE2b-256 | ed5624afd37e0a3f001b9a169ebee5ad62e2604e502eab393b35121e387e6072 |
Hashes for lapx-0.5.3-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 266931a5d0c6ee2337e868474983c353a7f27f371fdaee586edab28cb1fd63e2 |
|
MD5 | cd07a3bf3b7bdcc94284e0c2422abacc |
|
BLAKE2b-256 | e3e59e188a3a4cbb91e07bc54e5658fd57024b80b478fa4a0ceafd551e0f7237 |
Hashes for lapx-0.5.3-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 42b0813d022bfa60910cbbca8d4ef1b7e699577506134f6ce4a69a6510ebc834 |
|
MD5 | 0c5fdb21112514892c2aed1ecdee21d5 |
|
BLAKE2b-256 | eb37c77a9ad44172dbb7765f450f98847e4b4a2fed61044ecee752704b549a7c |
Hashes for lapx-0.5.3-cp38-cp38-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ccd49c1ea76870f66b49c6872ef85e7d367a4df4484ed001f8c4b5c950a6394f |
|
MD5 | 7991d978080baeae0031743e31065efa |
|
BLAKE2b-256 | 7d513b22d1dfeb6944adaaa1b5bb2348d039448f1d9910065e0a1406cc2e0261 |
Hashes for lapx-0.5.3-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4cf7ff0e0b6cea1cb37f9e59d2070e219eb16d7229a466fec487b2ff6256953a |
|
MD5 | 9bafe7696834562198e5dea1ff420b87 |
|
BLAKE2b-256 | 08f774abba832cd5db2e72f7bb84cc4c3e9c3a8ff45e00f8df95e8992b6fbde1 |
Hashes for lapx-0.5.3-cp37-cp37m-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e811a5f0ca2cda50d685f85314e696986520c511051770ac8d383e2566f2d5d1 |
|
MD5 | 649e29f3a86fb9e6cd49c79d2d13392e |
|
BLAKE2b-256 | 38c5d690c4b0b2a5ea8c0d7b87b998f20d157f54cdf3c66ddbc667596652cbda |
Hashes for lapx-0.5.3-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b790cde6ec0a222d86d7dcf02ddac14cea1fb7ef39ea01c6c7f10f603b74150b |
|
MD5 | 566da49c7c797f010716cdf31d20a72f |
|
BLAKE2b-256 | 14446c24e9ad0dc49b8092af3469ff335d88104a14f0efb4b8ae8c42b7744357 |
Hashes for lapx-0.5.3-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3cacea27dc7bf070a81cfd3a2bc25acd208ad24793ebfabce5a7ed6daecd2ffc |
|
MD5 | 5737cd8358aa54dd2f57fc5b3c29bdfb |
|
BLAKE2b-256 | 54f771dd4fd60d5b949bd162371eb2222209de189d35dd1b7a973ac88d1422d7 |