Project: lapx

Linear Assignment Problem solver (LAPJV/LAPMOD).

Project Details

Latest version
0.5.5
Home Page
https://github.com/rathaROG/lapx
PyPI Page
https://pypi.org/project/lapx/

Project Popularity

PageRank
0.0021610239600416913
Number of downloads
75635

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: 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, 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)]