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__, 143, __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 variablesSet +=
never executed: variablesSet += QSet<QSimplexVariable *>::fromList(constraints[i]->variables.keys());
0
74 QSet<QSimplexVariable *>::fromList(constraints[i]->variables.keys());
never executed: variablesSet += QSet<QSimplexVariable *>::fromList(constraints[i]->variables.keys());
0
75 variables = variablesSet.toList();-
76-
77-
78-
79-
80 for (int i = 0; i < variables.size()
i < variables.size()Description
TRUEnever evaluated
FALSEnever evaluated
; ++i) {		0
81-
82 variables[i]->index = i + 1;-
83 }
never executed: end of block
0
84 int variableIndex = variables.size();-
85 QList <QSimplexVariable *> artificialList;-
86-
87 for (int i = 0; i < constraints.size()
i < constraints.size()Description
TRUEnever evaluated
FALSEnever evaluated
; ++i) {		0
88 QSimplexVariable *slack;-
89 QSimplexVariable *surplus;-
90 QSimplexVariable *artificial;-
91-
92 ((!(constraints[i]->helper.first == 0)) ? qt_assert("constraints[i]->helper.first == 0",__FILE__,189) : qt_noop());-
93 ((!(constraints[i]->artificial == 0)) ? qt_assert("constraints[i]->artificial == 0",__FILE__,190) : qt_noop());-
94-
95 switch(constraints[i]->ratio) {-
96 case
never executed: case QSimplexConstraint::LessOrEqual:
 QSimplexConstraint::LessOrEqual:
never executed: case QSimplexConstraint::LessOrEqual:
0
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
never executed: case QSimplexConstraint::MoreOrEqual:
 QSimplexConstraint::MoreOrEqual:
never executed: case QSimplexConstraint::MoreOrEqual:
0
103 surplus = new QSimplexVariable;-
104 surplus->index = ++variableIndex;-
105 constraints[i]->helper.first = surplus;-
106 constraints[i]->helper.second = -1.0;-
107-
108 case
never executed: case QSimplexConstraint::Equal:
 QSimplexConstraint::Equal:
never executed: 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: end of block
0
115-
116-
117-
118-
119-
120 firstArtificial = variableIndex + 1;-
121 for (int i = 0; i < artificialList.size()
i < artificialList.size()Description
TRUEnever evaluated
FALSEnever evaluated
; ++i)		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
!matrixDescription
TRUEnever evaluated
FALSEnever evaluated
) {		0
136 QMessageLogger(__FILE__, 233, __PRETTY_FUNCTION__).warning("QSimplex: Unable to allocate memory!");-
137 return
never executed: return false;
 false;
never executed: return false;
0
138 }-
139 for (int i = columns * rows - 1; i >= 0
i >= 0Description
TRUEnever evaluated
FALSEnever evaluated
; --i)		0
140 matrix[i] = 0.0;
never executed: matrix[i] = 0.0;
0
141-
142-
143 for (int i = 1; i <= constraints.size()
i <= constraints.size()Description
TRUEnever evaluated
FALSEnever evaluated
; ++i) {		0
144 QSimplexConstraint *c = constraints[i - 1];-
145-
146 if (c->artificial
c->artificialDescription
TRUEnever evaluated
FALSEnever evaluated
) {		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
c->helper.second != 0.0Description
TRUEnever evaluated
FALSEnever evaluated
) {		0
152-
153 setValueAt(i, c->helper.first->index, c->helper.second);-
154 }
never executed: end of block
0
155 }
never executed: end of block
 else {		0
156-
157 ((!(c->helper.second == 1.0)) ? qt_assert("c->helper.second == 1.0",__FILE__,254) : qt_noop());-
158 setValueAt(i, 0, c->helper.first->index);-
159 setValueAt(i, c->helper.first->index, 1.0);-
160 }
never executed: end of block
0
161-
162 QHash<QSimplexVariable *, qreal>::const_iterator iter;-
163 for (iter = c->variables.constBegin();-
164 iter != c->variables.constEnd()
iter != c->var...les.constEnd()Description
TRUEnever evaluated
FALSEnever evaluated
;		0
165 ++iter) {-
166 setValueAt(i, iter.key()->index, iter.value());-
167 }
never executed: end of block
0
168-
169 setValueAt(i, columns - 1, c->constant);-
170 }
never executed: end of block
0
171-
172-
173-
174 for (int j = firstArtificial; j < columns - 1
j < columns - 1Description
TRUEnever evaluated
FALSEnever evaluated
; ++j)		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, 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
187 QMessageLogger(__FILE__, 284, __PRETTY_FUNCTION__).warning("QSimplex: No feasible solution!");-
188 clearDataStructures();-
189 return
never executed: return false;
 false;
