Linear Assignment Problem solver (LAPJV/LAPMOD).

Navigation

Verified details

These details have been verified by PyPI
Project links
GitHub Statistics
Maintainers
Avatar for tomash from gravatar.com tomash

Unverified details

These details have not been verified by PyPI
Meta
  • License: BSD License (BSD-2-Clause)
  • Author: gatagat, rathaROG, and co.
  • Tags Linear Assignment, LAPJV, LAPMOD, lap, lapx
  • Requires: Python >=3.7
Classifiers

Project description

Test Simple Benchmark Test PyPI Build Publish to PyPI

lap: Linear Assignment Problem Solver

lap is a linear assignment problem solver using Jonker-Volgenant algorithm for dense LAPJV¹ or sparse LAPMOD² matrices. Both algorithms are implemented from scratch based solely on the papers¹˒² and the public domain Pascal implementation provided by A. Volgenant³. 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.

¹ R. Jonker and A. Volgenant, "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems", Computing 38, 325-340 (1987)
² A. Volgenant, "Linear and Semi-Assignment Problems: A Core Oriented Approach", Computer Ops Res. 23, 917-932 (1996)
³ http://www.assignmentproblems.com/LAPJV.htm | [archive.org]

💽 Installation

Install from PyPI:

PyPI version Downloads Downloads

pip install lap
Pre-built Wheels 🛞 Windows ✅ Linux ✅ macOS ✅
Python 3.7 AMD64 x86_64/aarch64 x86_64
Python 3.8 AMD64 x86_64/aarch64 x86_64/arm64
Python 3.9-3.13 ¹ AMD64/ARM64 ² x86_64/aarch64 x86_64/arm64

¹ v0.5.10 supports numpy v2.x for Python 3.9-3.13. 🆕
² Windows ARM64 is experimental.

Other options

Install from GitHub repo (requires C++ compiler):

pip install git+https://github.com/gatagat/lap.git

Build and install (requires C++ compiler):

git clone https://github.com/gatagat/lap.git
cd lap
pip install "setuptools>=67.8.0"
pip install wheel build
python -m build --wheel
cd dist

🧪 Usage

import lap
import numpy as np
print(lap.lapjv(np.random.rand(4, 5), extend_cost=True))
More details

cost, x, y = lap.lapjv(C)

The function lapjv(C) returns the assignment cost cost and two arrays x and y. If cost matrix C has shape NxM, then x is a size-N array specifying to which column each 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)]

License

Released under the 2-clause BSD license, see LICENSE.

Copyright (C) 2012-2024, Tomas Kazmar

Contributors (in alphabetic order):

  • Benjamin Eysenbach
  • Léo Duret
  • Raphael Reme
  • Ratha Siv
  • Robert Wen
  • Steven
  • Tom White
  • Tomas Kazmar
  • Wok

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page