qsimplex_p.cpp

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