never executed: return false;
0
190 }-
191-
192-
193-
194-
195 clearColumns(firstArtificial, columns - 2);-
196-
197 return
never executed: return true;
 true;
never executed: return true;
0
198}-
199void QSimplex::solveMaxHelper()-
200{-
201 reducedRowEchelon();-
202 while (iterate()
iterate()Description
TRUEnever evaluated
FALSEnever evaluated
) ;
never executed: ;
0
203}
never executed: end of block
0
204-
205-
206-
207-
208void QSimplex::setObjective(QSimplexConstraint *newObjective)-
209{-
210 objective = newObjective;-
211}
never executed: end of block
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 < columnsDescription
TRUEnever evaluated
FALSEnever evaluated
; ++i)		0
220 item[i] = 0.0;
never executed: item[i] = 0.0;
0
221}
never executed: end of block
0
222-
223-
224-
225-
226void QSimplex::clearColumns(int first, int last)-
227{-
228 for (int i = 0; i < rows
i < rowsDescription
TRUEnever evaluated
FALSEnever evaluated
; ++i) {		0
229 qreal *row = matrix + i * columns;-
230 for (int j = first; j <= last
j <= lastDescription
TRUEnever evaluated
FALSEnever evaluated
; ++j)		0
231 row[j] = 0.0;
never executed: row[j] = 0.0;
0
232 }
never executed: end of block
0
233}
never executed: end of block
0
234-
235-
236-
237-
238void QSimplex::dumpMatrix()-
239{-
240 QMessageLogger(__FILE__, 347, __PRETTY_FUNCTION__).debug("---- Simplex Matrix ----\n");-
241-
242 QString str(QLatin1String(" "));-
243 for (int j = 0; j < columns
j < columnsDescription
TRUEnever evaluated
FALSEnever evaluated
; ++j)		0
244 str += QString::fromLatin1(" <%1 >").arg(j, 2);
never executed: str += QString::fromLatin1(" <%1 >").arg(j, 2);
0
245 QMessageLogger(__FILE__, 352, __PRETTY_FUNCTION__).debug("%s", QString(str).toLocal8Bit().constData());-
246 for (int i = 0; i < rows
i < rowsDescription
TRUEnever evaluated
FALSEnever evaluated
; ++i) {		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 < columnsDescription
TRUEnever evaluated
FALSEnever evaluated
; ++j)		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(__FILE__, 359, __PRETTY_FUNCTION__).debug("%s", QString(str).toLocal8Bit().constData());-
253 }
never executed: end of block
0
254 QMessageLogger(__FILE__, 361, __PRETTY_FUNCTION__).debug("------------------------\n");-
255}
never executed: end of block
0
256-
257-
258-
259-
260void QSimplex::combineRows(int toIndex, int fromIndex, qreal factor)-
261{-
262 if (!factor
!factorDescription
TRUEnever evaluated
FALSEnever evaluated
)		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 < columnsDescription
TRUEnever evaluated
FALSEnever evaluated
; ++j) {		0
269 qreal value = from[j];-
270-
271-
272 if (value == 0.0
value == 0.0Description
TRUEnever evaluated
FALSEnever evaluated
)		0
273 continue;
never executed: continue;
0
274-
275 to[j] += factor * value;-
276-
277-
278 if (qAbs(to[j]) < 0.0000000001
qAbs(to[j]) < 0.0000000001Description
TRUEnever evaluated
FALSEnever evaluated
)		0
279 to[j] = 0.0;
never executed: to[j] = 0.0;
0
280 }
never executed: end of block
0
281}
never executed: end of block
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 < columns-1Description
TRUEnever evaluated
FALSEnever evaluated
; ++j) {		0
292 if (valueAt(0, j) < min
valueAt(0, j) < minDescription
TRUEnever evaluated
FALSEnever evaluated
) {		0
293 min = valueAt(0, j);-
294 minIndex = j;-
295 }
never executed: end of block
0
296 }
never executed: end of block
0
297-
298 return
never executed: return minIndex;
 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 < rowsDescription
