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}-
9-
10-
11-
12-
13QSimplex::~QSimplex()-
14{-
15 clearDataStructures();-
16}-
17-
18-
19-
20-
21void QSimplex::clearDataStructures()-
22{-
23 if (matrix == 0)-
24 return;-
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) {-
35 delete constraints[i]->helper.first;-
36 delete constraints[i]->artificial;-
37 delete constraints[i];-
38 }-
39 constraints.clear();-
40-
41-
42 variables.clear();-
43 objective = 0;-
44}-
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__, 143149, __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) variablesSet +=		0
QSet<QSimplexVariable *>::fromList({
73 const auto &v = constraints[.at(i]->)->variables;-
74 for (auto it = v.keyscbegin(), end = v.cend(); it != end
it != endDescription
TRUEnever evaluated
FALSEnever evaluated
; ++it)		0
75 variablesSet.insert(it.key
never executed: variablesSet.insert(it.key());
never executed: 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__,189197) : qt_noop());-
95 ((!(constraints[i]->artificial == 0)) ? qt_assert("constraints[i]->artificial == 0",__FILE__,190198) : 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__, 233241, __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__,254262) : 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__, 284292, __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()) ;-
205}-
206-
207-
208-
209-
210void QSimplex::setObjective(QSimplexConstraint *newObjective)-
211{-
212 objective = newObjective;-
213}-
214-
215-
216-
217-
218void QSimplex::clearRow(int rowIndex)-
219{-
220 qreal *item = matrix + rowIndex * columns;-
221 for (int i = 0; i < columns; ++i)-
222 item[i] = 0.0;-
223}-
224-
225-
226-
227-
228void QSimplex::clearColumns(int first, int last)-
229{-
230 for (int i = 0; i < rows; ++i) {-
231 qreal *row = matrix + i * columns;-
232 for (int j = first; j <= last; ++j)-
233 row[j] = 0.0;-
234 }-
235}-
236-
237-
238-
239-
240void QSimplex::dumpMatrix()-
241{-
242 QMessageLogger(__FILE__, 347355, __PRETTY_FUNCTION__).debug("---- Simplex Matrix ----\n");-
243-
244 QString str(QLatin1String(" "));-
245 for (int j = 0; j < columns; ++j)-
246 str += QString::fromLatin1(" <%1 >").arg(j, 2);-
247 QMessageLogger(__FILE__, 352360, __PRETTY_FUNCTION__).debug("%s", QString(str).toLocal8Bit().constData());-
248 for (int i = 0; i < rows; ++i) {-
249 str = QString::fromLatin1("Row %1:").arg(i, 2);-
250-
251 qreal *row = matrix + i * columns;-
252 for (int j = 0; j < columns; ++j)-
253 str += QString::fromLatin1("%1").arg(row[j], 7, 'f', 2);-
254 QMessageLogger(__FILE__, 359367, __PRETTY_FUNCTION__).debug("%s", QString(str).toLocal8Bit().constData());-
255 }-
256 QMessageLogger(__FILE__, 361369, __PRETTY_FUNCTION__).debug("------------------------\n");-
257}-
258-
259-
260-
261-
262void QSimplex::combineRows(int toIndex, int fromIndex, qreal factor)-
263{-
264 if (!factor)-
265 return;-
266-
267 qreal *from = matrix + fromIndex * columns;-
268 qreal *to = matrix + toIndex * columns;-
269-
270 for (int j = 1; j < columns; ++j) {-
271 qreal value = from[j];-
272-
273-
274 if (value == 0.0)-
275 continue;-
276-
277 to[j] += factor * value;-
278-
279-
280 if (qAbs(to[j]) < 0.0000000001)-
281 to[j] = 0.0;-
282 }-
283}-
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) {-
294 if (valueAt(0, j) < min) {-
295 min = valueAt(0, j);-
296 minIndex = j;-
297 }-
298 }-
299-
300 return minIndex;-
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) {-
308 qreal divisor = valueAt(i, column);-
309 if (divisor <= 0)-
310 continue;-
311-
312 qreal quotient = valueAt(i, columns - 1) / divisor;-
313 if (quotient < min) {-
314 min = quotient;-
315 minIndex = i;-
316 } else if ((quotient == min) && (valueAt(i, 0) > valueAt(minIndex, 0))) {-
317 minIndex = i;-
318 }-
319 }-
320-
321 return minIndex;-
322}-
323-
324-
325-
326-
327void QSimplex::reducedRowEchelon()-
328{-
329 for (int i = 1; i < rows; ++i) {-
330 int factorInObjectiveRow = valueAt(i, 0);-
331 combineRows(0, i, -1 * valueAt(0, factorInObjectiveRow));-
332 }-
333}-
334-
335-
336-
337-
338-
339-
340-
341bool QSimplex::iterate()-
342{-
343-
344 int pivotColumn = findPivotColumn();-
345 if (pivotColumn == -1)-
346 return false;-
347-
348-
349 int pivotRow = pivotRowForColumn(pivotColumn);-
350 if (pivotRow == -1) {-
351 QMessageLogger(__FILE__, 474482, __PRETTY_FUNCTION__).warning("QSimplex: Unbounded problem!");-
352 return false;-
353 }-
354-
355-
356 qreal pivot = valueAt(pivotRow, pivotColumn);-
357 if (pivot != 1.0)-
358 combineRows(pivotRow, pivotRow, (1.0 - pivot) / pivot);-
359-
360-
361 for (int row=0; row < rows; ++row) {-
362 if (row == pivotRow)-
363 continue;-
364-
365 combineRows(row, pivotRow, -1 * valueAt(row, pivotColumn));-
366 }-
367-
368-
369 setValueAt(pivotRow, 0, pivotColumn);-
370-
371-
372-
373 return true;-
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();-
385 ++iter) {-
386-
387-
388-
389-
390 if (iter.key()->index == -1) {-
391 resultOffset += iter.value() * iter.key()->result;-
392 continue;-
393 }-
394-
395 setValueAt(0, iter.key()->index, -1 * factor * iter.value());-
396 }-
397-
398 solveMaxHelper();-
399 collectResults();-
400-
401-
402 for (int i = 0; i < constraints.size(); ++i) {-
403 ((!(constraints[i]->isSatisfied())) ? qt_assert("constraints[i]->isSatisfied()",__FILE__,540548) : qt_noop());-
404 }-
405-
406-
407-
408-
409 return (factor * valueAt(0, columns - 1)) + resultOffset;-
410}-
411-
412-
413-
414-
415-
416qreal QSimplex::solveMin()-
417{-
418 return solver(Minimum);-
419}-
420-
421-
422-
423-
424-
425qreal QSimplex::solveMax()-
426{-
427 return solver(Maximum);-
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)-
443 variables[i]->result = 0;-
444-
445-
446-
447-
448 for (int i = 1; i < rows; ++i) {-
449 int index = valueAt(i, 0) - 1;-
450 if (index < variables.size())-
451 variables[index]->result = valueAt(i, columns - 1);-
452 }-
453}-
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) {-
466 modified = false;-
467-
468-
469 QList<QSimplexConstraint *>::iterator iter = constraints->begin();-
470 while (iter != constraints->end()) {-
471 QSimplexConstraint *c = *iter;-
472 if ((c->ratio == QSimplexConstraint::Equal) && (c->variables.count() == 1)) {-
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 }-
484-
485-
486 QHash<QSimplexVariable *, qreal>::const_iterator r;-
487 for (r = results.constBegin(); r != results.constEnd(); ++r) {-
488 if (c->variables.contains(r.key())) {-
489 c->constant -= r.value() * c->variables.take(r.key());-
490 modified = true;-
491 }-
492 }-
493-
494-
495 if (c->constant < 0)-
496 c->invert();-
497-
498 if (c->variables.isEmpty()) {-
499-
500 if (c->isSatisfied() == false)-
501-
502-
503-
504 return false;-
505-
506 delete c;-
507 iter = constraints->erase(iter);-
508 } else {-
509 ++iter;-
510 }-
511 }-
512 }-
513-
514 return true;-
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) {-
524 iter.value() = -iter.value();-
525 }-
526}-
527-
528-
Switch to Source codePreprocessed file
Generated by Squish Coco Non-Commercial 4.3.0-BETA-master-30-08-2018-4cb69e9