Linear sum assignment problem solver using JonkerVolgenant algorithm.
Project description
Linear Assignment Problem solver using JonkerVolgenant algorithm
This project is the rewrite of pyLAPJV which supports Python 3 and updates the core code. The performance is twice as high as the original thanks to the optimization of the augmenting row reduction phase using Intel AVX2 intrinsics. It is a native Python 3 module and does not work with Python 2.x, stick to pyLAPJV otherwise.
Linear assignment problem is the bijection between two sets with equal cardinality which optimizes the sum of the individual mapping costs taken from the fixed cost matrix. It naturally arises e.g. when we want to fit tSNE results into a rectangular regular grid. See this awesome notebook for the details about why LAP matters: CloudToGrid.
JonkerVolgenant algorithm is described in the paper:
R. Jonker and A. Volgenant, "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems," Computing, vol. 38, pp. 325340, 1987.
This paper is not publicly available though a brief description exists on sciencedirect.com. JV is faster in than the Hungarian algorithm in practice, though the complexity is the same  O(n^{3}).
The C++ source of the algorithm comes from http://www.magiclogic.com/assignment.html It has been reworked and partially optimized with OpenMP 4.0 SIMD.
Installing
pip3 install lapjv
Tested on Linux and macOS.
Usage
Refer to test.py for the complete code.
from lapjv import lapjv
row_ind, col_ind, _ = lapjv(cost_matrix)
The assignment matrix by row is row_ind
: the value at nth place is the assigned column index to the nth row.
col_ind
is the reverse of row_ind
: mapping from columns to row indexes.
Note: a bijection is only possible for sets with equal cardinality. If you need to map A vectors to B vectors, derive the square symmetric (A+B) x (A+B) matrix: take the first A rows and columns from A and the remaining [A..A+B] rows and columns from B. Set the A>A and B>B costs to some maximum distance value, big enough so that you don't see assignment errors.
Illegal instruction
This error appears if your CPU does not support the AVX2 instruction set. We do not ship builds for different CPUs so you need to build the package yourself:
pip3 install git+https://github.com/srcd/lapjv
NANs
NANs in the cost matrix lead to completely undefined result. It is the caller's responsibility to check them.
License
MIT Licensed,see LICENSE
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.
Filename, size  File type  Python version  Upload date  Hashes 

Filename, size lapjv1.3.14cp38cp38manylinux_2_24_x86_64.whl (147.7 kB)  File type Wheel  Python version cp38  Upload date  Hashes View 
Filename, size lapjv1.3.14.tar.gz (10.3 kB)  File type Source  Python version None  Upload date  Hashes View 
Hashes for lapjv1.3.14cp38cp38manylinux_2_24_x86_64.whl
Algorithm  Hash digest  

SHA256  20ee320bf2de1122e825f02976cb76c2f755026f4d7cbfa904fe31146085f9dd 

MD5  fd103bef2de832a396a27a89a219d505 

BLAKE2256  4ad9238e4c180d4b64138008533513c798aa7d16dfe387ff972ff03bb0a78ea9 