TRUEnever evaluated
FALSEnever evaluated
; ++i) {		0
306 qreal divisor = valueAt(i, column);-
307 if (divisor <= 0
divisor <= 0Description
TRUEnever evaluated
FALSEnever evaluated
)		0
308 continue;
never executed: continue;
0
309-
310 qreal quotient = valueAt(i, columns - 1) / divisor;-
311 if (quotient < min
quotient < minDescription
TRUEnever evaluated
FALSEnever evaluated
) {		0
312 min = quotient;-
313 minIndex = i;-
314 }
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
315 minIndex = i;-
316 }
never executed: end of block
0
317 }
never executed: end of block
0
318-
319 return
never executed: return minIndex;
 minIndex;
never executed: return minIndex;
0
320}-
321-
322-
323-
324-
325void QSimplex::reducedRowEchelon()-
326{-
327 for (int i = 1; i < rows
i < rowsDescription
TRUEnever evaluated
FALSEnever evaluated
; ++i) {		0
328 int factorInObjectiveRow = valueAt(i, 0);-
329 combineRows(0, i, -1 * valueAt(0, factorInObjectiveRow));-
330 }
never executed: end of block
0
331}
never executed: end of block
0
332-
333-
334-
335-
336-
337-
338-
339bool QSimplex::iterate()-
340{-
341-
342 int pivotColumn = findPivotColumn();-
343 if (pivotColumn == -1
pivotColumn == -1Description
TRUEnever evaluated
FALSEnever evaluated
)		0
344 return
never executed: return false;
 false;
never executed: return false;
0
345-
346-
347 int pivotRow = pivotRowForColumn(pivotColumn);-
348 if (pivotRow == -1
pivotRow == -1Description
TRUEnever evaluated
FALSEnever evaluated
) {		0
349 QMessageLogger(__FILE__, 474, __PRETTY_FUNCTION__).warning("QSimplex: Unbounded problem!");-
350 return
never executed: return false;
 false;
never executed: return false;
0
351 }-
352-
353-
354 qreal pivot = valueAt(pivotRow, pivotColumn);-
355 if (pivot != 1.0
pivot != 1.0Description
TRUEnever evaluated
FALSEnever evaluated
)		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 < rowsDescription
TRUEnever evaluated
FALSEnever evaluated
; ++row) {		0
360 if (row == pivotRow
row == pivotRowDescription
TRUEnever evaluated
FALSEnever evaluated
)		0
361 continue;
never executed: continue;
0
362-
363 combineRows(row, pivotRow, -1 * valueAt(row, pivotColumn));-
364 }
never executed: end of block
0
365-
366-
367 setValueAt(pivotRow, 0, pivotColumn);-
368-
369-
370-
371 return
never executed: return true;
 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()
