summaryrefslogtreecommitdiffstats
path: root/src/gui/graphicsview/qsimplex_p.h
diff options
context:
space:
mode:
authorJesus Sanchez-Palencia <jesus.palencia@openbossa.org>2009-05-28 17:42:36 (GMT)
committerEduardo M. Fleury <eduardo.fleury@openbossa.org>2009-07-22 18:03:52 (GMT)
commit26a785e3c65a5f60bcf5bb2e07e58bc6b544dc30 (patch)
tree88a61bdcb24206534f2a27ae1c1f593074747444 /src/gui/graphicsview/qsimplex_p.h
parenta3b7580944d22b4f3f59bc6a4828a7b01a26407f (diff)
downloadQt-26a785e3c65a5f60bcf5bb2e07e58bc6b544dc30.zip
Qt-26a785e3c65a5f60bcf5bb2e07e58bc6b544dc30.tar.gz
Qt-26a785e3c65a5f60bcf5bb2e07e58bc6b544dc30.tar.bz2
QSimplex: Adding the Simplex solver for linear systems
This implementation is based on the iterative algorithm presented in http://en.wikibooks.org/wiki/Operations_Research/The_Simplex_Method. It is capable of giving us the solution to any n variable LP model. Although we focused on QGraphicsAnchorLayout, the solver is general enough for being reused in any other Qt classes if needed. Signed-off-by: Anselmo Lacerda S. de Melo <anselmo.melo@openbossa.org> Signed-off-by: Caio Marcelo de Oliveira Filho <caio.oliveira@openbossa.org> Signed-off-by: Eduardo M. Fleury <eduardo.fleury@openbossa.org> Signed-off-by: Jesus Sanchez-Palencia <jesus.palencia@openbossa.org>
Diffstat (limited to 'src/gui/graphicsview/qsimplex_p.h')
-rw-r--r--src/gui/graphicsview/qsimplex_p.h120
1 files changed, 120 insertions, 0 deletions
diff --git a/src/gui/graphicsview/qsimplex_p.h b/src/gui/graphicsview/qsimplex_p.h
new file mode 100644
index 0000000..3881893
--- /dev/null
+++ b/src/gui/graphicsview/qsimplex_p.h
@@ -0,0 +1,120 @@
+/****************************************************************************
+**
+** Copyright (C) 1992-$THISYEAR$ $TROLLTECH$. All rights reserved.
+**
+** This file is part of the $MODULE$ of the Qt Toolkit.
+**
+** $TROLLTECH_DUAL_LICENSE$
+**
+** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
+** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+**
+****************************************************************************/
+
+#ifndef QSIMPLEX_P_H
+#define QSIMPLEX_P_H
+
+#include <QtCore/qhash.h>
+#include <QtCore/qpair.h>
+
+struct QSimplexVariable
+{
+ QSimplexVariable() : result(0), index(0) {};
+
+ qreal result;
+ uint index;
+};
+
+
+/*!
+ \internal
+
+ Representation of a LP constraint like:
+
+ (c1 * X1) + (c2 * X2) + ... = K
+ or <= K
+ or >= K
+
+ Where (ci, Xi) are the pairs in "variables" and K the real "constant".
+*/
+struct QSimplexConstraint
+{
+ QSimplexConstraint() : constant(0), ratio(Equal), artificial(0) {};
+
+ enum Ratio {
+ LessOrEqual = 0,
+ Equal,
+ MoreOrEqual
+ };
+
+ QHash<QSimplexVariable *, qreal> variables;
+ qreal constant;
+ Ratio ratio;
+
+ QPair<QSimplexVariable *, qreal> helper;
+ QSimplexVariable * artificial;
+};
+
+
+class QSimplex
+{
+public:
+ QSimplex();
+ virtual ~QSimplex();
+
+ qreal solveMin();
+ qreal solveMax();
+ QList<QSimplexVariable *> constraintsVariables();
+
+ void setConstraints(const QList<QSimplexConstraint *> constraints);
+ void setObjective(QSimplexConstraint *objective);
+
+ void dumpMatrix();
+
+private:
+ // Matrix handling
+ qreal valueAt(int row, int column);
+ void setValueAt(int row, int column, qreal value);
+ void clearRow(int rowIndex);
+ void clearColumns(int first, int last);
+ void combineRows(int toIndex, int fromIndex, qreal factor);
+
+ // Simplex
+ int findPivotColumn();
+ int pivotRowForColumn(int column);
+ void reducedRowEchelon();
+ bool iterate();
+
+ // Helpers
+ void clearDataStructures();
+ void solveMaxHelper();
+ void collectResults();
+
+ QList<QSimplexConstraint *> constraints;
+ QList<QSimplexVariable *> variables;
+ QSimplexConstraint *objective;
+
+ int rows;
+ int columns;
+ int firstArtificial;
+
+ qreal *matrix;
+};
+
+inline QList<QSimplexVariable *> QSimplex::constraintsVariables()
+{
+ return variables;
+}
+
+inline qreal QSimplex::valueAt(int rowIndex, int columnIndex)
+{
+ return matrix[rowIndex * columns + columnIndex];
+}
+
+inline void QSimplex::setValueAt(int rowIndex, int columnIndex, qreal value)
+{
+ matrix[rowIndex * columns + columnIndex] = value;
+}
+
+
+#endif