/
index.ts
302 lines (261 loc) · 10.3 KB
/
index.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
export class Solver {
num_rows: number
num_cols: number
#i_starts_stops: number[]
#j_counts: number[]
#column_indices: number[]
#prices: number[]
#values: number[]
#ustack: number[]
constructor () {
this.num_rows = 0
this.num_cols = 0
this.#i_starts_stops = new Array<number>()
this.#j_counts = new Array<number>()
this.#prices = new Array<number>()
this.#column_indices = new Array<number>()
this.#values = new Array<number>()
this.#ustack = new Array<number>()
}
#positive_values (): boolean {
const value = this.#values[0] === undefined ? 0 : this.#values[0]
return value >= 0
}
// Adds a single value to the internal cost matrix
add_value (row: number, column: number, value: number): void {
const currentRow = this.#j_counts.length - 1
if (row !== currentRow || row !== currentRow + 1) {
throw new Error('rows must be added in order')
}
// todo check the addition overflow
const cumalitiveOffset = this.#i_starts_stops[currentRow + 1] + 1
if (row > currentRow) {
if (this.#j_counts[currentRow] === 0) {
throw new Error('row must have at least one column')
}
this.#i_starts_stops.push(cumalitiveOffset)
this.#j_counts.push(1)
} else {
this.#i_starts_stops[currentRow + 1] = cumalitiveOffset
this.#j_counts[currentRow] += 1
}
this.#column_indices.push(column)
this.#values.push(value)
}
// extends the internal cost matrix by adding the given row, and adding the given columns, and the corresponding values
extend_from_value (row: number, columns: number[], values: number[]): void {
// Check that the given row is valid. It should be either the next row,
// or the row after the last row.
if (columns.length !== values.length) {
throw new Error('columns and values must have the same length')
}
const currentRow = this.#j_counts.length - 1
if (row !== currentRow && row !== currentRow + 1) {
throw new Error('rows must be added in order')
}
// Compute the length of the new row, and the offset of the new row.
const lengthIncrement = columns.length
const cumalitiveOffset = this.#i_starts_stops[currentRow] + lengthIncrement
// Add a new row if the given row is the next row, otherwise
// update the current row.
if (row > currentRow) {
// Check that the current row has at least one column.
if (this.#j_counts[currentRow] === 0) {
throw new Error('row must have at least one column')
}
// Add the new row.
this.#i_starts_stops.push(cumalitiveOffset)
this.#j_counts.push(lengthIncrement)
} else {
// Update the current row.
this.#i_starts_stops[currentRow + 1] = cumalitiveOffset
this.#j_counts[currentRow] += lengthIncrement
}
// Add the given columns and values to the list of columns and values.
this.#column_indices.push(...columns)
this.#values.push(...values)
}
// Get the total cost of a solution from the internal cost matrix
// Does not mutate the solution.
get_costs (solution: Solution): number {
const positiveValues = this.#positive_values()
let objective = 0
for (let i = 0; i < this.num_rows; i++) {
const j = solution.person_to_object[i]
if (j === Number.MAX_VALUE) {
continue
}
const numObjects = this.#j_counts[i]
const start = this.#i_starts_stops[i]
for (let k = 0; k < numObjects; k++) {
const index = start + k
const l = this.#column_indices[index]
if (l === j) {
if (positiveValues) {
objective += this.#values[index]
} else {
objective -= this.#values[index]
}
}
}
}
return objective
}
// Resets the solver to a default state.
// Must be called before the solver can be used and in-between calls to solve.
init (rows: number, cols: number): void {
this.num_rows = rows
this.num_cols = cols
resize(this.#i_starts_stops, 2, 0)
this.#j_counts.length = 0
this.#j_counts.push(0)
this.#column_indices.length = 0
}
// Resets a solution object to a default state.
#init_solve (solution: Solution, maximize: boolean): void {
const positiveValues = this.#positive_values()
// Javascript doesn't have a logical xor operato. big sad moments
if (maximize !== positiveValues) {
// flip the sign of all values
for (let i = 0; i < this.#values.length; i++) {
this.#values[i] = -this.#values[i]
}
}
// The prices are the amounts that are added to each element
// of the matrix to create a modified matrix.
// The prices are initially zero.
this.#prices.length = 0
resize(this.#prices, this.num_cols, 0)
// The solution.person_to_object array contains the
// column index for each row that is assigned to an object.
// Initially, no rows are assigned to an object.
solution.person_to_object.length = 0
resize(solution.person_to_object, this.num_rows, Number.MAX_VALUE)
// The solution.object_to_person array contains the
// row index for each column that is assigned to a person.
// Initially, no columns are assigned to a person.
solution.object_to_person.length = 0
resize(solution.object_to_person, this.num_cols, Number.MAX_VALUE)
// The number of rows that are not assigned to an object.
// Initially, all rows are not assigned to an object.
solution.unassigned = this.num_rows
// The unassigned rows are stored in a stack in reverse order
this.#ustack.length = 0
for (let i = this.num_rows; (i--) !== 0;) {
this.#ustack.push(i)
}
}
validate_inputs (): void {
const arcs = this.#column_indices.length
if (arcs === 0 || arcs === Number.MAX_VALUE || arcs !== this.#values.length) {
throw new Error('invalid arc count')
}
if (this.num_rows === 0 || this.num_rows === Number.MAX_VALUE) {
throw new Error('invalid row or col count')
}
}
solve (solution: Solution, maximize: boolean, epsilon = 1 / this.num_cols): void {
this.validate_inputs()
this.#init_solve(solution, maximize)
// Update the epsilon value in the solution object.
solution.epsilon = epsilon
const [wMin, wMax] = this.#values.reduce(([min, max]: [number, number], el) =>
[
// If min is less than element, return min, else return element
min < el ? min : el,
// If max is greater than element, return max, else return element
max > el ? max : el
]
// Set inital values to the largest and smallest possible numbers
, [Number.POSITIVE_INFINITY, Number.NEGATIVE_INFINITY])
// console.log(w_min, w_max);
const priceThreshold = (this.num_cols / 2) * (wMax - wMin + epsilon)
// while the number of unassigned rows is greater than zero
while (this.#ustack.length > 0) {
// Get the next unassigned row.
const u = this.#ustack.pop()
if (u === undefined) { break }
solution.iterations += 1
const start = this.#i_starts_stops[u]
const numObjects = this.#j_counts[u]
// initalize variables to default values
let maxProfit = Number.NEGATIVE_INFINITY
let secondMaxProfit = Number.NEGATIVE_INFINITY
let maxEdgeValue = Number.NEGATIVE_INFINITY
let matchedVertex = 0
// For each column in the block, calculate the profit of the edge in that column.
// A column is a potential match if its profit is greater than the profit ofthe current best match and greater than the profit of the second best match.
for (let i = 0; i < numObjects; i++) {
// Global index of the column in the block
const globalIndex = start + i
const j = this.#column_indices[globalIndex]
// The value of the edge in the column
const edgeValue = this.#values[globalIndex]
// The profit of matching the edge in the column
const profit = edgeValue - this.#prices[j]
if (profit > maxProfit) {
// The new best matched vertex
matchedVertex = j
// The old best match is now the second best
secondMaxProfit = maxProfit
// The new best match has the new best profit
maxProfit = profit
// The value of the edge in the new best match
maxEdgeValue = edgeValue
} else if (profit > secondMaxProfit) {
// The new second best match
secondMaxProfit = profit
}
}
// if the matched vertex is above the price threshold, then it is not a match
if (this.#prices[matchedVertex] > priceThreshold) {
continue
}
if (Number.isFinite(secondMaxProfit)) {
// Update the price of v to be one below the second max profit.
this.#prices[matchedVertex] = maxEdgeValue - secondMaxProfit
} else {
// Otherwise, increment the price of v by epsilon.
this.#prices[matchedVertex] += epsilon
}
// if the vertex was assigned to a person, then move that person out of the solution.
const movedOut = solution.object_to_person[matchedVertex]
if (movedOut !== Number.MAX_VALUE) {
solution.person_to_object[movedOut] = Number.MAX_VALUE
solution.unassigned += 1
// Add u back to the stack of unassigned people.
this.#ustack.push(movedOut)
}
// assign the matched vertex from the top of the stack.
solution.person_to_object[u] = matchedVertex
solution.object_to_person[matchedVertex] = u
solution.unassigned -= 1
}
}
}
// resizes an array in place to a new size, filling any new slots with the default value
function resize<T> (arr: T[], newSize: number, defaultValue: T): void {
// calculate the difference between the array length and the new size
let delta = arr.length - newSize
if (delta > 0) {
// if the array length is greater than the new size, trim the array
arr.length = newSize
} else {
// otherwise, fill the difference to the array with the default value
while (delta++ < 0) { arr.push(defaultValue) }
}
}
export class Solution {
person_to_object: number[]
object_to_person: number[]
unassigned: number
epsilon: number
iterations: number
constructor (rowCapacity: number, colCapacity: number) {
this.person_to_object = new Array<number>(rowCapacity)
this.object_to_person = new Array<number>(colCapacity)
this.unassigned = Number.MAX_VALUE
this.epsilon = Number.NaN
this.iterations = 0
}
}