iter != object...les.constEnd()Description
TRUEnever evaluated
FALSEnever evaluated
;		0
383 ++iter) {-
384-
385-
386-
387-
388 if (iter.key()->index == -1
iter.key()->index == -1Description
TRUEnever evaluated
FALSEnever evaluated
) {		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: end of block
0
395-
396 solveMaxHelper();-
397 collectResults();-
398-
399-
400 for (int i = 0; i < constraints.size()
i < constraints.size()Description
TRUEnever evaluated
FALSEnever evaluated
; ++i) {		0
401 ((!(constraints[i]->isSatisfied())) ? qt_assert("constraints[i]->isSatisfied()",__FILE__,540) : qt_noop());-
402 }
never executed: end of block
0
403-
404-
405-
406-
407 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
408}-
409-
410-
411-
412-
413-
414qreal QSimplex::solveMin()-
415{-
416 return
never executed: return solver(Minimum);
 solver(Minimum);
never executed: return solver(Minimum);
0
417}-
418-
419-
420-
421-
422-
423qreal QSimplex::solveMax()-
424{-
425 return
never executed: return solver(Maximum);
 solver(Maximum);
never executed: return solver(Maximum);
0
426}-
427-
428-
429-
430-
431-
432-
433-
434void QSimplex::collectResults()-
435{-
436-
437-
438-
439-
440 for (int i = 0; i < variables.size()
i < variables.size()Description
TRUEnever evaluated
FALSEnever evaluated
; ++i)		0
441 variables[i]->result = 0;
never executed: variables[i]->result = 0;
0
442-
443-
444-
445-
446 for (int i = 1; i < rows
i < rowsDescription
TRUEnever evaluated
FALSEnever evaluated
; ++i) {		0
447 int index = valueAt(i, 0) - 1;-
448 if (index < variables.size()
index < variables.size()Description
TRUEnever evaluated
FALSEnever evaluated
)		0
449 variables[index]->result = valueAt(i, columns - 1);
never executed: variables[index]->result = valueAt(i, columns - 1);
0
450 }
never executed: end of block
0
451}
never executed: end of block
0
452-
453-
454-
455-
456-
457-
458bool QSimplex::simplifyConstraints(QList<QSimplexConstraint *> *constraints)-
459{-
460 QHash<QSimplexVariable *, qreal> results;-
461 bool modified = true;-
462-
463 while (modified
modifiedDescription
TRUEnever evaluated
FALSEnever evaluated
) {		0
464 modified = false;-
465-
466-
467 QList<QSimplexConstraint *>::iterator iter = constraints->begin();-
468 while (iter != constraints->end()
iter != constraints->end()Description
TRUEnever evaluated
FALSEnever evaluated
) {		0
469 QSimplexConstraint *c = *iter;-
470 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
471-
472-
473 QSimplexVariable *variable = c->variables.constBegin().key();-
474 qreal result = c->constant / c->variables.value(variable);-
475-
476 results.insert(variable, result);-
477 variable->result = result;-
478 variable->index = -1;-
479 modified = true;-
480-
481 }
never executed: end of block
0
482-
483-
484 QHash<QSimplexVariable *, qreal>::const_iterator r;-
485 for (r = results.constBegin(); r != results.constEnd()
r != results.constEnd()Description
TRUEnever evaluated
FALSEnever evaluated
; ++r) {		0
486 if (c->variables.contains(r.key())
c->variables.contains(r.key())Description
TRUEnever evaluated
FALSEnever evaluated
) {		0
487 c->constant -= r.value() * c->variables.take(r.key());-
488 modified = true;-
489 }
never executed: end of block
0
490 }
never executed: end of block
0
491-
492-
493 if (c->constant < 0
c->constant < 0Description
TRUEnever evaluated
FALSEnever evaluated
)		0
494 c->invert();
never executed: c->invert();
0
495-
496 if (c->variables.isEmpty()
c->variables.isEmpty()Description
TRUEnever evaluated
FALSEnever evaluated
) {		0
497-
498 if (c->isSatisfied() == false
c->isSatisfied() == falseDescription
TRUEnever evaluated
FALSEnever evaluated
)		0
499-
500-
501-
502 return
never executed: return false;
 false;
never executed: return false;
0
503-
504 delete c;-
505 iter = constraints->erase(iter);-
506 }
never executed: end of block
 else {		0
507 ++iter;-
508 }
never executed: end of block
0
509 }-
510 }
never executed: end of block
0
511-
512 return
never executed: return true;
 true;
never executed: return true;
0
513}-
514-
515void QSimplexConstraint::invert()-
516{-
517 constant = -constant;-
518 ratio = Ratio(2 - ratio);-
519-
520 QHash<QSimplexVariable *, qreal>::iterator iter;-
521 for (iter = variables.begin(); iter != variables.end()
iter != variables.end()Description
TRUEnever evaluated
FALSEnever evaluated
; ++iter) {		0
522 iter.value() = -iter.value();-
523 }
never executed: end of block
0
524}
never executed: end of block
0
525-
526-
Switch to Source codePreprocessed file
Generated by Squish Coco Non-Commercial 4.3.0-BETA-master-30-08-2018-4cb69e9