Importing Cython 'munkres' module

[emmanuelasso]

Hi. When I import gmatch4py there is a warning: for optimal results, the Cython 'munkres' module must be installed. But when entering the given url this is totally deprecated and it is impossible to install. How much does this affect the operation of gmatch4py?

[jacquesfize]

Hi @emmanuelasso

For my part, the installation of the munkres module worked smoothly. Here, my installation script:

virtualenv -p python3 test_munkres
cd test_munkres
source bin/activate
pip install numpy cython scipy
pip install git+https://github.com/jfrelinger/cython-munkres-wrapper.git

If the munkres algorithm is not installed, the scipy.optimize.linear_sum_assignment is used. However, in terms of performance, the munkres package is much faster. As an example:

import numpy as np
from munkres import munkres
from scipy.optimize import linear_sum_assignment

a = np.random.randint(0,10,81).reshape(9,9).astype(float)

%time linear_sum_assignment(a)
CPU times: user 759 µs, sys: 208 µs, total: 967 µs
Wall time: 800 µs
Out[18]: (array([0, 1, 2, 3, 4, 5, 6, 7, 8]), array([5, 2, 0, 3, 8, 7, 1, 4, 6]))

%time munkres(a)
CPU times: user 46 µs, sys: 4 µs, total: 50 µs
Wall time: 54.1 µs
Out[19]:
array([[False, False, False, False, False,  True, False, False, False],
       [False, False,  True, False, False, False, False, False, False],
       [ True, False, False, False, False, False, False, False, False],
       [False, False, False,  True, False, False, False, False, False],
       [False, False, False, False, False, False, False, False,  True],
       [False, False, False, False, False, False, False,  True, False],
       [False,  True, False, False, False, False, False, False, False],
       [False, False, False, False,  True, False, False, False, False],
       [False, False, False, False, False, False,  True, False, False]])

Bests,
Jacques