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.
- Based on: [ed04ab7752]
- License: BSD-2-Clause, see
LICENSE
@gatagat
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(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.4-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bac3ba3544ed27a7827d56bddd88e2c36d723b6020c7c64847e457b6b4ba03e1 |
|
MD5 | 6ed4dca5bc95669883e8c479797355bf |
|
BLAKE2b-256 | 5bed08b00cb070f654ac2ed3ae365805be66870b424b75b06c46ef1ade940156 |
Hashes for lapx-0.5.4-cp311-cp311-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2e18fb041e0d0dbed688e0dd720e87ddaf8ad7669b8f3103297ab13da0aecdf0 |
|
MD5 | ed89a45bfaec4e217f4f9a964c4f24f2 |
|
BLAKE2b-256 | e4dbf1a96340e97e95ea5e0c814d4bad368e4f27c7713e04d8dc4e9871740fb6 |
Hashes for lapx-0.5.4-cp311-cp311-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e60e32cdcb21c4a47768d7e77f8d4b41772fce068fcbf1ce70ae90c2003b7f5d |
|
MD5 | 5fff08505397fd0f7c835e0d0d71733b |
|
BLAKE2b-256 | c16f448d9b8cd7d7210a37e32a55105555b531eaff5d0d3ae115a4922e810616 |
Hashes for lapx-0.5.4-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 14afce31e2efbc9e3bdafdef95641f7beed20ed8f4085b3c46ed7acaa31f6f72 |
|
MD5 | 095c41ebfc3c604eae46eca35957226d |
|
BLAKE2b-256 | b3193fa7eb580474bc0ea06020ee99e60ef4bde459b72c89cf13dd31b54b8b26 |
Hashes for lapx-0.5.4-cp311-cp311-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7e4d65a13897e8a2a9b52ec5369bed1fea0a6c45ded2810f0557a63875c36130 |
|
MD5 | 22b1a31935375fa43573bd04d3ca2e0e |
|
BLAKE2b-256 | 21f65404cdcf23317e3e88daea32c6a09e4da497abe23a661a4e196172a4dd00 |
Hashes for lapx-0.5.4-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0b989b329c81e3c4fc96d6989e4d3d3d30b9d4af6cfd8cf986462108cd56559d |
|
MD5 | 71145a46906c80ce48b5b608c628b5ce |
|
BLAKE2b-256 | 6c50eef4f4ebb9f3d2f13169c8cbb6f30675df2a67a56dfc328c7c2846dc4c07 |
Hashes for lapx-0.5.4-cp310-cp310-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ca2519400991724f0bc5e8aa1d8e5f4f543041042abac25ad057eac2a883a998 |
|
MD5 | 51f41cc9a71deb2ba5267ddf55d45a97 |
|
BLAKE2b-256 | 7184b9338f89d96aef3b7379f27f92d49353cc7c58496bd27fb77d36e0910077 |
Hashes for lapx-0.5.4-cp310-cp310-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 76c549a53f619b7c8a41824eb6d420e67380f48f6baa96481fdec7229f4cc007 |
|
MD5 | 92bb9e2e8164cd2f142ed3077971bead |
|
BLAKE2b-256 | 0788af367939455f771f13cd09db5c7d08b8a2e71ebd02753e9812fc2cbef9bf |
Hashes for lapx-0.5.4-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f5aaaf26710f39499a392ad9c714dcdbfded4a30694182212532e2f4efc0180e |
|
MD5 | 3c13854ede2dccda51a74d37d2438545 |
|
BLAKE2b-256 | d96ae9dab7ae286d402c8124a09f692956630a32ad29942cfb841d121331314e |
Hashes for lapx-0.5.4-cp310-cp310-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 305cbfd64ee2fa2ecd16d9032f0b503d2299c93752e0e2f64d8bcdcf5a190b72 |
|
MD5 | ac34cc8f4c3ecd6409a66a405be72a08 |
|
BLAKE2b-256 | 0e808c28ea4c3f61c8f0742ae6fcd7046cd06afb436778575aea6da3f03793ac |
Hashes for lapx-0.5.4-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9229fd56e9b00aeba6b925367e4b453d18ad47899b11e5822f0166947a3c4696 |
|
MD5 | be080ee9f95edda2c92c02932b1024af |
|
BLAKE2b-256 | f6d4b6c71094b175f675f366c7059f2bc013ca28bec82fc86023a26307020f85 |
Hashes for lapx-0.5.4-cp39-cp39-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fe81dc9d1ec4d7a928dc056ec281d49ddd987ce0d67346031a25bc494cf1281a |
|
MD5 | eedc57a757fe09b7bec88c4412203986 |
|
BLAKE2b-256 | 7bf740decebe2bfc6a57138922b7c50a0e18c7c14db7a2bd9c03d5174eec79fe |
Hashes for lapx-0.5.4-cp39-cp39-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ddd4a09b42659d4b08d8db694d92174f2ba3bb023813f6b863effe891e97acbe |
|
MD5 | 9be20feb0087559c62112166878296e6 |
|
BLAKE2b-256 | 680693af39dff37a54ab7884cf491b9158ddca2f7fa353bd58d674e4b8a28b77 |
Hashes for lapx-0.5.4-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 895f90375fdcde3cfc03b73225c7a8b323f442f853ccb4dda627d39504ff75ae |
|
MD5 | 68212a6177c3c3a4d10de8c5fe933377 |
|
BLAKE2b-256 | 9175f0eed55755b5abee1670b446468af33782370e3d9704516fd5371ecf8900 |
Hashes for lapx-0.5.4-cp39-cp39-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b7291c207f03b491906cf9fa8b2c2fddae188c329c31e54782aa1166aa0dd7cc |
|
MD5 | fc221dc0edda6d323118c8b989c9a048 |
|
BLAKE2b-256 | a2cb48c12b62eaf5d7e104ab3ac18cdc36f4ec5871cb42b57779b788aa1e3cba |
Hashes for lapx-0.5.4-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fbe7464c0043bca666ba59fc3e9e4bef63f776de61ae76ad01ba68290c623384 |
|
MD5 | a7c7fb630dc026b5ffc945b40aa982b3 |
|
BLAKE2b-256 | 54ff7d0fb1da9af27291e6abcafdf1b63487af3544cf5a5b3f00ebac3dfbe357 |
Hashes for lapx-0.5.4-cp38-cp38-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a8eb1df4db52f7564de920df49f174b2da00f611fe27229b380e7eab4b659140 |
|
MD5 | cf0c2a1cff1ccaf31802f83194903439 |
|
BLAKE2b-256 | b89cf6bbed1248c58452aecbdefeab353c0dab39f2c8707e4d621d1956be2ce7 |
Hashes for lapx-0.5.4-cp38-cp38-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f9f33a820b8e9ff5030742d83936cfa9b5557ddc491d414b3c4659b772b0ea55 |
|
MD5 | b6d50cc6a337771360d0da11e5fd97fb |
|
BLAKE2b-256 | 465d9d43bfa248c86d4654b123edb8c1e4703fa54a79dd98aa069bd5d057639c |
Hashes for lapx-0.5.4-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3935a6d4a518d24c8cb17eb79865c03a9205f64c3dd6484f4c84d2ef38966e3e |
|
MD5 | 88c4b551ba696b7046ddeb3488b595db |
|
BLAKE2b-256 | c6c3a05cb641cc6ded2fea1fb00783994bfb5bb6b94b996b7a2c0537ceca9e57 |
Hashes for lapx-0.5.4-cp38-cp38-macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f1227e850e6c7fd454af9a3af7a6866997ddb797bad65fd55df30024397842a1 |
|
MD5 | 5301c624eb8de2e9c6270a5411fbfc9e |
|
BLAKE2b-256 | 6eb10946aaca5006349422a084fec0fae8f9dc6cf9b7e27f621156908c2cdbf3 |
Hashes for lapx-0.5.4-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e09a5890f515b7f5f623d70f370462aa9acf8130fc9d913207d6fcd503208b24 |
|
MD5 | 8892b723ebf0586801d2ab3f5654f6f9 |
|
BLAKE2b-256 | 1184d7eae99d5f5fcd15bd4fec2baed30ac0d7585c2ad03384dac2f2c1d4309f |
Hashes for lapx-0.5.4-cp37-cp37m-musllinux_1_1_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c8270e216f0b9043512f6b5c1ff22629aef8acfedb8a8a0ff5177006645dcffa |
|
MD5 | 6cf2d023cc22a7bb431ebc8105a9d4c1 |
|
BLAKE2b-256 | fd4302c6fdb453320b39fd0650237958aafbb34dd84bc0347d25fc7d1f748b3c |
Hashes for lapx-0.5.4-cp37-cp37m-manylinux_2_5_x86_64.manylinux1_x86_64.manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7ebf503c5f83d6ed7586d1c920dacf5815f40d11843bd0211ee018c99d206750 |
|
MD5 | 41b78c37767dbc552c77200c0ef53020 |
|
BLAKE2b-256 | 9f3f7856ad4dd8fffa10598e1628c986c37f1f17b4e8f4a485323e206511979a |
Hashes for lapx-0.5.4-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8ba718dbb5320a461efbffaf60a5c5aa7a08248518b449ebbf353fcfd389e5cc |
|
MD5 | beed2e2f8a04cf773578a944d9da9f9c |
|
BLAKE2b-256 | 6c900f6397f67aa65008f3149ae5744f3a8fc5e6330bd2564a2336126f8d72e8 |