path size

[matheusbg8]

Hi phoemur,

congratulations on this amazing implementation of the Hungarian Algorithm!

I found a problem with the size of the vector path used on step 5 to track zero primes and zero stars. I believe the size must be at least twice the size of the squared matrix (original). The change should be made on the following line:

hungarian_algorithm/hungarian.cpp

Line 496 in 89af778

std::vector<std::vector<int>> path (sz+1, std::vector<int>(2, 0));

It should be 2*sz instead of sz+1.

You can check this problem with the following input:

tests.push_back({{100,100,100,81},
                 {100,100,100,100},
                 {100,100,100,17},
                 {100,100,100,100},
                 {100,100,100,99}});

After a few iterations you end-up on the following situation:

0' 0 0 0* 0
0 0 0* 19 0'
64 64 64 0' 64
0 0* 0' 19 0
0* 0' 0 18 0

In this situation you will added the 9 elements in bold on the path vector but its size is 5 resulting in a segmentation fault.

Cheers!

[MacroUniverse]

I can confirm this with the matrix
{{15,40,45},
{20,60,35},
{20,40,25}}
it gives a segmentation fault for the original code

[Helder-PB]

I can confirm this with the matrix {{15,40,45}, {20,60,35}, {20,40,25}} it gives a segmentation fault for the original code

I totally share your view. I started to make my c++ version of the original published article in
https://users.cs.duke.edu/~brd/Teaching/Bio/asmb/current/Handouts/munkres.html

where this repository is based.
Faced the same problem.

I wonder if there is a mathematical deduction to the maximum size of the variable path

[EbenezerA99]

Hello,

I am looking to use this repository but wanted to check if this was the only problem with it that you guys saw. Did fixing that path vector to be of size 2*sz fix the problem? Are there any other issues that result from this change? Are there any other issues you saw with the repository?