cheind / py-lapsolver Goto Github PK

Fast linear assignment problem (LAP) solvers for Python based on c-extensions

License: MIT License

CMake 1.01% Python 62.85% C++ 36.14%

py-lapsolver's Introduction

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

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

# 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/

py-lapsolver's People

Contributors

Stargazers

Watchers

py-lapsolver's Issues

Installation trouble

Hi there,

I just wondering if you have tested the package using python 2.7. I got an error when I am installing it.

Regards;

Yaniel

Found run times vary drastically for different distance matrices with same sizes.

As the author put it, this algorithm is much faster. For a randomly generated 3000x3000 cost matrix, it'll take a fraction of seconds to solve.

N_a = 3000
N_b = 3000

# Random costs
dist_mat_rand = np.random.uniform(0, 400, (N_a, N_b))

start_time = time.time()
ind_1, ind_2 = solve_dense(dist_mat_rand)
print(time.time() - start_time)

0.8244 sec

However, when it comes to a distance matrix between two sets of points, the run time increases drastically, the same sizes though.

# Manhattan distance bipartite matching
loc_a = np.random.uniform(0, 100, (N_a, 2))
loc_b = np.random.uniform(0, 200, (N_b, 2))
dist_mat = get_dist_mat(loc_a, loc_b)

start_time = time.time()
ind_1, ind_2 = solve_dense(dist_mat)
print(time.time() - start_time)

30.2019 sec

If adding the above two matrix, the run time will be between the two above.

start_time = time.time()
ind_1, ind_2 = solve_dense(dist_mat+dist_mat_rand)
print(time.time() - start_time)

17.5623 sec

The only difference I can think of the two distance matrices is whether they have correlations. Was wondering why the run times are so hugely different?

Error during installation

Hi, I get the following error installing the project on MacOS :
axelpro:heetch_simulator $ pip install lapsolver
[...]
[ 50%] Building CXX object CMakeFiles/lapsolverc.dir/src/lapsolverc.cpp.o
clang: error: no such file or directory: 'NOTFOUND'
make[2]: *** [CMakeFiles/lapsolverc.dir/src/lapsolverc.cpp.o] Error 1
make[1]: *** [CMakeFiles/lapsolverc.dir/all] Error 2
make: *** [all] Error 2
Traceback (most recent call last):
File "", line 1, in
File "/private/var/folders/4p/jw6zpctd6sqd6hb7j_mz8fsh0000gp/T/pip-install-jsd4kq_g/lapsolver/setup.py", line 88, in
keywords='hungarian munkres kuhn linear-sum-assignment bipartite-graph lap'
File "/anaconda3/envs/simu/lib/python3.6/site-packages/setuptools/init.py", line 129, in setup
return distutils.core.setup(**attrs)
File "/anaconda3/envs/simu/lib/python3.6/distutils/core.py", line 148, in setup
dist.run_commands()
File "/anaconda3/envs/simu/lib/python3.6/distutils/dist.py", line 955, in run_commands
self.run_command(cmd)
File "/anaconda3/envs/simu/lib/python3.6/distutils/dist.py", line 974, in run_command
cmd_obj.run()
File "/anaconda3/envs/simu/lib/python3.6/site-packages/setuptools/command/install.py", line 61, in run
return orig.install.run(self)
File "/anaconda3/envs/simu/lib/python3.6/distutils/command/install.py", line 545, in run
self.run_command('build')
File "/anaconda3/envs/simu/lib/python3.6/distutils/cmd.py", line 313, in run_command
self.distribution.run_command(command)
File "/anaconda3/envs/simu/lib/python3.6/distutils/dist.py", line 974, in run_command
cmd_obj.run()
File "/anaconda3/envs/simu/lib/python3.6/distutils/command/build.py", line 135, in run
self.run_command(cmd_name)
File "/anaconda3/envs/simu/lib/python3.6/distutils/cmd.py", line 313, in run_command
self.distribution.run_command(command)
File "/anaconda3/envs/simu/lib/python3.6/distutils/dist.py", line 974, in run_command
cmd_obj.run()
File "/private/var/folders/4p/jw6zpctd6sqd6hb7j_mz8fsh0000gp/T/pip-install-jsd4kq_g/lapsolver/setup.py", line 33, in run
self.build_extension(ext)
File "/private/var/folders/4p/jw6zpctd6sqd6hb7j_mz8fsh0000gp/T/pip-install-jsd4kq_g/lapsolver/setup.py", line 58, in build_extension
subprocess.check_call(['cmake', '--build', '.'] + build_args, cwd=self.build_temp)
File "/anaconda3/envs/simu/lib/python3.6/subprocess.py", line 291, in check_call
raise CalledProcessError(retcode, cmd)
subprocess.CalledProcessError: Command '['cmake', '--build', '.', '--config', 'Release', '--', '-j2']' returned non-zero exit status 2.

