lapsolver
Fast linear assignment problem (LAP) solvers for Python based on c-extensions
Science Score: 23.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
○CITATION.cff file
-
✓codemeta.json file
Found codemeta.json file -
○.zenodo.json file
-
○DOI references
-
○Academic publication links
-
✓Committers with academic emails
1 of 6 committers (16.7%) from academic institutions -
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (10.5%) to scientific vocabulary
Keywords
Repository
Fast linear assignment problem (LAP) solvers for Python based on c-extensions
Basic Info
Statistics
- Stars: 160
- Watchers: 3
- Forks: 26
- Open Issues: 3
- Releases: 0
Topics
Metadata Files
ReadMe.md
py-lapsolver
py-lapsolver implements a Linear sum Assignment Problem (LAP) solver for dense matrices based on shortest path augmentation in Python. In practice, it solves 5000x5000 problems in around 3 seconds.
Install
pip install [--pre] lapsolver
Windows binary wheels are provided for Python 3.5/3.6. Source wheels otherwise.
Install from source
Clone this repository
git clone --recursive https://github.com/cheind/py-lapsolver.git
Then build the project and exectute tests
python setup.py develop
python setup.py test
Executing the tests requires pytest and optionally pytest-benchmark for generating benchmarks.
Usage
```python import numpy as np from lapsolver import solve_dense
costs = np.array([ [6, 9, 1], [10, 3, 2], [8, 7, 4.] ], dtype=np.float32)
rids, cids = solve_dense(costs)
for r,c in zip(rids, cids): print(r,c) # Row/column pairings """ 0 2 1 1 2 0 """ ```
You may also want to mark certain pairings impossible
```python
Matrix with non-allowed pairings
costs = np.array([ [5, 9, np.nan], [10, np.nan, 2], [8, 7, 4.]] )
rids, cids = solve_dense(costs)
for r,c in zip(rids, cids): print(r,c) # Row/column pairings """ 0 0 1 2 2 1 """ ```
Benchmarks
Comparisons below are generated by scripts in ./lapsolver/benchmarks.
Currently, the following solvers are tested
- lapjv - https://github.com/gatagat/lap
- munkres - http://software.clapper.org/munkres/
- ortools - https://github.com/google/or-tools **
- scipy - https://github.com/scipy/scipy/tree/master/scipy
- lapsolver - this project
**reduced performance due to costly dense matrix to graph conversion. If you know a better way, please let me know.
Please note that the x-axis is scaled logarithmically. Missing bars indicate excessive runtime or errors in returned result.
Additional Benchmarks
Berhane performs an in depth analysis of Python3 linear assignment problem solver at https://github.com/berhane/LAP-solvers
References
py-lapsolver heavily relies on code published by @jaehyunp at https://github.com/jaehyunp/
Owner
- Name: Christoph Heindl
- Login: cheind
- Kind: user
- Location: Austrian area
- Website: https://cheind.github.io/
- Repositories: 88
- Profile: https://github.com/cheind
I am a computer scientist working at the interface of perception, robotics and deep learning.
GitHub Events
Total
- Issues event: 6
- Watch event: 3
- Issue comment event: 8
- Push event: 3
- Fork event: 2
Last Year
- Issues event: 6
- Watch event: 3
- Issue comment event: 8
- Push event: 3
- Fork event: 2
Committers
Last synced: 9 months ago
Top Committers
| Name | Commits | |
|---|---|---|
| Christoph Heindl | c****l@g****m | 76 |
| Heindl Christoph | c****d@p****t | 7 |
| Jack Valmadre | j****r | 2 |
| Jack Valmadre | v****e@g****m | 2 |
| maleicacid | 4****4 | 1 |
| Kyle M. Tarplee | k****e@a****u | 1 |
Committer Domains (Top 20 + Academic)
Issues and Pull Requests
Last synced: 6 months ago
All Time
- Total issues: 16
- Total pull requests: 7
- Average time to close issues: over 1 year
- Average time to close pull requests: 7 months
- Total issue authors: 13
- Total pull request authors: 5
- Average comments per issue: 2.19
- Average comments per pull request: 2.43
- Merged pull requests: 5
- Bot issues: 0
- Bot pull requests: 0
Past Year
- Issues: 2
- Pull requests: 0
- Average time to close issues: about 1 month
- Average time to close pull requests: N/A
- Issue authors: 2
- Pull request authors: 0
- Average comments per issue: 1.5
- Average comments per pull request: 0
- Merged pull requests: 0
- Bot issues: 0
- Bot pull requests: 0
Top Authors
Issue Authors
- cheind (3)
- guoyangqin (2)
- AlphonsG (1)
- YanielCarreno (1)
- rwolst (1)
- AxlJ (1)
- JohnPekl (1)
- cbm755 (1)
- WMXJY (1)
- aminaghoul (1)
- ktarplee (1)
- Multihuntr (1)
- boguszjelinski (1)
Pull Request Authors
- jvlmdr (3)
- cbm755 (1)
- ktarplee (1)
- qingswu (1)
- kazuki0824 (1)
Top Labels
Issue Labels
Pull Request Labels
Packages
- Total packages: 1
-
Total downloads:
- pypi 1,234 last-month
- Total dependent packages: 5
- Total dependent repositories: 41
- Total versions: 3
- Total maintainers: 1
pypi.org: lapsolver
Fast linear assignment problem solvers
- Homepage: https://github.com/cheind/py-lapsolver
- Documentation: https://lapsolver.readthedocs.io/
- License: MIT
-
Latest release: 1.1.0
published about 6 years ago