search

saebyn / munkres-cpp

Kuhn-Munkres (Hungarian) Algorithm in C++
http://saebyn.info/2007/05/22/munkres-code-v2/
GNU General Public License v2.0
205 stars 79 forks source link

Wrong result of function minimize_along_direction over rows and columns #11

Closed Gluttton closed 10 years ago

Gluttton commented 10 years ago

Based on test: MunkresTest.minimize_along_direction_5x5_OverRowsAndColumns_Success result of function minimize_along_direction with over_columns = true is wrong.

Possibly reason (in my opinion):

  1. Wrong test case (in particular I have not understood intention of function).
  2. Error in algorithm.
saebyn commented 10 years ago

Ah, yes. This could be more clear - the idea is that you call the minimize_along_direction function for each direction (either over columns, or over rows). To minimize in both directions, the function needs to be called twice (once with over_columns = false, and once with over_columns = true). I merged the two separate functions (minimize_rows() and minimize_columns()) into this one to reduce duplication, but it did make the operation a bit more opaque. :(

As part of the debugging I'm doing, I've changed the test case to fix it.

Gluttton commented 10 years ago

OK. Closed.