possible built failures on Python 3.11?

Upcoming Fedora 37 has Python 3.11rc2 right now. I tried to install lapsolver with pip. There was no .whl (but maybe this is normal for pre-release, I'm not expert on Python packaging!).

Instead it tries to use the .tar.gz and fails:

pip install lapsolver
Defaulting to user installation because normal site-packages is not writeable
Collecting lapsolver
  Using cached lapsolver-1.1.0.tar.gz (261 kB)
  Preparing metadata (setup.py) ... done
Installing collected packages: lapsolver
  DEPRECATION: lapsolver is being installed using the legacy 'setup.py install' method, because it does not have a 'pyproject.toml' and the 'wheel' package is not installed. pip 23.1 will enforce this behaviour change. A possible replacement is to enable the '--use-pep517' option. Discussion can be found at https://github.com/pypa/pip/issues/8559
  Running setup.py install for lapsolver ... error
  error: subprocess-exited-with-error
  
  × Running setup.py install for lapsolver did not run successfully.
  │ exit code: 1
  ╰─> [312 lines of output]
      /usr/lib/python3.11/site-packages/setuptools/installer.py:27: SetuptoolsDeprecationWarning: setuptools.installer is deprecated. Requirements should be satisfied by a PEP 517 installer.
        warnings.warn(
      WARNING: The wheel package is not available.
      running install
      /usr/lib/python3.11/site-packages/setuptools/command/install.py:34: SetuptoolsDeprecationWarning: setup.py install is deprecated. Use build and pip and other standards-based tools.
        warnings.warn(
      running build
      running build_py
      creating build
      creating build/lib.linux-x86_64-cpython-311
      creating build/lib.linux-x86_64-cpython-311/lapsolver
      copying lapsolver/__init__.py -> build/lib.linux-x86_64-cpython-311/lapsolver
      creating build/lib.linux-x86_64-cpython-311/lapsolver/tests
      copying lapsolver/tests/__init__.py -> build/lib.linux-x86_64-cpython-311/lapsolver/tests
      copying lapsolver/tests/test_files.py -> build/lib.linux-x86_64-cpython-311/lapsolver/tests
      copying lapsolver/tests/test_dense.py -> build/lib.linux-x86_64-cpython-311/lapsolver/tests
      running egg_info
      writing lapsolver.egg-info/PKG-INFO
      writing dependency_links to lapsolver.egg-info/dependency_links.txt
      writing top-level names to lapsolver.egg-info/top_level.txt
      reading manifest file 'lapsolver.egg-info/SOURCES.txt'
      reading manifest template 'MANIFEST.in'
      adding license file 'LICENSE'
      writing manifest file 'lapsolver.egg-info/SOURCES.txt'
      /usr/lib/python3.11/site-packages/setuptools/command/build_py.py:153: SetuptoolsDeprecationWarning:     Installing 'lapsolver.data.dense' as data is deprecated, please list it in `packages`.
          !!
      
      
          ############################
          # Package would be ignored #
          ############################
          Python recognizes 'lapsolver.data.dense' as an importable package,
          but it is not listed in the `packages` configuration of setuptools.
      
          'lapsolver.data.dense' has been automatically added to the distribution only
          because it may contain data files, but this behavior is likely to change
          in future versions of setuptools (and therefore is considered deprecated).
      
          Please make sure that 'lapsolver.data.dense' is included as a package by using
          the `packages` configuration field or the proper discovery methods
          (for example by using `find_namespace_packages(...)`/`find_namespace:`
          instead of `find_packages(...)`/`find:`).
      
          You can read more about "package discovery" and "data files" on setuptools
          documentation page.
      
      
      !!
      
        check.warn(importable)
      /usr/lib/python3.11/site-packages/setuptools/command/build_py.py:153: SetuptoolsDeprecationWarning:     Installing 'lapsolver.etc' as data is deprecated, please list it in `packages`.
          !!
      
      
          ############################
          # Package would be ignored #
          ############################
          Python recognizes 'lapsolver.etc' as an importable package,
          but it is not listed in the `packages` configuration of setuptools.
      
          'lapsolver.etc' has been automatically added to the distribution only
          because it may contain data files, but this behavior is likely to change
          in future versions of setuptools (and therefore is considered deprecated).
      
          Please make sure that 'lapsolver.etc' is included as a package by using
          the `packages` configuration field or the proper discovery methods
          (for example by using `find_namespace_packages(...)`/`find_namespace:`
          instead of `find_packages(...)`/`find:`).
      
          You can read more about "package discovery" and "data files" on setuptools
          documentation page.
      
      
      !!
      
        check.warn(importable)
      creating build/lib.linux-x86_64-cpython-311/lapsolver/data
      creating build/lib.linux-x86_64-cpython-311/lapsolver/data/dense
      copying lapsolver/data/dense/costs0.npz -> build/lib.linux-x86_64-cpython-311/lapsolver/data/dense
      copying lapsolver/data/dense/costs1.npz -> build/lib.linux-x86_64-cpython-311/lapsolver/data/dense
      copying lapsolver/data/dense/costs10.npz -> build/lib.linux-x86_64-cpython-311/lapsolver/data/dense
      copying lapsolver/data/dense/costs2.npz -> build/lib.linux-x86_64-cpython-311/lapsolver/data/dense
      copying lapsolver/data/dense/costs3.npz -> build/lib.linux-x86_64-cpython-311/lapsolver/data/dense
      copying lapsolver/data/dense/costs4.npz -> build/lib.linux-x86_64-cpython-311/lapsolver/data/dense
      copying lapsolver/data/dense/costs5.npz -> build/lib.linux-x86_64-cpython-311/lapsolver/data/dense
      copying lapsolver/data/dense/costs6.npz -> build/lib.linux-x86_64-cpython-311/lapsolver/data/dense
      copying lapsolver/data/dense/costs7.npz -> build/lib.linux-x86_64-cpython-311/lapsolver/data/dense
      copying lapsolver/data/dense/costs8.npz -> build/lib.linux-x86_64-cpython-311/lapsolver/data/dense
      copying lapsolver/data/dense/costs9.npz -> build/lib.linux-x86_64-cpython-311/lapsolver/data/dense
      creating build/lib.linux-x86_64-cpython-311/lapsolver/etc
      copying lapsolver/etc/benchmark-dtype-int.png -> build/lib.linux-x86_64-cpython-311/lapsolver/etc
      copying lapsolver/etc/benchmark-dtype-numpy.float32.png -> build/lib.linux-x86_64-cpython-311/lapsolver/etc
      running build_ext
      -- The C compiler identification is GNU 12.2.1
      -- The CXX compiler identification is GNU 12.2.1
      -- Detecting C compiler ABI info
      -- Detecting C compiler ABI info - done
      -- Check for working C compiler: /usr/bin/cc - skipped
      -- Detecting C compile features
      -- Detecting C compile features - done
      -- Detecting CXX compiler ABI info
      -- Detecting CXX compiler ABI info - done
      -- Check for working CXX compiler: /usr/bin/c++ - skipped
      -- Detecting CXX compile features
      -- Detecting CXX compile features - done
      -- Found PythonInterp: /usr/bin/python3 (found version "3.11")
      -- Found PythonLibs: /usr/lib64/libpython3.11.so
      -- Performing Test HAS_CPP14_FLAG
      -- Performing Test HAS_CPP14_FLAG - Success
      -- pybind11 v2.2.1
      -- Performing Test HAS_FLTO
      -- Performing Test HAS_FLTO - Success
      -- LTO enabled
      -- Configuring done
      -- Generating done
      -- Build files have been written to: /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/build/temp.linux-x86_64-cpython-311
      [ 50%] Building CXX object CMakeFiles/lapsolverc.dir/src/lapsolverc.cpp.o
      In file included from /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/cast.h:16,
                       from /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/attr.h:13,
                       from /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h:43,
                       from /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/src/lapsolverc.cpp:1:
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/detail/internals.h:82:33: warning: ‘int PyThread_create_key()’ is deprecated [-Wdeprecated-declarations]
         82 |     decltype(PyThread_create_key()) tstate = 0; // Usually an int but a long on Cygwin64 with Python 3.x
            |              ~~~~~~~~~~~~~~~~~~~^~
      In file included from /usr/include/python3.11/Python.h:89,
                       from /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/detail/common.h:111,
                       from /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pytypes.h:12,
                       from /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/cast.h:13:
      /usr/include/python3.11/pythread.h:96:36: note: declared here
         96 | Py_DEPRECATED(3.7) PyAPI_FUNC(int) PyThread_create_key(void);
            |                                    ^~~~~~~~~~~~~~~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/detail/internals.h:82:33: warning: ‘int PyThread_create_key()’ is deprecated [-Wdeprecated-declarations]
         82 |     decltype(PyThread_create_key()) tstate = 0; // Usually an int but a long on Cygwin64 with Python 3.x
            |              ~~~~~~~~~~~~~~~~~~~^~
      /usr/include/python3.11/pythread.h:96:36: note: declared here
         96 | Py_DEPRECATED(3.7) PyAPI_FUNC(int) PyThread_create_key(void);
            |                                    ^~~~~~~~~~~~~~~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/detail/internals.h: In function ‘pybind11::detail::internals& pybind11::detail::get_internals()’:
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/detail/internals.h:165:27: warning: ‘void PyEval_InitThreads()’ is deprecated [-Wdeprecated-declarations]
        165 |         PyEval_InitThreads();
            |         ~~~~~~~~~~~~~~~~~~^~
      In file included from /usr/include/python3.11/Python.h:95:
      /usr/include/python3.11/ceval.h:132:37: note: declared here
        132 | Py_DEPRECATED(3.9) PyAPI_FUNC(void) PyEval_InitThreads(void);
            |                                     ^~~~~~~~~~~~~~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/detail/internals.h:167:52: warning: ‘int PyThread_create_key()’ is deprecated [-Wdeprecated-declarations]
        167 |         internals_ptr->tstate = PyThread_create_key();
            |                                 ~~~~~~~~~~~~~~~~~~~^~
      /usr/include/python3.11/pythread.h:96:36: note: declared here
         96 | Py_DEPRECATED(3.7) PyAPI_FUNC(int) PyThread_create_key(void);
            |                                    ^~~~~~~~~~~~~~~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/detail/internals.h:168:31: warning: ‘int PyThread_set_key_value(int, void*)’ is deprecated [-Wdeprecated-declarations]
        168 |         PyThread_set_key_value(internals_ptr->tstate, tstate);
            |         ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      /usr/include/python3.11/pythread.h:98:36: note: declared here
         98 | Py_DEPRECATED(3.7) PyAPI_FUNC(int) PyThread_set_key_value(int key,
            |                                    ^~~~~~~~~~~~~~~~~~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/cast.h: In function ‘std::string pybind11::detail::error_string()’:
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/cast.h:441:36: error: invalid use of incomplete type ‘PyFrameObject’ {aka ‘struct _frame’}
        441 |                 "  " + handle(frame->f_code->co_filename).cast<std::string>() +
            |                                    ^~
      In file included from /usr/include/python3.11/Python.h:42:
      /usr/include/python3.11/pytypedefs.h:22:16: note: forward declaration of ‘PyFrameObject’ {aka ‘struct _frame’}
         22 | typedef struct _frame PyFrameObject;
            |                ^~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/cast.h:441:75: error: expected primary-expression before ‘>’ token
        441 |                 "  " + handle(frame->f_code->co_filename).cast<std::string>() +
            |                                                                           ^
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/cast.h:441:77: error: expected primary-expression before ‘)’ token
        441 |                 "  " + handle(frame->f_code->co_filename).cast<std::string>() +
            |                                                                             ^
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/cast.h:443:29: error: invalid use of incomplete type ‘PyFrameObject’ {aka ‘struct _frame’}
        443 |                 handle(frame->f_code->co_name).cast<std::string>() + "\n";
            |                             ^~
      /usr/include/python3.11/pytypedefs.h:22:16: note: forward declaration of ‘PyFrameObject’ {aka ‘struct _frame’}
         22 | typedef struct _frame PyFrameObject;
            |                ^~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/cast.h:443:64: error: expected primary-expression before ‘>’ token
        443 |                 handle(frame->f_code->co_name).cast<std::string>() + "\n";
            |                                                                ^
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/cast.h:443:66: error: expected primary-expression before ‘)’ token
        443 |                 handle(frame->f_code->co_name).cast<std::string>() + "\n";
            |                                                                  ^
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/cast.h:444:26: error: invalid use of incomplete type ‘PyFrameObject’ {aka ‘struct _frame’}
        444 |             frame = frame->f_back;
            |                          ^~
      /usr/include/python3.11/pytypedefs.h:22:16: note: forward declaration of ‘PyFrameObject’ {aka ‘struct _frame’}
         22 | typedef struct _frame PyFrameObject;
            |                ^~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h: In constructor ‘pybind11::gil_scoped_acquire::gil_scoped_acquire()’:
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h:1741:58: warning: ‘void* PyThread_get_key_value(int)’ is deprecated [-Wdeprecated-declarations]
       1741 |         tstate = (PyThreadState *) PyThread_get_key_value(internals.tstate);
            |                                    ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
      /usr/include/python3.11/pythread.h:100:39: note: declared here
        100 | Py_DEPRECATED(3.7) PyAPI_FUNC(void *) PyThread_get_key_value(int key);
            |                                       ^~~~~~~~~~~~~~~~~~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h:1753:35: warning: ‘int PyThread_set_key_value(int, void*)’ is deprecated [-Wdeprecated-declarations]
       1753 |             PyThread_set_key_value(internals.tstate, tstate);
            |             ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
      /usr/include/python3.11/pythread.h:98:36: note: declared here
         98 | Py_DEPRECATED(3.7) PyAPI_FUNC(int) PyThread_set_key_value(int key,
            |                                    ^~~~~~~~~~~~~~~~~~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h: In member function ‘void pybind11::gil_scoped_acquire::dec_ref()’:
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h:1792:38: warning: ‘void PyThread_delete_key_value(int)’ is deprecated [-Wdeprecated-declarations]
       1792 |             PyThread_delete_key_value(detail::get_internals().tstate);
            |             ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      /usr/include/python3.11/pythread.h:101:37: note: declared here
        101 | Py_DEPRECATED(3.7) PyAPI_FUNC(void) PyThread_delete_key_value(int key);
            |                                     ^~~~~~~~~~~~~~~~~~~~~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h: In constructor ‘pybind11::gil_scoped_release::gil_scoped_release(bool)’:
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h:1820:39: warning: ‘int PyThread_set_key_value(int, void*)’ is deprecated [-Wdeprecated-declarations]
       1820 |                 PyThread_set_key_value(key, nullptr);
            |                 ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
      /usr/include/python3.11/pythread.h:98:36: note: declared here
         98 | Py_DEPRECATED(3.7) PyAPI_FUNC(int) PyThread_set_key_value(int key,
            |                                    ^~~~~~~~~~~~~~~~~~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h: In destructor ‘pybind11::gil_scoped_release::~gil_scoped_release()’:
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h:1833:35: warning: ‘int PyThread_set_key_value(int, void*)’ is deprecated [-Wdeprecated-declarations]
       1833 |             PyThread_set_key_value(key, tstate);
            |             ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
      /usr/include/python3.11/pythread.h:98:36: note: declared here
         98 | Py_DEPRECATED(3.7) PyAPI_FUNC(int) PyThread_set_key_value(int key,
            |                                    ^~~~~~~~~~~~~~~~~~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h: In function ‘pybind11::function pybind11::get_type_overload(const void*, const detail::type_info*, const char*)’:
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h:1890:49: error: ‘PyThreadState’ {aka ‘struct _ts’} has no member named ‘frame’; did you mean ‘cframe’?
       1890 |     PyFrameObject *frame = PyThreadState_Get()->frame;
            |                                                 ^~~~~
            |                                                 cframe
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h:1891:41: error: invalid use of incomplete type ‘PyFrameObject’ {aka ‘struct _frame’}
       1891 |     if (frame && (std::string) str(frame->f_code->co_name) == name &&
            |                                         ^~
      /usr/include/python3.11/pytypedefs.h:22:16: note: forward declaration of ‘PyFrameObject’ {aka ‘struct _frame’}
         22 | typedef struct _frame PyFrameObject;
            |                ^~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h:1892:14: error: invalid use of incomplete type ‘PyFrameObject’ {aka ‘struct _frame’}
       1892 |         frame->f_code->co_argcount > 0) {
            |              ^~
      /usr/include/python3.11/pytypedefs.h:22:16: note: forward declaration of ‘PyFrameObject’ {aka ‘struct _frame’}
         22 | typedef struct _frame PyFrameObject;
            |                ^~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h:1895:18: error: invalid use of incomplete type ‘PyFrameObject’ {aka ‘struct _frame’}
       1895 |             frame->f_locals, PyTuple_GET_ITEM(frame->f_code->co_varnames, 0));
            |                  ^~
      /usr/include/python3.11/pytypedefs.h:22:16: note: forward declaration of ‘PyFrameObject’ {aka ‘struct _frame’}
         22 | typedef struct _frame PyFrameObject;
            |                ^~~~~~
      In file included from /usr/include/python3.11/Python.h:38:
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h:1895:52: error: invalid use of incomplete type ‘PyFrameObject’ {aka ‘struct _frame’}
       1895 |             frame->f_locals, PyTuple_GET_ITEM(frame->f_code->co_varnames, 0));
            |                                                    ^~
      /usr/include/python3.11/pyport.h:24:38: note: in definition of macro ‘_Py_CAST’
         24 | #define _Py_CAST(type, expr) ((type)(expr))
            |                                      ^~~~
      /usr/include/python3.11/cpython/tupleobject.h:30:38: note: in expansion of macro ‘_PyTuple_CAST’
         30 | #define PyTuple_GET_ITEM(op, index) (_PyTuple_CAST(op)->ob_item[index])
            |                                      ^~~~~~~~~~~~~
      /tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/pybind11/include/pybind11/pybind11.h:1895:30: note: in expansion of macro ‘PyTuple_GET_ITEM’
       1895 |             frame->f_locals, PyTuple_GET_ITEM(frame->f_code->co_varnames, 0));
            |                              ^~~~~~~~~~~~~~~~
      /usr/include/python3.11/pytypedefs.h:22:16: note: forward declaration of ‘PyFrameObject’ {aka ‘struct _frame’}
         22 | typedef struct _frame PyFrameObject;
            |                ^~~~~~
      gmake[2]: *** [CMakeFiles/lapsolverc.dir/build.make:76: CMakeFiles/lapsolverc.dir/src/lapsolverc.cpp.o] Error 1
      gmake[1]: *** [CMakeFiles/Makefile2:100: CMakeFiles/lapsolverc.dir/all] Error 2
      gmake: *** [Makefile:91: all] Error 2
      Traceback (most recent call last):
        File "<string>", line 2, in <module>
        File "<pip-setuptools-caller>", line 34, in <module>
        File "/tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/setup.py", line 72, in <module>
          setup(
        File "/usr/lib/python3.11/site-packages/setuptools/__init__.py", line 87, in setup
          return distutils.core.setup(**attrs)
                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        File "/usr/lib/python3.11/site-packages/setuptools/_distutils/core.py", line 177, in setup
          return run_commands(dist)
                 ^^^^^^^^^^^^^^^^^^
        File "/usr/lib/python3.11/site-packages/setuptools/_distutils/core.py", line 193, in run_commands
          dist.run_commands()
        File "/usr/lib/python3.11/site-packages/setuptools/_distutils/dist.py", line 968, in run_commands
          self.run_command(cmd)
        File "/usr/lib/python3.11/site-packages/setuptools/dist.py", line 1229, in run_command
          super().run_command(command)
        File "/usr/lib/python3.11/site-packages/setuptools/_distutils/dist.py", line 987, in run_command
          cmd_obj.run()
        File "/usr/lib/python3.11/site-packages/setuptools/command/install.py", line 68, in run
          return orig.install.run(self)
                 ^^^^^^^^^^^^^^^^^^^^^^
        File "/usr/lib/python3.11/site-packages/setuptools/_distutils/command/install.py", line 690, in run
          self.run_command('build')
        File "/usr/lib/python3.11/site-packages/setuptools/_distutils/cmd.py", line 317, in run_command
          self.distribution.run_command(command)
        File "/usr/lib/python3.11/site-packages/setuptools/dist.py", line 1229, in run_command
          super().run_command(command)
        File "/usr/lib/python3.11/site-packages/setuptools/_distutils/dist.py", line 987, in run_command
          cmd_obj.run()
        File "/usr/lib/python3.11/site-packages/setuptools/command/build.py", line 24, in run
          super().run()
        File "/usr/lib/python3.11/site-packages/setuptools/_distutils/command/build.py", line 131, in run
          self.run_command(cmd_name)
        File "/usr/lib/python3.11/site-packages/setuptools/_distutils/cmd.py", line 317, in run_command
          self.distribution.run_command(command)
        File "/usr/lib/python3.11/site-packages/setuptools/dist.py", line 1229, in run_command
          super().run_command(command)
        File "/usr/lib/python3.11/site-packages/setuptools/_distutils/dist.py", line 987, in run_command
          cmd_obj.run()
        File "/tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/setup.py", line 33, in run
          self.build_extension(ext)
        File "/tmp/pip-install-ekbfrdjj/lapsolver_e4dd55aaded347cd9b2fabba1cf0d339/setup.py", line 58, in build_extension
          subprocess.check_call(['cmake', '--build', '.'] + build_args, cwd=self.build_temp)
        File "/usr/lib64/python3.11/subprocess.py", line 413, in check_call
          raise CalledProcessError(retcode, cmd)
      subprocess.CalledProcessError: Command '['cmake', '--build', '.', '--config', 'Release', '--', '-j2']' returned non-zero exit status 2.
      [end of output]
  
  note: This error originates from a subprocess, and is likely not a problem with pip.
error: legacy-install-failure

× Encountered error while trying to install package.
╰─> lapsolver

note: This is an issue with the package mentioned above, not pip.
hint: See above for output from the failure.

How can I get Cost of the solution?

I can only get row and column index from this statement rids, cids = solve_dense(costs). How can I get the cost for these output row and column indexes?

I think the cost can be obtained by

`sum=0
 for i in rids:
    sum = sum+costs[i, cids [i]]`

Fails to build on Windows using Python 3.10 + Fix

Fails with py-lapsolver\pybind11\include\pybind11/numpy.h(35,22): error C2065: 'ssize_t': undeclared identifier.

Checking out the master branch of the pybind11 submodule, instead of the currently set branch v2.2, fixes the error and the build finishes. All tests passed.

Add Python 3.7 to CI

we should also release binary wheels for Python 3.7 on Windows.

Fails to install lapsolver using python 3.8

I use Ubuntu and I tried to install lapsolver by doing what you wrote on the Readme page, but I got this error :

python3.8 setup.py develop
/mnt/data/home/aghoul/env8/lib/python3.8/site-packages/setuptools/init.py:80: _DeprecatedInstaller: setuptools.installer and fetch_build_eggs are deprecated.
!!

    ********************************************************************************
    Requirements should be satisfied by a PEP 517 installer.
    If you are using pip, you can try `pip install --use-pep517`.
    ********************************************************************************

!!
dist.fetch_build_eggs(dist.setup_requires)
WARNING: The wheel package is not available.
running develop
/mnt/data/home/aghoul/env8/lib/python3.8/site-packages/setuptools/command/develop.py:39: EasyInstallDeprecationWarning: easy_install command is deprecated.
!!

    ********************************************************************************
    Please avoid running ``setup.py`` and ``easy_install``.
    Instead, use pypa/build, pypa/installer or other
    standards-based tools.

    See https://github.com/pypa/setuptools/issues/917 for details.
    ********************************************************************************

!!
easy_install.initialize_options(self)
/mnt/data/home/aghoul/env8/lib/python3.8/site-packages/setuptools/_distutils/cmd.py:66: SetuptoolsDeprecationWarning: setup.py install is deprecated.
!!

    ********************************************************************************
    Please avoid running ``setup.py`` directly.
    Instead, use pypa/build, pypa/installer or other
    standards-based tools.

    See https://blog.ganssle.io/articles/2021/10/setup-py-deprecated.html for details.
    ********************************************************************************

!!
self.initialize_options()
running egg_info
writing lapsolver.egg-info/PKG-INFO
writing dependency_links to lapsolver.egg-info/dependency_links.txt
writing top-level names to lapsolver.egg-info/top_level.txt
reading manifest file 'lapsolver.egg-info/SOURCES.txt'
reading manifest template 'MANIFEST.in'
warning: no files found matching 'README.md'
adding license file 'LICENSE'
writing manifest file 'lapsolver.egg-info/SOURCES.txt'
running build_ext
Traceback (most recent call last):
File "/mnt/data/home/aghoul/env8/bin/cmake", line 5, in
from cmake import cmake
ModuleNotFoundError: No module named 'cmake'
Traceback (most recent call last):
File "setup.py", line 72, in
setup(
File "/mnt/data/home/aghoul/env8/lib/python3.8/site-packages/setuptools/init.py", line 103, in setup
return distutils.core.setup(**attrs)
File "/mnt/data/home/aghoul/env8/lib/python3.8/site-packages/setuptools/_distutils/core.py", line 185, in setup
return run_commands(dist)
File "/mnt/data/home/aghoul/env8/lib/python3.8/site-packages/setuptools/_distutils/core.py", line 201, in run_commands
dist.run_commands()
File "/mnt/data/home/aghoul/env8/lib/python3.8/site-packages/setuptools/_distutils/dist.py", line 969, in run_commands
self.run_command(cmd)
File "/mnt/data/home/aghoul/env8/lib/python3.8/site-packages/setuptools/dist.py", line 963, in run_command
super().run_command(command)
File "/mnt/data/home/aghoul/env8/lib/python3.8/site-packages/setuptools/_distutils/dist.py", line 988, in run_command
cmd_obj.run()
File "/mnt/data/home/aghoul/env8/lib/python3.8/site-packages/setuptools/command/develop.py", line 33, in run
self.install_for_development()
File "/mnt/data/home/aghoul/env8/lib/python3.8/site-packages/setuptools/command/develop.py", line 108, in install_for_development
self.run_command('build_ext')
File "/mnt/data/home/aghoul/env8/lib/python3.8/site-packages/setuptools/_distutils/cmd.py", line 318, in run_command
self.distribution.run_command(command)
File "/mnt/data/home/aghoul/env8/lib/python3.8/site-packages/setuptools/dist.py", line 963, in run_command
super().run_command(command)
File "/mnt/data/home/aghoul/env8/lib/python3.8/site-packages/setuptools/_distutils/dist.py", line 988, in run_command
cmd_obj.run()
File "setup.py", line 22, in run
out = subprocess.check_output(['cmake', '--version'])
File "/usr/lib/python3.8/subprocess.py", line 411, in check_output
return run(*popenargs, stdout=PIPE, timeout=timeout, check=True,
File "/usr/lib/python3.8/subprocess.py", line 512, in run
raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['cmake', '--version']' returned non-zero exit status 1.

Thank you for your response 👍

Q: why is py-lapsolver so much faster than its counterparts like scipy.optimize.linear_sum_assignment or sklearn.utils.linear_assignment_?

Thanks for this package, it saves me a huge amount of time.

Just wondering why is it so much faster? Is it because of a better algorithm or being based on C. If latter, why didn't scipy.optimize.linear_sum_assignment or sklearn.utils.linear_assignment_ develop based on C? Thanks.

Extend Benchmarks

More libraries to test against: pymatgen, centrosome
See gatagat/lap#9

Parallel Algorithm

This is certainly the fastest LAP solver for Python that I used (by a fair margin). I was wondering if you know of any parallel extensions to the algorithm (that are well accepted) for the LAP. I Googled but couldn't find any popular approach.

If there is, I would be interested in extending the project with OpenMP.

It seems like this may be a good review of the methods:
https://pdfs.semanticscholar.org/f202/410bbc322784673f707dd35cd3220d4bca47.pdf

OpenMP not needed

Your CMakeLists.txt file requires OpenMP to be installed (line 6 and 11). If both of those lines are commented out everything compiles nicely. Those lines were causing pip install lapsolver to fail on macOS. It seems you are not using OpenMP so those lines are extraneous, right?

Compare with new Scipy implementation

As of v1.4.0 (Dec 2019) [1] [2] Scipy released a new implementation for solving the linear assignment problem.

The release notes under-sell how much of a speed improvement there is. I adapted the python-based tests found in https://github.com/Yay295/AssignmentProblemComparison, to test the speed across versions and found it to be up to 1000x faster than it used to be on random data.

For completeness: here is my test script, and these are my results:

                           |   50x50      250x250   1000x1000
--------------------------------------------------------------
scipy v1.3.4               |  0.009084    0.50559    59.3130
scipy v1.4.1               |  0.000101    0.00198     0.0439

They reference a paper in the source code which implies that this speedup is from a new, effective algorithm, rather than technical implementation improvements.

I think that either the tests should be re-run on scipy >1.4.0, or the README should make note that the latest scipy implementation is much faster than indicated.

CI slow on Python 3.5

On travis, Python 3.6 completes after 1 minute, while Python 3.5 takes more than 6 minutes to build. Seems like building cmake itself is the bottleneck.

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.