This function is the jv shortest augmenting path algorithm to solve the assignment problem*/
| 27 | |
| 28 | /*This function is the jv shortest augmenting path algorithm to solve the assignment problem*/ |
| 29 | cost lap(const std::vector<std::vector<cost>>& assigncost, |
| 30 | std::vector<col>& rowsol, |
| 31 | std::vector<row>& colsol, |
| 32 | std::vector<cost>& u, |
| 33 | std::vector<cost>& v) |
| 34 | |
| 35 | // input: |
| 36 | // assigncost - cost matrix |
| 37 | |
| 38 | // output: |
| 39 | // rowsol - column assigned to row in solution |
| 40 | // colsol - row assigned to column in solution |
| 41 | // u - dual variables, row reduction numbers |
| 42 | // v - dual variables, column reduction numbers |
| 43 | |
| 44 | { |
| 45 | int dimRows = assigncost.size(); |
| 46 | int dimCols = assigncost[0].size(); |
| 47 | bool unassignedfound = false; |
| 48 | row numfree = 0; |
| 49 | col j2 = 0, endofpath = 0, last = 0; |
| 50 | cost min = std::numeric_limits<cost>::max(); |
| 51 | |
| 52 | std::vector<row> freeunassigned(dimRows); // list of unassigned rows. |
| 53 | std::vector<col> collist(dimCols); // list of columns to be scanned in various ways. |
| 54 | std::vector<col> matches(dimRows, 0); // counts how many times a row could be assigned. |
| 55 | std::vector<cost> d(dimCols); // 'cost-distance' in augmenting path calculation. |
| 56 | std::vector<row> pred(dimCols); // row-predecessor of column in augmenting/alternating path. |
| 57 | |
| 58 | // COLUMN REDUCTION |
| 59 | for (col j = dimCols; j--;) // reverse order gives better results. |
| 60 | { |
| 61 | // find minimum cost over rows. |
| 62 | min = assigncost[0][j]; |
| 63 | row imin = 0; |
| 64 | for (row i = 1; i < dimRows; i++) |
| 65 | if (assigncost[i][j] < min) { |
| 66 | min = assigncost[i][j]; |
| 67 | imin = i; |
| 68 | } |
| 69 | v[j] = min; |
| 70 | if (++matches[imin] == 1) { |
| 71 | // init assignment if minimum row assigned for first time. |
| 72 | rowsol[imin] = j; |
| 73 | colsol[j] = imin; |
| 74 | } else if (v[j] < v[rowsol[imin]]) { |
| 75 | int j1 = rowsol[imin]; |
| 76 | rowsol[imin] = j; |
| 77 | colsol[j] = imin; |
| 78 | colsol[j1] = -1; |
| 79 | } else |
| 80 | colsol[j] = -1; // row already assigned, column not assigned. |
| 81 | } |
| 82 | |
| 83 | // REDUCTION TRANSFER |
| 84 | for (row i = 0; i < dimRows; i++) |
| 85 | if (matches[i] == 0) // fill list of unassigned 'free' rows. |
| 86 | freeunassigned[numfree++] = i; |