lap

Linear Assignment Problem solver (LAPJV/LAPMOD).

https://github.com/gatagat/lap

Last synced: 11 months ago · JSON representation

Repository

Linear Assignment Problem solver (LAPJV/LAPMOD).

Basic Info

Host: GitHub
Owner: gatagat
License: bsd-2-clause
Language: Python
Default Branch: master
Homepage:
Size: 1.65 MB

Statistics

Stars: 236
Watchers: 6
Forks: 69
Open Issues: 12
Releases: 0

Created over 10 years ago · Last pushed over 1 year ago

Metadata Files

Readme License

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:

pip install lap

^{¹ v0.5.12 supports both numpy 1.x and 2.x for Python 3.8-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`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html) and lapsolver's [`solve dense`](https://github.com/cheind/py-lapsolver)). 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.

Contributors (in alphabetic order): - Benjamin Eysenbach - Léo Duret - Pieter Lenaerts - Raphael Reme - Ratha Siv - Robert Wen - Steven - Tom White - Tomas Kazmar - Wok

Owner

Name: Tomas Kazmar
Login: gatagat
Kind: user
Location: Vienna, AT

Repositories: 9
Profile: https://github.com/gatagat

GitHub Events

Total

Issues event: 19
Watch event: 24
Delete event: 1
Member event: 1
Issue comment event: 47
Push event: 10
Pull request event: 14
Fork event: 5
Create event: 4

Last Year

Issues event: 19
Watch event: 24
Delete event: 1
Member event: 1
Issue comment event: 47
Push event: 10
Pull request event: 14
Fork event: 5
Create event: 4

Committers

Last synced: over 2 years ago

All Time

Total Commits: 85
Total Committers: 5
Avg Commits per committer: 17.0
Development Distribution Score (DDS): 0.059

Past Year

Commits: 0
Committers: 0
Avg Commits per committer: 0.0
Development Distribution Score (DDS): 0.0

Top Committers

Name	Email	Commits
Tomas Kazmar	t**r@s**z	80
jenhaoyang	r**2@g**m	2
Tom White	t**m@s**m	1
Benjamin Eysenbach	e**h@g**m	1
Robert Wen	r**n@c**m	1

Committer Domains (Top 20 + Academic)

clarifai.com: 1 google.com: 1 sixdozen.com: 1 seznam.cz: 1

Issues and Pull Requests

Last synced: 11 months ago

All Time

Total issues: 43
Total pull requests: 24
Average time to close issues: about 1 year
Average time to close pull requests: 5 months
Total issue authors: 36
Total pull request authors: 18
Average comments per issue: 4.16
Average comments per pull request: 0.79
Merged pull requests: 10
Bot issues: 0
Bot pull requests: 0

Past Year

Issues: 1
Pull requests: 7
Average time to close issues: 1 day
Average time to close pull requests: 6 days
Issue authors: 1
Pull request authors: 4
Average comments per issue: 4.0
Average comments per pull request: 0.57
Merged pull requests: 3
Bot issues: 0
Bot pull requests: 0

View more stats

Top Authors

Issue Authors

gatagat (6)
truongkhaihoa1995 (2)
Bram94 (2)
jvlmdr (2)
drimyus (1)
dribnet (1)
emanuele (1)
rathaROG (1)
dohieunghia2002 (1)
kiufta (1)
cheind (1)
remram44 (1)
xcTorres (1)
therc (1)
liu-mengyang (1)

Pull Request Authors

gatagat (6)
troycarlson (2)
tlambert03 (2)
jenhaoyang (2)
johnnynunez (2)
vlad-nn (2)
ExDrag0n (2)
cshimmin (2)
assafmus (2)
plenaerts (1)
jvlmdr (1)
dribnet (1)
brunolnetto (1)
ben-eysenbach (1)
timwroge (1)

Top Labels

Issue Labels

enhancement (2)

Pull Request Labels

Packages

Total packages: 7
Total downloads:
- pypi 340,358 last-month
Total docker downloads: 7,990

Total dependent packages: 22
(may contain duplicates)
Total dependent repositories: 676
(may contain duplicates)
Total versions: 11
Total maintainers: 6

pypi.org: lap

Linear Assignment Problem solver (LAPJV/LAPMOD).

Homepage: https://github.com/gatagat/lap
Documentation: https://lap.readthedocs.io/
License: BSD-2-Clause
Latest release: 0.5.12
published over 1 year ago

Versions: 3
Dependent Packages: 21
Dependent Repositories: 673
Downloads: 340,229 Last month
Docker Downloads: 7,990

Rankings

Dependent repos count: 0.5%

Dependent packages count: 0.6%

Downloads: 0.6%

Docker downloads count: 1.5%

Average: 2.3%

Stargazers count: 5.3%

Forks count: 5.5%

Maintainers (1)

tomash

Last synced: 11 months ago

pypi.org: lap05

Linear Assignment Problem solver (LAPJV/LAPMOD).

Homepage: https://github.com/gatagat/lap
Documentation: https://lap05.readthedocs.io/
License: BSD (2-clause)
Latest release: 0.5.1
published over 4 years ago

Versions: 2
Dependent Packages: 0
Dependent Repositories: 1
Downloads: 43 Last month

Rankings

Stargazers count: 5.3%

Forks count: 5.5%

Downloads: 6.5%

Average: 9.8%

Dependent packages count: 10.0%

Dependent repos count: 21.8%

Maintainers (2)

remram tinaksite

Last synced: 11 months ago

alpine-edge: py3-lap

Linear Assignment Problem solver (LAPJV/LAPMOD)

Homepage: https://github.com/gatagat/lap
License: BSD-2-Clause
Latest release: 0.5.12-r0
published about 1 year ago

Versions: 1
Dependent Packages: 0
Dependent Repositories: 0

Rankings

Dependent repos count: 0.0%

Average: 11.2%

Dependent packages count: 13.6%

Forks count: 14.3%

Stargazers count: 16.8%

Maintainers (1)

soeren+alpine@soeren-tempel.net

Last synced: 11 months ago

pypi.org: lap-sdist

Linear Assignment Problem solver (LAPJV/LAPMOD).

Homepage: https://github.com/gatagat/lap
Documentation: https://lap-sdist.readthedocs.io/
License: BSD (2-clause)
Latest release: 0.5.dev0
published about 3 years ago

Versions: 1
Dependent Packages: 0
Dependent Repositories: 1
Downloads: 86 Last month

Rankings

Stargazers count: 5.3%

Forks count: 5.5%

Dependent packages count: 10.0%

Average: 12.6%

Downloads: 20.3%

Dependent repos count: 21.8%

Maintainers (1)

sr99622

Last synced: 11 months ago

spack.io: py-lap

lap is a linear assignment problem solver using Jonker-Volgenant algorithm for dense (LAPJV) or sparse (LAPMOD) matrices.

Homepage: https://github.com/gatagat/lap
License: []
Latest release: 0.4.0
published over 4 years ago

Versions: 1
Dependent Packages: 0
Dependent Repositories: 0

Rankings

Dependent repos count: 0.0%

Stargazers count: 15.8%

Forks count: 16.0%

Average: 22.3%

Dependent packages count: 57.3%

Maintainers (1)

adamjstewart

Last synced: 11 months ago

conda-forge.org: lap

Homepage: https://github.com/gatagat/lap
License: BSD-2-Clause
Latest release: 0.4.0
published over 6 years ago

Versions: 2
Dependent Packages: 1
Dependent Repositories: 1

Rankings

Dependent repos count: 24.3%

Forks count: 26.5%

Average: 27.2%

Dependent packages count: 29.0%

Stargazers count: 29.1%

Last synced: 11 months ago

alpine-v3.22: py3-lap

Linear Assignment Problem solver (LAPJV/LAPMOD)

Homepage: https://github.com/gatagat/lap
License: BSD-2-Clause
Latest release: 0.5.12-r0
published about 1 year ago

Versions: 1
Dependent Packages: 0
Dependent Repositories: 0

Rankings

Dependent repos count: 0.0%

Dependent packages count: 0.0%

Average: 100%

Maintainers (1)

soeren+alpine@soeren-tempel.net

Last synced: 11 months ago

lap

Science Score: 13.0%

Repository

Basic Info

Statistics

Metadata Files

README.md

lap: Linear Assignment Problem Solver

💽 Installation

Install from PyPI:

🧪 Usage

License

Owner

GitHub Events

Total

Last Year

Committers

All Time

Past Year

Top Committers

Committer Domains (Top 20 + Academic)

Issues and Pull Requests

All Time

Past Year

Top Authors

Issue Authors

Pull Request Authors

Top Labels

Issue Labels

Pull Request Labels

Packages

pypi.org: lap

Rankings

Maintainers (1)

pypi.org: lap05

Rankings

Maintainers (2)

alpine-edge: py3-lap

Rankings

Maintainers (1)

pypi.org: lap-sdist

Rankings

Maintainers (1)

spack.io: py-lap

Rankings

Maintainers (1)

conda-forge.org: lap

Rankings

alpine-v3.22: py3-lap

Rankings

Maintainers (1)