hrldcpr / hungarian Goto Github PK

Hungarian / Munkres' algorithm for the linear assignment problem, in Python

License: MIT License

C++ 74.05% C 3.20% Python 22.75%

hungarian's Introduction

This is an outdated package

Consider using scipy.optimize.linear_sum_assignment instead.

This module is just a simple wrapper for a C++ implementation of Knuth's Hungarian algorithm, a.k.a. Munkres' algorithm, for the linear assignment problem.

For a faster, but less tolerant, LAP algorithm see http://github.com/hrldcpr/pyLAPJV

Note that this module depends on the numpy module. You must install numpy before you can compile this module. Numpy can be downloaded from http://numpy.scipy.org

If you have any problems with this module, you should contact me, not Mr. Battre.

To build this module run:

> python setup.py build

Then you can either put the file build/lib-/hungarian.so in the same directory as the code that will be using it, or you can install it so that all of your python programs can see it:

> python setup.py install

For the module's documentation, type at a Python prompt:

>>> help('hungarian')

Additional Information:

This wrapper for the algorithm uses double precision (i.e. 64-bit) floating point arithmetic. To change it to single precision, integer, or anything else, simply change the corresponding types in asp.h

hungarian's People

Contributors

Stargazers

Watchers

hungarian's Issues

Wrong result for example?

It may be that I'm not understanding how to use this code correctly, but as I'm interpreting the output on the example included with this package it is not optimal. The scipy implementation finds the correct one.

In [1]: import numpy as np

In [2]: import hungarian

In [3]: from scipy.optimize import linear_sum_assignment

In [4]: inf = 1000

In [5]: a = np.array( [[inf,2,11,10,8,7,6,5],
                  [6,inf,1,8,8,4,6,7],
                  [5,12,inf,11,8,12,3,11],
                  [11,9,10,inf,1,9,8,10],
                  [11,11,9,4,inf,2,10,9],
                  [12,8,5,2,11,inf,11,9],
                  [10,11,12,10,9,12,inf,3],
                  [10,10,10,10,6,3,1,inf]] )

In [6]: sorted(zip(*hungarian.lap(a)))
Out[6]: [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3), (6, 6), (7, 7)]

In [7]: sorted(zip(*linear_sum_assignment(a)))
Out[7]: [(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3), (6, 7), (7, 6)]

In [8]: sum(a[hungarian.lap(a)])
Out[8]: 2013

In [9]: sum(a[linear_sum_assignment(a)])
Out[9]: 17

Build fails, cant compile

I get this error in a Python 3.5 Conda environment on Windows 10 while trying to build the modul.

Any idea how to fix this?

Many thanks in advance.

running build
running config_cc
unifing config_cc, config, build_clib, build_ext, build commands --compiler options
running config_fc
unifing config_fc, config, build_clib, build_ext, build commands --fcompiler options
running build_src
build_src
building extension "hungarian" sources
 - nothing done with h_files = ['asp.h']
