graphicsview/qsimplex_p.cpp

Switch to Source codePreprocessed file
LineSource CodeCoverage
1 -
2 -
3 -
4 -
5 -
6QSimplex::QSimplex() : objective(0), rows(0), columns(0), firstArtificial(0), matrix(0) -
7{ -
8}
never executed: }
0
9 -
10 -
11 -
12 -
13QSimplex::~QSimplex() -
14{ -
15 clearDataStructures(); -
16}
never executed: }
0
17 -
18 -
19 -
20 -
21void QSimplex::clearDataStructures() -
22{ -
23 if (matrix == 0)
never evaluated: matrix == 0
0
24 return;
never executed: return;
0
25 -
26 -
27 rows = 0; -
28 columns = 0; -
29 firstArtificial = 0; -
30 free(matrix); -
31 matrix = 0; -
32 -
33 -
34 for (int i = 0; i < constraints.size(); ++i) {
never evaluated: i < constraints.size()
0
35 delete constraints[i]->helper.first; -
36 delete constraints[i]->artificial; -
37 delete constraints[i]; -
38 }
never executed: }
0
39 constraints.clear(); -
40 -
41 -
42 variables.clear(); -
43 objective = 0; -
44}
never executed: }
0
45bool QSimplex::setConstraints(const QList<QSimplexConstraint *> newConstraints) -
46{ -
47 -
48 -
49 -
50 clearDataStructures(); -
51 -
52 if (newConstraints.isEmpty())
never evaluated: newConstraints.isEmpty()
0
53 return true;
never executed: return true;
0
54 -
55 -
56 -
57 for (int i = 0; i < newConstraints.size(); ++i) {
never evaluated: i < newConstraints.size()
0
58 QSimplexConstraint *c = new QSimplexConstraint; -
59 c->constant = newConstraints[i]->constant; -
60 c->ratio = newConstraints[i]->ratio; -
61 c->variables = newConstraints[i]->variables; -
62 constraints << c; -
63 }
never executed: }
0
64 -
65 -
66 if (!simplifyConstraints(&constraints)) {
never evaluated: !simplifyConstraints(&constraints)
0
67 QMessageLogger("graphicsview/qsimplex_p.cpp", 151, __PRETTY_FUNCTION__).warning() << "QSimplex: No feasible solution!"; -
68 clearDataStructures(); -
69 return false;
never executed: return false;
0
70 } -
71 QSet<QSimplexVariable *> variablesSet; -
72 for (int i = 0; i < constraints.size(); ++i)
never evaluated: i < constraints.size()
0
73 variablesSet += QSet<QSimplexVariable *>::fromList(constraints[i]->variables.keys());
never executed: variablesSet += QSet<QSimplexVariable *>::fromList(constraints[i]->variables.keys());
0
74 -
75 variables = variablesSet.toList(); -
76 -
77 -
78 -
79 -
80 for (int i = 0; i < variables.size(); ++i) {
never evaluated: i < variables.size()
0
81 -
82 variables[i]->index = i + 1; -
83 }
never executed: }
0
84 int variableIndex = variables.size(); -
85 QList <QSimplexVariable *> artificialList; -
86 -
87 for (int i = 0; i < constraints.size(); ++i) {
never evaluated: i < constraints.size()
0
88 QSimplexVariable *slack; -
89 QSimplexVariable *surplus; -
90 QSimplexVariable *artificial; -
91 -
92 qt_noop(); -
93 qt_noop(); -
94 -
95 switch(constraints[i]->ratio) { -
96 case QSimplexConstraint::LessOrEqual: -
97 slack = new QSimplexVariable; -
98 slack->index = ++variableIndex; -
99 constraints[i]->helper.first = slack; -
100 constraints[i]->helper.second = 1.0; -
101 break;
never executed: break;
0
102 case QSimplexConstraint::MoreOrEqual: -
103 surplus = new QSimplexVariable; -
104 surplus->index = ++variableIndex; -
105 constraints[i]->helper.first = surplus; -
106 constraints[i]->helper.second = -1.0; -
107 -
108 case QSimplexConstraint::Equal:
code before this statement never executed: case QSimplexConstraint::Equal:
0
109 artificial = new QSimplexVariable; -
110 constraints[i]->artificial = artificial; -
111 artificialList += constraints[i]->artificial; -
112 break;
never executed: break;
0
113 } -
114 }
never executed: }
0
115 -
116 -
117 -
118 -
119 -
120 firstArtificial = variableIndex + 1; -
121 for (int i = 0; i < artificialList.size(); ++i)
never evaluated: i < artificialList.size()
0
122 artificialList[i]->index = ++variableIndex;
never executed: artificialList[i]->index = ++variableIndex;
0
123 artificialList.clear(); -
124 -
125 -
126 -
127 -
128 -
129 -
130 columns = variableIndex + 2; -
131 -
132 rows = constraints.size() + 1; -
133 -
134 matrix = (qreal *)malloc(sizeof(qreal) * columns * rows); -
135 if (!matrix) {
never evaluated: !matrix
0
136 QMessageLogger("graphicsview/qsimplex_p.cpp", 241, __PRETTY_FUNCTION__).warning() << "QSimplex: Unable to allocate memory!"; -
137 return false;
never executed: return false;
0
138 } -
139 for (int i = columns * rows - 1; i >= 0; --i)
never evaluated: i >= 0
0
140 matrix[i] = 0.0;
never executed: matrix[i] = 0.0;
0
141 -
142 -
143 for (int i = 1; i <= constraints.size(); ++i) {
never evaluated: i <= constraints.size()
0
144 QSimplexConstraint *c = constraints[i - 1]; -
145 -
146 if (c->artificial) {
never evaluated: c->artificial
0
147 -
148 setValueAt(i, 0, c->artificial->index); -
149 setValueAt(i, c->artificial->index, 1.0); -
150 -
151 if (c->helper.second != 0.0) {
never evaluated: c->helper.second != 0.0
0
152 -
153 setValueAt(i, c->helper.first->index, c->helper.second); -
154 }
never executed: }
0
155 } else {
never executed: }
0
156 -
157 qt_noop(); -
158 setValueAt(i, 0, c->helper.first->index); -
159 setValueAt(i, c->helper.first->index, 1.0); -
160 }
never executed: }
0
161 -
162 QHash<QSimplexVariable *, qreal>::const_iterator iter; -
163 for (iter = c->variables.constBegin(); -
164 iter != c->variables.constEnd();
never evaluated: iter != c->variables.constEnd()
0
165 ++iter) { -
166 setValueAt(i, iter.key()->index, iter.value()); -
167 }
never executed: }
0
168 -
169 setValueAt(i, columns - 1, c->constant); -
170 }
never executed: }
0
171 -
172 -
173 -
174 for (int j = firstArtificial; j < columns - 1; ++j)
never evaluated: j < columns - 1
0
175 setValueAt(0, j, 1.0);
never executed: setValueAt(0, j, 1.0);
0
176 -
177 -
178 solveMaxHelper(); -
179 -
180 -
181 -
182 -
183 -
184 -
185 -
186 if ((valueAt(0, columns - 1) != 0.0) && (qAbs(valueAt(0, columns - 1)) > 0.00001)) {
never evaluated: (valueAt(0, columns - 1) != 0.0)
never evaluated: (qAbs(valueAt(0, columns - 1)) > 0.00001)
0
187 QMessageLogger("graphicsview/qsimplex_p.cpp", 292, __PRETTY_FUNCTION__).warning() << "QSimplex: No feasible solution!"; -
188 clearDataStructures(); -
189 return false;
never executed: return false;
0
190 } -
191 -
192 -
193 -
194 -
195 clearColumns(firstArtificial, columns - 2); -
196 -
197 return true;
never executed: return true;
0
198} -
199void QSimplex::solveMaxHelper() -
200{ -
201 reducedRowEchelon(); -
202 while (iterate()) ;
never evaluated: iterate()
never executed: ;
0
203}
never executed: }
0
204 -
205 -
206 -
207 -
208void QSimplex::setObjective(QSimplexConstraint *newObjective) -
209{ -
210 objective = newObjective; -
211}
never executed: }
0
212 -
213 -
214 -
215 -
216void QSimplex::clearRow(int rowIndex) -
217{ -
218 qreal *item = matrix + rowIndex * columns; -
219 for (int i = 0; i < columns; ++i)
never evaluated: i < columns
0
220 item[i] = 0.0;
never executed: item[i] = 0.0;
0
221}
never executed: }
0
222 -
223 -
224 -
225 -
226void QSimplex::clearColumns(int first, int last) -
227{ -
228 for (int i = 0; i < rows; ++i) {
never evaluated: i < rows
0
229 qreal *row = matrix + i * columns; -
230 for (int j = first; j <= last; ++j)
never evaluated: j <= last
0
231 row[j] = 0.0;
never executed: row[j] = 0.0;
0
232 }
never executed: }
0
233}
never executed: }
0
234 -
235 -
236 -
237 -
238void QSimplex::dumpMatrix() -
239{ -
240 QMessageLogger("graphicsview/qsimplex_p.cpp", 355, __PRETTY_FUNCTION__).debug("---- Simplex Matrix ----\n"); -
241 -
242 QString str(QLatin1String(" ")); -
243 for (int j = 0; j < columns; ++j)
never evaluated: j < columns
0
244 str += QString::fromLatin1(" <%1 >").arg(j, 2);
never executed: str += QString::fromLatin1(" <%1 >").arg(j, 2);
0
245 QMessageLogger("graphicsview/qsimplex_p.cpp", 360, __PRETTY_FUNCTION__).debug("%s", QString(str).toLocal8Bit().constData()); -
246 for (int i = 0; i < rows; ++i) {
never evaluated: i < rows
0
247 str = QString::fromLatin1("Row %1:").arg(i, 2); -
248 -
249 qreal *row = matrix + i * columns; -
250 for (int j = 0; j < columns; ++j)
never evaluated: j < columns
0
251 str += QString::fromLatin1("%1").arg(row[j], 7, 'f', 2);
never executed: str += QString::fromLatin1("%1").arg(row[j], 7, 'f', 2);
0
252 QMessageLogger("graphicsview/qsimplex_p.cpp", 367, __PRETTY_FUNCTION__).debug("%s", QString(str).toLocal8Bit().constData()); -
253 }
never executed: }
0
254 QMessageLogger("graphicsview/qsimplex_p.cpp", 369, __PRETTY_FUNCTION__).debug("------------------------\n"); -
255}
never executed: }
0
256 -
257 -
258 -
259 -
260void QSimplex::combineRows(int toIndex, int fromIndex, qreal factor) -
261{ -
262 if (!factor)
never evaluated: !factor
0
263 return;
never executed: return;
0
264 -
265 qreal *from = matrix + fromIndex * columns; -
266 qreal *to = matrix + toIndex * columns; -
267 -
268 for (int j = 1; j < columns; ++j) {
never evaluated: j < columns
0
269 qreal value = from[j]; -
270 -
271 -
272 if (value == 0.0)
never evaluated: value == 0.0
0
273 continue;
never executed: continue;
0
274 -
275 to[j] += factor * value; -
276 -
277 -
278 if (qAbs(to[j]) < 0.0000000001)
never evaluated: qAbs(to[j]) < 0.0000000001
0
279 to[j] = 0.0;
never executed: to[j] = 0.0;
0
280 }
never executed: }
0
281}
never executed: }
0
282 -
283 -
284 -
285 -
286int QSimplex::findPivotColumn() -
287{ -
288 qreal min = 0; -
289 int minIndex = -1; -
290 -
291 for (int j = 0; j < columns-1; ++j) {
never evaluated: j < columns-1
0
292 if (valueAt(0, j) < min) {
never evaluated: valueAt(0, j) < min
0
293 min = valueAt(0, j); -
294 minIndex = j; -
295 }
never executed: }
0
296 }
never executed: }
0
297 -
298 return minIndex;
never executed: return minIndex;
0
299} -
300int QSimplex::pivotRowForColumn(int column) -
301{ -
302 qreal min = qreal(999999999999.0); -
303 int minIndex = -1; -
304 -
305 for (int i = 1; i < rows; ++i) {
never evaluated: i < rows
0
306 qreal divisor = valueAt(i, column); -
307 if (divisor <= 0)
never evaluated: divisor <= 0
0
308 continue;
never executed: continue;
0
309 -
310 qreal quotient = valueAt(i, columns - 1) / divisor; -
311 if (quotient < min) {
never evaluated: quotient < min
0
312 min = quotient; -
313 minIndex = i; -
314 } else if ((quotient == min) && (valueAt(i, 0) > valueAt(minIndex, 0))) {
never evaluated: (quotient == min)
never evaluated: (valueAt(i, 0) > valueAt(minIndex, 0))
never executed: }
0
315 minIndex = i; -
316 }
never executed: }
0
317 } -
318 -
319 return minIndex;
never executed: return minIndex;
0
320} -
321 -
322 -
323 -
324 -
325void QSimplex::reducedRowEchelon() -
326{ -
327 for (int i = 1; i < rows; ++i) {
never evaluated: i < rows
0
328 int factorInObjectiveRow = valueAt(i, 0); -
329 combineRows(0, i, -1 * valueAt(0, factorInObjectiveRow)); -
330 }
never executed: }
0
331}
never executed: }
0
332 -
333 -
334 -
335 -
336 -
337 -
338 -
339bool QSimplex::iterate() -
340{ -
341 -
342 int pivotColumn = findPivotColumn(); -
343 if (pivotColumn == -1)
never evaluated: pivotColumn == -1
0
344 return false;
never executed: return false;
0
345 -
346 -
347 int pivotRow = pivotRowForColumn(pivotColumn); -
348 if (pivotRow == -1) {
never evaluated: pivotRow == -1
0
349 QMessageLogger("graphicsview/qsimplex_p.cpp", 482, __PRETTY_FUNCTION__).warning() << "QSimplex: Unbounded problem!"; -
350 return false;
never executed: return false;
0
351 } -
352 -
353 -
354 qreal pivot = valueAt(pivotRow, pivotColumn); -
355 if (pivot != 1.0)
never evaluated: pivot != 1.0
0
356 combineRows(pivotRow, pivotRow, (1.0 - pivot) / pivot);
never executed: combineRows(pivotRow, pivotRow, (1.0 - pivot) / pivot);
0
357 -
358 -
359 for (int row=0; row < rows; ++row) {
never evaluated: row < rows
0
360 if (row == pivotRow)
never evaluated: row == pivotRow
0
361 continue;
never executed: continue;
0
362 -
363 combineRows(row, pivotRow, -1 * valueAt(row, pivotColumn)); -
364 }
never executed: }
0
365 -
366 -
367 setValueAt(pivotRow, 0, pivotColumn); -
368 -
369 -
370 -
371 return true;
never executed: return true;
0
372} -
373qreal QSimplex::solver(solverFactor factor) -
374{ -
375 -
376 clearRow(0); -
377 -
378 -
379 qreal resultOffset = 0; -
380 QHash<QSimplexVariable *, qreal>::const_iterator iter; -
381 for (iter = objective->variables.constBegin(); -
382 iter != objective->variables.constEnd();
never evaluated: iter != objective->variables.constEnd()
0
383 ++iter) { -
384 -
385 -
386 -
387 -
388 if (iter.key()->index == -1) {
never evaluated: iter.key()->index == -1
0
389 resultOffset += iter.value() * iter.key()->result; -
390 continue;
never executed: continue;
0
391 } -
392 -
393 setValueAt(0, iter.key()->index, -1 * factor * iter.value()); -
394 }
never executed: }
0
395 -
396 solveMaxHelper(); -
397 collectResults(); -
398 return (factor * valueAt(0, columns - 1)) + resultOffset;
never executed: return (factor * valueAt(0, columns - 1)) + resultOffset;
0
399} -
400 -
401 -
402 -
403 -
404 -
405qreal QSimplex::solveMin() -
406{ -
407 return solver(Minimum);
never executed: return solver(Minimum);
0
408} -
409 -
410 -
411 -
412 -
413 -
414qreal QSimplex::solveMax() -
415{ -
416 return solver(Maximum);
never executed: return solver(Maximum);
0
417} -
418 -
419 -
420 -
421 -
422 -
423 -
424 -
425void QSimplex::collectResults() -
426{ -
427 -
428 -
429 -
430 -
431 for (int i = 0; i < variables.size(); ++i)
never evaluated: i < variables.size()
0
432 variables[i]->result = 0;
never executed: variables[i]->result = 0;
0
433 -
434 -
435 -
436 -
437 for (int i = 1; i < rows; ++i) {
never evaluated: i < rows
0
438 int index = valueAt(i, 0) - 1; -
439 if (index < variables.size())
never evaluated: index < variables.size()
0
440 variables[index]->result = valueAt(i, columns - 1);
never executed: variables[index]->result = valueAt(i, columns - 1);
0
441 }
never executed: }
0
442}
never executed: }
0
443 -
444 -
445 -
446 -
447 -
448 -
449bool QSimplex::simplifyConstraints(QList<QSimplexConstraint *> *constraints) -
450{ -
451 QHash<QSimplexVariable *, qreal> results; -
452 bool modified = true; -
453 -
454 while (modified) {
never evaluated: modified
0
455 modified = false; -
456 -
457 -
458 QList<QSimplexConstraint *>::iterator iter = constraints->begin(); -
459 while (iter != constraints->end()) {
never evaluated: iter != constraints->end()
0
460 QSimplexConstraint *c = *iter; -
461 if ((c->ratio == QSimplexConstraint::Equal) && (c->variables.count() == 1)) {
never evaluated: (c->ratio == QSimplexConstraint::Equal)
never evaluated: (c->variables.count() == 1)
0
462 -
463 -
464 QSimplexVariable *variable = c->variables.constBegin().key(); -
465 qreal result = c->constant / c->variables.value(variable); -
466 -
467 results.insert(variable, result); -
468 variable->result = result; -
469 variable->index = -1; -
470 modified = true; -
471 -
472 }
never executed: }
0
473 -
474 -
475 QHash<QSimplexVariable *, qreal>::const_iterator r; -
476 for (r = results.constBegin(); r != results.constEnd(); ++r) {
never evaluated: r != results.constEnd()
0
477 if (c->variables.contains(r.key())) {
never evaluated: c->variables.contains(r.key())
0
478 c->constant -= r.value() * c->variables.take(r.key()); -
479 modified = true; -
480 }
never executed: }
0
481 }
never executed: }
0
482 -
483 -
484 if (c->constant < 0)
never evaluated: c->constant < 0
0
485 c->invert();
never executed: c->invert();
0
486 -
487 if (c->variables.isEmpty()) {
never evaluated: c->variables.isEmpty()
0
488 -
489 if (c->isSatisfied() == false)
never evaluated: c->isSatisfied() == false
0
490 -
491 -
492 -
493 return false;
never executed: return false;
0
494 -
495 delete c; -
496 iter = constraints->erase(iter); -
497 } else {
never executed: }
0
498 ++iter; -
499 }
never executed: }
0
500 } -
501 }
never executed: }
0
502 -
503 return true;
never executed: return true;
0
504} -
505 -
506void QSimplexConstraint::invert() -
507{ -
508 constant = -constant; -
509 ratio = Ratio(2 - ratio); -
510 -
511 QHash<QSimplexVariable *, qreal>::iterator iter; -
512 for (iter = variables.begin(); iter != variables.end(); ++iter) {
never evaluated: iter != variables.end()
0
513 iter.value() = -iter.value(); -
514 }
never executed: }
0
515}
never executed: }
0
516 -
517 -
518 -
Switch to Source codePreprocessed file
Generated by Squish Coco Non-Commercial