framework
framework copied to clipboard
accord-net
`IndexOutOfRangeException` exception running `Munkres.Minimize()`
What would you like to submit? (put an 'x' inside the bracket that applies)
- [ ] question
- [x] bug report
- [ ] feature request
Issue description
Here's the minimal version of my code that's throwing this exception:
double[][] scoreMatrix = new double[13][];
scoreMatrix[0] = new double[] { 0.516666666666667, 1, 0.544444444444445, 1, 1, 1, 1, 1, 1, 0.516666666666667, 0.552380952380952, 1, 1, 1, 0.516666666666667, 1, 0.562962962962963, 0.516666666666667 };
scoreMatrix[1] = new double[] { 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
scoreMatrix[2] = new double[] { 0.316666666666667, 0.504761904761905, 0.577777777777778, 1, 1, 1, 1, 1, 1, 0.316666666666667, 0.585714285714286, 1, 0.596296296296296, 1, 0.316666666666667, 0.433333333333333, 0.566666666666667, 0.55 };
scoreMatrix[3] = new double[] { 0.516666666666667, 0.552380952380952, 0.544444444444445, 1, 1, 1, 1, 1, 1, 0.516666666666667, 0.552380952380952, 1, 0.562962962962963, 1, 0.516666666666667, 0.366666666666667, 0.562962962962963, 1 };
scoreMatrix[4] = new double[] { 0.55, 0.534920634920635, 1, 1, 1, 1, 1, 1, 1, 0.55, 0.504761904761905, 1, 1, 1, 0.55, 0.55, 0.566666666666667, 0.55 };
scoreMatrix[5] = new double[] { 1, 0.392857142857143, 0.569444444444444, 1, 1, 1, 1, 1, 1, 1, 0.577380952380952, 0.513888888888889, 0.587962962962963, 1, 1, 0.541666666666667, 0.430555555555556, 1 };
scoreMatrix[6] = new double[] { 0.472222222222222, 0.507936507936508, 1, 1, 1, 1, 1, 1, 1, 0.472222222222222, 0.507936507936508, 0.444444444444445, 0.518518518518519, 1, 0.472222222222222, 0.472222222222222, 0.518518518518519, 1 };
scoreMatrix[7] = new double[] { 1, 0.535714285714286, 1, 1, 1, 1, 0.472222222222222, 1, 1, 1, 1, 1, 0.546296296296296, 1, 1, 1, 1, 1 };
scoreMatrix[8] = new double[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0.259259259259259, 0.416666666666667 };
scoreMatrix[9] = new double[] { 0.527777777777778, 0.563492063492063, 1, 1, 0.527777777777778, 1, 1, 1, 1, 0.527777777777778, 0.46031746031746, 1, 1, 1, 0.527777777777778, 0.527777777777778, 0.481481481481482, 1 };
scoreMatrix[10] = new double[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0.462962962962963, 1 };
scoreMatrix[11] = new double[] { 0.546296296296296, 0.664021164021164, 0.574074074074074, 1, 0.546296296296296, 1, 0.518518518518519, 1, 1, 0.546296296296296, 0.523809523809524, 1, 1, 1, 0.546296296296296, 0.546296296296296, 0.444444444444445, 0.546296296296296 };
scoreMatrix[12] = new double[] { 1, 0.571428571428571, 1, 1, 1, 1, 0.507936507936508, 1, 1, 1, 0.571428571428571, 0.349206349206349, 0.243386243386243, 1, 1, 1, 1, 0.535714285714286 };
Munkres munkresSolver = new Munkres(scoreMatrix);
munkresSolver.Minimize().Dump();
Here's the relevant portion of the stack trace (from LINQPad):
at Accord.Math.Optimization.Munkres.step_four()
at Accord.Math.Optimization.Munkres.RunStep(Int32 step)
at Accord.Math.Optimization.Munkres.run(Double[][] m)
at Accord.Math.Optimization.Munkres.Minimize()
I'm running the code in LINQPad. The Dump() method is a LINQPad extension method (that just dumps info about the object to the screen).
It doesn't seem to be the specific data that's causing the exception either; this code results in the same exception being thrown:
double[][] cm3 = new double[13][];
Random r = new Random(1);
for (int i = 0; i < 13; i++)
{
cm3[i] = new double[18];
for (int j = 0; j < 18; j++)
{
cm3[i][j] = r.NextDouble();
}
}
m = new Munkres(cm3);
m.Minimize().Dump();
m.Solution.Dump();
m.Value.Dump();
It's not just that the number of 'tasks' is greater than the number of 'workers' either as this code runs fine:
double[][] cm2 =
{
// Clean bathroom, Sweep floors, Wash windows, Stock shelves
/* Armond */ new double[] { 2, 3, 3, 2 },
/* Francine */ new double[] { 3, 2, 3, 1 },
/* Herbert */ new double[] { 3, 3, 2, 3 },
};
m = new Munkres(cm2);
m.Minimize().Dump();
m.Solution.Dump();
m.Value.Dump();
The above code is the same as the example in the docs for the Munkres class except with the extra Stock shelves task.
I debugged a local build of the code for the current development branch; the step_four() method code:
private int step_four()
{
List<Tuple<int, int>> zeros = find_all_zeros();
while (zeros.Count > 0)
{
path_row_0 = zeros[0].Item1;
path_col_0 = zeros[0].Item2;
primeZ[path_row_0] = path_col_0;
int stz = starZ[path_row_0];
if (stz == -1)
return 5;
rowCover[path_row_0] = true;
colCover[stz] = false;
zeros.RemoveAll(x => x.Item1 == path_row_0);
// Update
for (int r = 0; r < rowCover.Length; r++)
{
if (rowCover[r])
continue;
double a = costMatrix[r][stz];
double b = MinRow[r] + MinCol[stz];
if (a.IsEqual(b, rtol: tolerance))
zeros.Add(Tuple.Create(r, stz));
}
}
return 6;
}
The line that causes the exception is line 551:
double a = costMatrix[r][stz];
For my actual data, the value of rowCover.Length before the exception is thrown is 18 (the number of tasks).
In the step_zero() method I noticed these lines:
...
n = Math.Max(nRows, nCols);
...
this.rowCover = new bool[n];
this.colCover = new bool[n];
this.stars = Jagged.Create(n, n, false);
...
That can't be right if this is intended to work with rectangular cost matrices. I suspect now that this implementation doesn't work, generally, with rectangular cost matrices.
The code for the relevant class mentions:
/// This code has been based on the original MIT-licensed code by R.A. Pilgrim, available in
/// http://csclab.murraystate.edu/~bob.pilgrim/445/munkres.html, and on the BSD-licensed code
/// by Yi Cao, available in http://fr.mathworks.com/matlabcentral/fileexchange/20652-hungarian-algorithm-for-linear-assignment-problems--v2-3-
From the "Answers to Frequently Asked Questions" at the bottom of the first page linked in the comments:
- Munkres can be extended to rectangular arrays (i.e. more jobs than workers, or more workers than jobs) .
I'm guessing the above implies that the algorithm described on that page doesn't handle rectangular arrays.
This answer to the following Stack Overflow question claims (implicitly) that adding "padding" rows or columns, to transform a rectangular cost matrix into a square matrix suffices:
Here is a smaller example which throws the mentioned exception:
var cost = new double[][]{
new[] { 0d, 0d },
new[] { 0d, 1d },
new[] { 0d, 2d }
};
var munkres = new Munkres(cost);
munkres.Minimize();
The minimal example above could be a problem, because there are not enough "jobs" (2) for the "people" (3). But the following example throws the same exception in "step_four":
double[][] costMatrix1 =
{
new double[] {0,0,1,1,1},
new double[] {0,0,1,1,1},
new double[] {0,0,1,1,1},
};
Munkres m = new Munkres(costMatrix1);
bool success = m.Minimize(); // solve it (should return true)
I have the same problem as @skaldrom and the error happens
System.IndexOutOfRangeException: Index was outside the bounds of the array.
at Accord.Math.Optimization.Munkres.step_four()
at Accord.Math.Optimization.Munkres.run(Double[][] m)
The only way it works if the matrix x and y values are the same length.
Follow this: https://github.com/vivet/HungarianAlgorithm