build_src: building npy-pkg config files
running build_ext
No module named 'numpy.distutils._msvccompiler' in numpy.distutils; trying from distutils
customize MSVCCompiler
customize MSVCCompiler using build_ext
No module named 'numpy.distutils._msvccompiler' in numpy.distutils; trying from distutils
customize MSVCCompiler
Missing compiler_cxx fix for MSVCCompiler
customize MSVCCompiler using build_ext
building 'hungarian' extension
compiling C sources
creating build
creating build\temp.win-amd64-3.5
creating build\temp.win-amd64-3.5\Release
C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\BIN\x86_amd64\cl.exe /c /nologo /Ox /W3 /GL /DNDEBUG /MD -IG:\Programme\Anaconda\envs\keras2\lib\site-packages\numpy\core\include -IG:\Programme\Anaconda\envs\keras2\include -IG:\Programme\Anaconda\envs\keras2\include -I"C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\INCLUDE" -I"C:\Program Files (x86)\Windows Kits\10\include\10.0.10240.0\ucrt" -I"C:\Program Files (x86)\Windows Kits\10\include\10.0.10240.0\shared" -I"C:\Program Files (x86)\Windows Kits\10\include\10.0.10240.0\um" -I"C:\Program Files (x86)\Windows Kits\10\include\10.0.10240.0\winrt" /EHsc /Tpasp.cpp /Fobuild\temp.win-amd64-3.5\Release\asp.obj /Zm1000
Found executable C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\BIN\x86_amd64\cl.exe
C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\BIN\x86_amd64\cl.exe /c /nologo /Ox /W3 /GL /DNDEBUG /MD -IG:\Programme\Anaconda\envs\keras2\lib\site-packages\numpy\core\include -IG:\Programme\Anaconda\envs\keras2\include -IG:\Programme\Anaconda\envs\keras2\include -I"C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\INCLUDE" -I"C:\Program Files (x86)\Windows Kits\10\include\10.0.10240.0\ucrt" -I"C:\Program Files (x86)\Windows Kits\10\include\10.0.10240.0\shared" -I"C:\Program Files (x86)\Windows Kits\10\include\10.0.10240.0\um" -I"C:\Program Files (x86)\Windows Kits\10\include\10.0.10240.0\winrt" /EHsc /Tphungarian.cpp /Fobuild\temp.win-amd64-3.5\Release\hungarian.obj /Zm1000
hungarian.cpp
g:\programme\anaconda\envs\keras2\lib\site-packages\numpy\core\include\numpy\npy_1_7_deprecated_api.h(12) : Warning Msg: Using deprecated NumPy API, disable it by #defining NPY_NO_DEPRECATED_API NPY_1_7_API_VERSION
hungarian.cpp(38): warning C4244: '=': conversion from 'npy_intp' to 'int', possible loss of data
hungarian.cpp(98): error C3861: 'Py_InitModule': identifier not found
hungarian.cpp(106): error C2664: 'void Py_SetProgramName(wchar_t *)': cannot convert argument 1 from 'char *' to 'wchar_t *'
hungarian.cpp(106): note: Types pointed to are unrelated; conversion requires reinterpret_cast, C-style cast or function-style cast
error: Command "C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\BIN\x86_amd64\cl.exe /c /nologo /Ox /W3 /GL /DNDEBUG /MD -IG:\Programme\Anaconda\envs\keras2\lib\site-packages\numpy\core\include -IG:\Programme\Anaconda\envs\keras2\include -IG:\Programme\Anaconda\envs\keras2\include -I"C:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\INCLUDE" -I"C:\Program Files (x86)\Windows Kits\10\include\10.0.10240.0\ucrt" -I"C:\Program Files (x86)\Windows Kits\10\include\10.0.10240.0\shared" -I"C:\Program Files (x86)\Windows Kits\10\include\10.0.10240.0\um" -I"C:\Program Files (x86)\Windows Kits\10\include\10.0.10240.0\winrt" /EHsc /Tphungarian.cpp /Fobuild\temp.win-amd64-3.5\Release\hungarian.obj /Zm1000" failed with exit status 2```

error installing hungarian in python 3.7.4

When try to install hungarian in Anaconda Promt I get the following message. Why?

(base) PS C:\Windows\system32> pip install hungarian
Collecting hungarian
Using cached https://files.pythonhosted.org/packages/b2/f9/9cccbbb8c724c4eff5d006bd3fe185e91d121caf2ffd345fe31421f1c886/hungarian-0.2.3.tar.gz
Building wheels for collected packages: hungarian
Building wheel for hungarian (setup.py) ... error
ERROR: Command errored out with exit status 1:
command: 'C:\ProgramData\Anaconda3\python.exe' -u -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'C:\Users\pexle\AppData\Local\Temp\pip-install-up8efxqd\hungarian\setup.py'"'"'; file='"'"'C:\Users\pexle\AppData\Local\Temp\pip-install-up8efxqd\hungarian\setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(file);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, file, '"'"'exec'"'"'))' bdist_wheel -d 'C:\Users\pexle\AppData\Local\Temp\pip-wheel-g1mta5do' --python-tag cp37
cwd: C:\Users\pexle\AppData\Local\Temp\pip-install-up8efxqd\hungarian
Complete output (22 lines):
running bdist_wheel
running build
running config_cc
unifing config_cc, config, build_clib, build_ext, build commands --compiler options
running config_fc
unifing config_fc, config, build_clib, build_ext, build commands --fcompiler options
running build_src
build_src
building extension "hungarian" sources

nothing done with h_files = ['asp.h']
build_src: building npy-pkg config files
running build_ext
No module named 'numpy.distutils._msvccompiler' in numpy.distutils; trying from distutils
customize MSVCCompiler
customize MSVCCompiler using build_ext
No module named 'numpy.distutils._msvccompiler' in numpy.distutils; trying from distutils
customize MSVCCompiler
Missing compiler_cxx fix for MSVCCompiler
customize MSVCCompiler using build_ext
building 'hungarian' extension
compiling C sources
error: Microsoft Visual C++ 14.0 is required. Get it with "Microsoft Visual C++ Build Tools": https://visualstudio.microsoft.com/downloads/

ERROR: Failed building wheel for hungarian
Running setup.py clean for hungarian
Failed to build hungarian
Installing collected packages: hungarian
Running setup.py install for hungarian ... error
ERROR: Command errored out with exit status 1:
command: 'C:\ProgramData\Anaconda3\python.exe' -u -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'C:\Users\pexle\AppData\Local\Temp\pip-install-up8efxqd\hungarian\setup.py'"'"'; file='"'"'C:\Users\pexle\AppData\Local\Temp\pip-install-up8efxqd\hungarian\setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(file);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, file, '"'"'exec'"'"'))' install --record 'C:\Users\pexle\AppData\Local\Temp\pip-record-cxnj44aq\install-record.txt' --single-version-externally-managed --compile
cwd: C:\Users\pexle\AppData\Local\Temp\pip-install-up8efxqd\hungarian
Complete output (22 lines):
running install
running build
running config_cc
unifing config_cc, config, build_clib, build_ext, build commands --compiler options
running config_fc
unifing config_fc, config, build_clib, build_ext, build commands --fcompiler options
running build_src
build_src
building extension "hungarian" sources
- nothing done with h_files = ['asp.h']
build_src: building npy-pkg config files
running build_ext
No module named 'numpy.distutils._msvccompiler' in numpy.distutils; trying from distutils
customize MSVCCompiler
customize MSVCCompiler using build_ext
No module named 'numpy.distutils._msvccompiler' in numpy.distutils; trying from distutils
customize MSVCCompiler
Missing compiler_cxx fix for MSVCCompiler
customize MSVCCompiler using build_ext
building 'hungarian' extension
compiling C sources
error: Microsoft Visual C++ 14.0 is required. Get it with "Microsoft Visual C++ Build Tools": https://visualstudio.microsoft.com/downloads/
----------------------------------------
ERROR: Command errored out with exit status 1: 'C:\ProgramData\Anaconda3\python.exe' -u -c 'import sys, setuptools, tokenize; sys.argv[0] = '"'"'C:\Users\pexle\AppData\Local\Temp\pip-install-up8efxqd\hungarian\setup.py'"'"'; file='"'"'C:\Users\pexle\AppData\Local\Temp\pip-install-up8efxqd\hungarian\setup.py'"'"';f=getattr(tokenize, '"'"'open'"'"', open)(file);code=f.read().replace('"'"'\r\n'"'"', '"'"'\n'"'"');f.close();exec(compile(code, file, '"'"'exec'"'"'))' install --record 'C:\Users\pexle\AppData\Local\Temp\pip-record-cxnj44aq\install-record.txt' --single-version-externally-managed --compile Check the logs for full command output.

merge this supposedly faster method into scipy.optimize.linear_sum_assignment

Seems to also implement the Hungarian algorithm, and is presumably better-maintained.

Update code on pypi

This module is really great. Could you update the code on pypi? The current version doesn't build with python3.

Conda package hungarian

Thanks very much for the py3 merge. I’d like to see releases packaged for conda, as well as pypi. Do you have any objections? I’m away from a computer just now, so can’t provide many links, but the issue below may answer questions. Thanks!

seperman/deepdiff#89

ValueError: negative dimensions are not allowed

Hi,

This looks like just what I'm looking for! However, it doesn't seem to compile on either mac or ubuntu. I was wonder if you've seen this error before?

ubuntu@cmb-staging:~/hungarian-master$ python setup.py build
running build
running config_cc
unifing config_cc, config, build_clib, build_ext, build commands --compiler options
running config_fc
unifing config_fc, config, build_clib, build_ext, build commands --fcompiler options
running build_src
build_src
building extension "hungarian" sources
build_src: building npy-pkg config files
running build_ext
customize UnixCCompiler
customize UnixCCompiler using build_ext
customize UnixCCompiler
customize UnixCCompiler using build_ext
building 'hungarian' extension
compiling C++ sources
C compiler: g++ -pthread -fno-strict-aliasing -DNDEBUG -g -fwrapv -O2 -Wall -fPIC

compile options: '-I/usr/local/lib/python2.7/dist-packages/numpy-1.6.2-py2.7-linux-x86_64.egg/numpy/core/include -I/usr/include/python2.7 -c'
g++: hungarian.cpp
hungarian.cpp: In function ‘PyObject* hungarian(PyObject_, PyObject_)’:
hungarian.cpp:76:1: error: jump to label ‘error’ [-fpermissive]
hungarian.cpp:38:8: error: from here [-fpermissive]
hungarian.cpp:45:15: error: crosses initialization of ‘npy_intp* strides’
hungarian.cpp:76:1: error: jump to label ‘error’ [-fpermissive]
hungarian.cpp:32:8: error: from here [-fpermissive]
hungarian.cpp:45:15: error: crosses initialization of ‘npy_intp* strides’
hungarian.cpp: In function ‘PyObject* hungarian(PyObject_, PyObject_)’:
hungarian.cpp:76:1: error: jump to label ‘error’ [-fpermissive]
hungarian.cpp:38:8: error: from here [-fpermissive]
hungarian.cpp:45:15: error: crosses initialization of ‘npy_intp* strides’
hungarian.cpp:76:1: error: jump to label ‘error’ [-fpermissive]
hungarian.cpp:32:8: error: from here [-fpermissive]
hungarian.cpp:45:15: error: crosses initialization of ‘npy_intp* strides’
error: Command "g++ -pthread -fno-strict-aliasing -DNDEBUG -g -fwrapv -O2 -Wall -fPIC -I/usr/local/lib/python2.7/dist-packages/numpy-1.6.2-py2.7-linux-x86_64.egg/numpy/core/include -I/usr/include/python2.7 -c hungarian.cpp -o build/temp.linux-x86_64-2.7/hungarian.o" failed with exit status 1

Thanks,
Adam

for rectangular matrix matching question

Thanks for your code.It's amazing， I ran this code with a big data which size is 35003500. It cost lease than 1 second. But I have an question about the input data. The code only supports square matrix， such as 33 , 66 or 5050. But It doesn't support rectangular matrix, such as 34 , 58 , or 50*80. I wonder my way to solve it is right or not. When I have an rectangular matrix, for example:

    b = np.array(
            [[3,4,6,4,9,5],
            [6,4,5,3,8,3],
            [6,3,2,2,5,3],
            [8,4,5,4,7,2]]
    )

This is an rectangular matrix :4 * 6, so I fill it with an big number,:

    f = 100
    b2 = np.array(
            [[3,4,6,4,9,5],
            [6,4,5,3,8,3],
            [6,3,2,2,5,3],
            [8,4,5,4,7,2],
            [f,f,f,f,f,f], 
            [f,f,f,f,f,f]]
    )

And then, I can run the code ,is it right ?
And given a matrix of positive weights, the code finds the minimum weight bipartite matching between to arrays. If I want to find the max， I only need to use the max element of the matrix minus every element. So， if
someone element unmatched rows in the case of unbalanced entries，what index will return ？ -1 ？ or ？

installed with pip, imported into python, getting a 'module not callable error'

a,b = hungarian(cost)
Traceback (most recent call last):
File "", line 1, in
TypeError: 'module' object is not callable

`pip3 install -e .` fails

(and similarly uploading latest version to pypi and then pip installing fails)

Obtaining file:///Users/harold/Documents/software/hungarian
    Complete output from command python setup.py egg_info:
    WARNING: '' not a valid package name; please use only .-separated package names in setup.py
    running egg_info
    error: error in 'egg_base' option: '' does not exist or is not a directory

    ----------------------------------------
Command "python setup.py egg_info" failed with error code 1 in /Users/harold/Documents/software/hungarian/

help! having a problem installing

I have python and numpy installed. I'm trying 'python setup.py build', and this is what I see - help?

$ python setup.py build
running build
running config_cc
unifing config_cc, config, build_clib, build_ext, build commands --compiler options
running config_fc
unifing config_fc, config, build_clib, build_ext, build commands --fcompiler options
running build_src
build_src
building extension "hungarian" sources
build_src: building npy-pkg config files
running build_ext
customize UnixCCompiler
customize UnixCCompiler using build_ext
customize UnixCCompiler
customize UnixCCompiler using build_ext
building 'hungarian' extension
compiling C++ sources
C compiler: g++ -fno-strict-aliasing -fno-common -dynamic -arch i386 -DNDEBUG -g -O3 -arch i386

compile options: '-I/Library/Frameworks/Python.framework/Versions/7.3/lib/python2.7/site-packages/numpy/core/include -I/Library/Frameworks/Python.framework/Versions/7.3/include/python2.7 -c'
g++: hungarian.cpp
hungarian.cpp: In function ‘PyObject* hungarian(PyObject_, PyObject_)’:
hungarian.cpp:76: error: jump to label ‘error’
hungarian.cpp:38: error: from here
hungarian.cpp:45: error: crosses initialization of ‘npy_intp* strides’
hungarian.cpp:76: error: jump to label ‘error’
hungarian.cpp:32: error: from here
hungarian.cpp:45: error: crosses initialization of ‘npy_intp* strides’
hungarian.cpp: In function ‘PyObject* hungarian(PyObject_, PyObject_)’:
hungarian.cpp:76: error: jump to label ‘error’
hungarian.cpp:38: error: from here
hungarian.cpp:45: error: crosses initialization of ‘npy_intp* strides’
hungarian.cpp:76: error: jump to label ‘error’
hungarian.cpp:32: error: from here
hungarian.cpp:45: error: crosses initialization of ‘npy_intp* strides’
error: Command "g++ -fno-strict-aliasing -fno-common -dynamic -arch i386 -DNDEBUG -g -O3 -arch i386 -I/Library/Frameworks/Python.framework/Versions/7.3/lib/python2.7/site-packages/numpy/core/include -I/Library/Frameworks/Python.framework/Versions/7.3/include/python2.7 -c hungarian.cpp -o build/temp.macosx-10.5-i386-2.7/hungarian.o" failed with exit status 1

hrldcpr / hungarian Goto Github PK

hungarian's Introduction

hungarian's People

Contributors

Stargazers

Watchers

Forkers

hungarian's Issues

Recommend Projects

Recommend Topics

Recommend Org