Merge branch 'cmarcelo-vertexsimplification' into 4.6

2 files changed, 559 insertions, 171 deletions

diff --git a/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp
index 96f8930..42972d2 100644
--- a/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp
+++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.cpp
@@ -61,6 +61,8 @@ QGraphicsAnchorPrivate::QGraphicsAnchorPrivate(int version)
 
 QGraphicsAnchorPrivate::~QGraphicsAnchorPrivate()
 {
+    // ###
+    layoutPrivate->restoreSimplifiedGraph(QGraphicsAnchorLayoutPrivate::Orientation(data->orientation));
     layoutPrivate->removeAnchor(data->from, data->to);
 }
 
@@ -218,9 +220,20 @@ bool AnchorData::refreshSizeHints(const QLayoutStyleInfo *styleInfo)
 
 void ParallelAnchorData::updateChildrenSizes()
 {
-    firstEdge->sizeAtMinimum = secondEdge->sizeAtMinimum = sizeAtMinimum;
-    firstEdge->sizeAtPreferred = secondEdge->sizeAtPreferred = sizeAtPreferred;
-    firstEdge->sizeAtMaximum = secondEdge->sizeAtMaximum = sizeAtMaximum;
+    firstEdge->sizeAtMinimum = sizeAtMinimum;
+    firstEdge->sizeAtPreferred = sizeAtPreferred;
+    firstEdge->sizeAtMaximum = sizeAtMaximum;
+
+    const bool secondFwd = (secondEdge->from == from);
+    if (secondFwd) {
+        secondEdge->sizeAtMinimum = sizeAtMinimum;
+        secondEdge->sizeAtPreferred = sizeAtPreferred;
+        secondEdge->sizeAtMaximum = sizeAtMaximum;
+    } else {
+        secondEdge->sizeAtMinimum = -sizeAtMinimum;
+        secondEdge->sizeAtPreferred = -sizeAtPreferred;
+        secondEdge->sizeAtMaximum = -sizeAtMaximum;
+    }
 
     firstEdge->updateChildrenSizes();
     secondEdge->updateChildrenSizes();
@@ -239,8 +252,16 @@ bool ParallelAnchorData::refreshSizeHints_helper(const QLayoutStyleInfo *styleIn
         return false;
     }
 
-    minSize = qMax(firstEdge->minSize, secondEdge->minSize);
-    maxSize = qMin(firstEdge->maxSize, secondEdge->maxSize);
+    // Account for parallel anchors where the second edge is backwards.
+    // We rely on the fact that a forward anchor of sizes min, pref, max is equivalent
+    // to a backwards anchor of size (-max, -pref, -min)
+    const bool secondFwd = (secondEdge->from == from);
+    const qreal secondMin = secondFwd ? secondEdge->minSize : -secondEdge->maxSize;
+    const qreal secondPref = secondFwd ? secondEdge->prefSize : -secondEdge->prefSize;
+    const qreal secondMax = secondFwd ? secondEdge->maxSize : -secondEdge->minSize;
+
+    minSize = qMax(firstEdge->minSize, secondMin);
+    maxSize = qMin(firstEdge->maxSize, secondMax);
 
     // This condition means that the maximum size of one anchor being simplified is smaller than
     // the minimum size of the other anchor. The consequence is that there won't be a valid size
@@ -249,7 +270,22 @@ bool ParallelAnchorData::refreshSizeHints_helper(const QLayoutStyleInfo *styleIn
         return false;
     }
 
-    prefSize = qMax(firstEdge->prefSize, secondEdge->prefSize);
+    // The equivalent preferred Size of a parallel anchor is calculated as to
+    // reduce the deviation from the original preferred sizes _and_ to avoid shrinking
+    // items below their preferred sizes, unless strictly needed.
+
+    // ### This logic only holds if all anchors in the layout are "well-behaved" in the
+    // following terms:
+    //
+    // - There are no negative-sized anchors
+    // - All sequential anchors are composed of children in the same direction as the
+    //   sequential anchor itself
+    //
+    // With these assumptions we can grow a child knowing that no hidden items will
+    // have to shrink as the result of that.
+    // If any of these does not hold, we have a situation where the ParallelAnchor
+    // does not have enough information to calculate its equivalent prefSize.
+    prefSize = qMax(firstEdge->prefSize, secondPref);
     prefSize = qMin(prefSize, maxSize);
 
     // See comment in AnchorData::refreshSizeHints() about sizeAt* values
@@ -502,34 +538,67 @@ inline static qreal checkAdd(qreal a, qreal b)
 /*!
     \internal
 
-    Adds \a newAnchor to the graph \a g.
+    Adds \a newAnchor to the graph.
 
     Returns the newAnchor itself if it could be added without further changes to the graph. If a
     new parallel anchor had to be created, then returns the new parallel anchor. If a parallel anchor
     had to be created and it results in an unfeasible setup, \a feasible is set to false, otherwise
     true.
+
+    Note that in the case a new parallel anchor is created, it might also take over some constraints
+    from its children anchors.
 */
-static AnchorData *addAnchorMaybeParallel(Graph<AnchorVertex, AnchorData> *g,
-                                          AnchorData *newAnchor, bool *feasible)
+AnchorData *QGraphicsAnchorLayoutPrivate::addAnchorMaybeParallel(AnchorData *newAnchor, bool *feasible)
 {
+    Orientation orientation = Orientation(newAnchor->orientation);
+    Graph<AnchorVertex, AnchorData> &g = graph[orientation];
     *feasible = true;
 
     // If already exists one anchor where newAnchor is supposed to be, we create a parallel
     // anchor.
-    if (AnchorData *oldAnchor = g->takeEdge(newAnchor->from, newAnchor->to)) {
+    if (AnchorData *oldAnchor = g.takeEdge(newAnchor->from, newAnchor->to)) {
         ParallelAnchorData *parallel = new ParallelAnchorData(oldAnchor, newAnchor);
 
+        // The parallel anchor will "replace" its children anchors in
+        // every center constraint that they appear.
+
+        // ### If the dependent (center) anchors had reference(s) to their constraints, we
+        // could avoid traversing all the itemCenterConstraints.
+        QList<QSimplexConstraint *> &constraints = itemCenterConstraints[orientation];
+
+        AnchorData *children[2] = { oldAnchor, newAnchor };
+        QList<QSimplexConstraint *> *childrenConstraints[2] = { &parallel->m_firstConstraints,
+                                                                &parallel->m_secondConstraints };
+
+        for (int i = 0; i < 2; ++i) {
+            AnchorData *child = children[i];
+            QList<QSimplexConstraint *> *childConstraints = childrenConstraints[i];
+
+            if (!child->isCenterAnchor)
+                continue;
+
+            parallel->isCenterAnchor = true;
+
+            for (int i = 0; i < constraints.count(); ++i) {
+                QSimplexConstraint *c = constraints[i];
+                if (c->variables.contains(child)) {
+                    childConstraints->append(c);
+                    qreal v = c->variables.take(child);
+                    c->variables.insert(parallel, v);
+                }
+            }
+        }
+
         // At this point we can identify that the parallel anchor is not feasible, e.g. one
         // anchor minimum size is bigger than the other anchor maximum size.
         *feasible = parallel->refreshSizeHints_helper(0, false);
         newAnchor = parallel;
     }
 
-    g->createEdge(newAnchor->from, newAnchor->to, newAnchor);
+    g.createEdge(newAnchor->from, newAnchor->to, newAnchor);
     return newAnchor;
 }
 
-
 /*!
     \internal
 
@@ -633,30 +702,185 @@ bool QGraphicsAnchorLayoutPrivate::simplifyGraph(Orientation orientation)
 
     if (graphSimplified[orientation])
         return true;
-    graphSimplified[orientation] = true;
 
 #if 0
     qDebug("Simplifying Graph for %s",
            orientation == Horizontal ? "Horizontal" : "Vertical");
 #endif
 
-    if (!layoutFirstVertex[orientation])
-        return true;
+    // Vertex simplification
+    if (!simplifyVertices(orientation)) {
+        restoreVertices(orientation);
+        return false;
+    }
 
+    // Anchor simplification
     bool dirty;
     bool feasible = true;
     do {
         dirty = simplifyGraphIteration(orientation, &feasible);
     } while (dirty && feasible);
 
-    if (!feasible)
-        graphSimplified[orientation] = false;
+    // Note that if we are not feasible, we fallback and make sure that the graph is fully restored
+    if (!feasible) {
+        graphSimplified[orientation] = true;
+        restoreSimplifiedGraph(orientation);
+        restoreVertices(orientation);
+        return false;
+    }
+
+    graphSimplified[orientation] = true;
+    return true;
+}
+
+static AnchorVertex *replaceVertex_helper(AnchorData *data, AnchorVertex *oldV, AnchorVertex *newV)
+{
+    AnchorVertex *other;
+    if (data->from == oldV) {
+        data->from = newV;
+        other = data->to;
+    } else {
+        data->to = newV;
+        other = data->from;
+    }
+    return other;
+}
+
+bool QGraphicsAnchorLayoutPrivate::replaceVertex(Orientation orientation, AnchorVertex *oldV,
+                                                 AnchorVertex *newV, const QList<AnchorData *> &edges)
+{
+    Graph<AnchorVertex, AnchorData> &g = graph[orientation];
+    bool feasible = true;
+
+    for (int i = 0; i < edges.count(); ++i) {
+        AnchorData *ad = edges[i];
+        AnchorVertex *otherV = replaceVertex_helper(ad, oldV, newV);
+
+#if defined(QT_DEBUG)
+        ad->name = QString::fromAscii("%1 --to--> %2").arg(ad->from->toString()).arg(ad->to->toString());
+#endif
+
+        bool newFeasible;
+        AnchorData *newAnchor = addAnchorMaybeParallel(ad, &newFeasible);
+        feasible &= newFeasible;
+
+        if (newAnchor != ad) {
+            // A parallel was created, we mark that in the list of anchors created by vertex
+            // simplification. This is needed because we want to restore them in a separate step
+            // from the restoration of anchor simplification.
+            anchorsFromSimplifiedVertices[orientation].append(newAnchor);
+        }
+
+        g.takeEdge(oldV, otherV);
+    }
 
     return feasible;
 }
 
 /*!
     \internal
+*/
+bool QGraphicsAnchorLayoutPrivate::simplifyVertices(Orientation orientation)
+{
+    Q_Q(QGraphicsAnchorLayout);
+    Graph<AnchorVertex, AnchorData> &g = graph[orientation];
+
+    // We'll walk through vertices
+    QStack<AnchorVertex *> stack;
+    stack.push(layoutFirstVertex[orientation]);
+    QSet<AnchorVertex *> visited;
+
+    while (!stack.isEmpty()) {
+        AnchorVertex *v = stack.pop();
+        visited.insert(v);
+
+        // Each adjacent of 'v' is a possible vertex to be merged. So we traverse all of
+        // them. Since once a merge is made, we might add new adjacents, and we don't want to
+        // pass two times through one adjacent. The 'index' is used to track our position.
+        QList<AnchorVertex *> adjacents = g.adjacentVertices(v);
+        int index = 0;
+
+        while (index < adjacents.count()) {
+            AnchorVertex *next = adjacents[index];
+            index++;
+
+            AnchorData *data = g.edgeData(v, next);
+            const bool bothLayoutVertices = v->m_item == q && next->m_item == q;
+            const bool zeroSized = !data->minSize && !data->maxSize;
+
+            if (!bothLayoutVertices && zeroSized) {
+
+                // Create a new vertex pair, note that we keep a list of those vertices so we can
+                // easily process them when restoring the graph.
+                AnchorVertexPair *newV = new AnchorVertexPair(v, next, data);
+                simplifiedVertices[orientation].append(newV);
+
+                // Collect the anchors of both vertices, the new vertex pair will take their place
+                // in those anchors
+                const QList<AnchorVertex *> &vAdjacents = g.adjacentVertices(v);
+                const QList<AnchorVertex *> &nextAdjacents = g.adjacentVertices(next);
+
+                for (int i = 0; i < vAdjacents.count(); ++i) {
+                    AnchorVertex *adjacent = vAdjacents[i];
+                    if (adjacent != next) {
+                        AnchorData *ad = g.edgeData(v, adjacent);
+                        newV->m_firstAnchors.append(ad);
+                    }
+                }
+
+                for (int i = 0; i < nextAdjacents.count(); ++i) {
+                    AnchorVertex *adjacent = nextAdjacents[i];
+                    if (adjacent != v) {
+                        AnchorData *ad = g.edgeData(next, adjacent);
+                        newV->m_secondAnchors.append(ad);
+
+                        // We'll also add new vertices to the adjacent list of the new 'v', to be
+                        // created as a vertex pair and replace the current one.
+                        if (!adjacents.contains(adjacent))
+                            adjacents.append(adjacent);
+                    }
+                }
+
+                // ### merge this loop into the ones that calculated m_firstAnchors/m_secondAnchors?
+                // Make newV take the place of v and next
+                bool feasible = replaceVertex(orientation, v, newV, newV->m_firstAnchors);
+                feasible &= replaceVertex(orientation, next, newV, newV->m_secondAnchors);
+
+                // Update the layout vertex information if one of the vertices is a layout vertex.
+                AnchorVertex *layoutVertex = 0;
+                if (v->m_item == q)
+                    layoutVertex = v;
+                else if (next->m_item == q)
+                    layoutVertex = next;
+
+                if (layoutVertex) {
+                    // Layout vertices always have m_item == q...
+                    newV->m_item = q;
+                    changeLayoutVertex(orientation, layoutVertex, newV);
+                }
+
+                g.takeEdge(v, next);
+
+                // If a non-feasibility is found, we leave early and cancel the simplification
+                if (!feasible)
+                    return false;
+
+                v = newV;
+                visited.insert(newV);
+
+            } else if (!visited.contains(next) && !stack.contains(next)) {
+                // If the adjacent is not fit for merge and it wasn't visited by the outermost
+                // loop, we add it to the stack.
+                stack.push(next);
+            }
+        }
+    }
+
+    return true;
+}
+
+/*!
+    \internal
 
     One iteration of the simplification algorithm. Returns true if another iteration is needed.
 
@@ -696,7 +920,8 @@ bool QGraphicsAnchorLayoutPrivate::simplifyGraphIteration(QGraphicsAnchorLayoutP
         // (a) it is a layout vertex, we don't simplify away the layout vertices;
         // (b) it does not have exactly 2 adjacents;
         // (c) it will change the direction of the sequence;
-        // (d) its next adjacent is already visited (a cycle in the graph).
+        // (d) its next adjacent is already visited (a cycle in the graph);
+        // (e) the next anchor is a center anchor.
 
         const QList<AnchorVertex *> &adjacents = g.adjacentVertices(v);
         const bool isLayoutVertex = v->m_item == q;
@@ -719,13 +944,14 @@ bool QGraphicsAnchorLayoutPrivate::simplifyGraphIteration(QGraphicsAnchorLayoutP
                 candidatesForward = (beforeSequence == data->from);
             }
 
-            // This is a tricky part. We peek at the next vertex to find out
+            // This is a tricky part. We peek at the next vertex to find out whether
             //
-            // - whether the edge from this vertex to the next vertex has the same direction;
-            // - whether we already visited the next vertex.
+            // - the edge from this vertex to the next vertex has the same direction;
+            // - we already visited the next vertex;
+            // - the next anchor is a center.
             //
-            // Those are needed to identify (c) and (d). Note that unlike (a) and (b), we preempt
-            // the end of sequence by looking into the next vertex.
+            // Those are needed to identify the remaining end of sequence cases. Note that unlike
+            // (a) and (b), we preempt the end of sequence by looking into the next vertex.
 
             // Peek at the next vertex
             AnchorVertex *after;
@@ -743,8 +969,8 @@ bool QGraphicsAnchorLayoutPrivate::simplifyGraphIteration(QGraphicsAnchorLayoutP
             const bool willChangeDirection = (candidatesForward != (v == data->from));
             const bool cycleFound = visited.contains(after);
 
-            // Now cases (c) and (d)...
-            endOfSequence = willChangeDirection || cycleFound;
+            // Now cases (c), (d) and (e)...
+            endOfSequence = willChangeDirection || cycleFound || data->isCenterAnchor;
 
             if (endOfSequence) {
                 if (!willChangeDirection) {
@@ -812,19 +1038,12 @@ bool QGraphicsAnchorLayoutPrivate::simplifyGraphIteration(QGraphicsAnchorLayoutP
         // Add the sequence to the graph.
         //
 
-        // ### At this point we assume that if some parallel anchor will be created because
-        // of the new sequence, the other anchor will not be a center anchor (since we
-        // not deal with that case yet). This assumption will break once we start simplifying
-        // vertices.
-        AnchorData *possibleParallel = g.edgeData(beforeSequence, afterSequence);
-        Q_ASSERT(!possibleParallel || !possibleParallel->isCenterAnchor);
-
         AnchorData *sequence = createSequence(&g, beforeSequence, candidates, afterSequence);
 
         // If 'beforeSequence' and 'afterSequence' already had an anchor between them, we'll
         // create a parallel anchor between the new sequence and the old anchor.
         bool newFeasible;
-        AnchorData *newAnchor = addAnchorMaybeParallel(&g, sequence, &newFeasible);
+        AnchorData *newAnchor = addAnchorMaybeParallel(sequence, &newFeasible);
 
         if (!newFeasible) {
             *feasible = false;
@@ -846,48 +1065,70 @@ bool QGraphicsAnchorLayoutPrivate::simplifyGraphIteration(QGraphicsAnchorLayoutP
     return false;
 }
 
-static void restoreSimplifiedAnchor(Graph<AnchorVertex, AnchorData> &g,
-                                    AnchorData *edge,
-                                    AnchorVertex *before,
-                                    AnchorVertex *after)
+void QGraphicsAnchorLayoutPrivate::restoreSimplifiedAnchor(AnchorData *edge)
 {
-    Q_ASSERT(edge->type != AnchorData::Normal);
 #if 0
     static const char *anchortypes[] = {"Normal",
                                         "Sequential",
                                         "Parallel"};
     qDebug("Restoring %s edge.", anchortypes[int(edge->type)]);
 #endif
-    if (edge->type == AnchorData::Sequential) {
-        SequentialAnchorData* seqEdge = static_cast<SequentialAnchorData*>(edge);
-        // restore the sequential anchor
-        AnchorVertex *prev = before;
-        AnchorVertex *last = after;
-        if (edge->from != prev)
-            qSwap(last, prev);
-
-        for (int i = 0; i < seqEdge->m_edges.count(); ++i) {
-            AnchorVertex *v1 = (i < seqEdge->m_children.count()) ? seqEdge->m_children.at(i) : last;
-            AnchorData *data = seqEdge->m_edges.at(i);
-            if (data->type != AnchorData::Normal) {
-                restoreSimplifiedAnchor(g, data, prev, v1);
-            } else {
-                g.createEdge(prev, v1, data);
-            }
-            prev = v1;
+
+    Graph<AnchorVertex, AnchorData> &g = graph[edge->orientation];
+
+    if (edge->type == AnchorData::Normal) {
+        g.createEdge(edge->from, edge->to, edge);
+
+    } else if (edge->type == AnchorData::Sequential) {
+        SequentialAnchorData *sequence = static_cast<SequentialAnchorData *>(edge);
+
+        for (int i = 0; i < sequence->m_edges.count(); ++i) {
+            AnchorData *data = sequence->m_edges.at(i);
+            restoreSimplifiedAnchor(data);
         }
+
+        delete sequence;
+
     } else if (edge->type == AnchorData::Parallel) {
-        ParallelAnchorData* parallelEdge = static_cast<ParallelAnchorData*>(edge);
-        AnchorData *parallelEdges[2] = {parallelEdge->firstEdge,
-                                        parallelEdge->secondEdge};
-        for (int i = 0; i < 2; ++i) {
-            AnchorData *data = parallelEdges[i];
-            if (data->type == AnchorData::Normal) {
-                g.createEdge(before, after, data);
-            } else {
-                restoreSimplifiedAnchor(g, data, before, after);
-            }
-        }
+
+        // Skip parallel anchors that were created by vertex simplification, they will be processed
+        // later, when restoring vertex simplification.
+        // ### we could improve this check bit having a bit inside 'edge'
+        if (anchorsFromSimplifiedVertices[edge->orientation].contains(edge))
+            return;
+
+        ParallelAnchorData* parallel = static_cast<ParallelAnchorData*>(edge);
+        restoreSimplifiedConstraints(parallel);
+
+        // ### Because of the way parallel anchors are created in the anchor simplification
+        // algorithm, we know that one of these will be a sequence, so it'll be safe if the other
+        // anchor create an edge between the same vertices as the parallel.
+        Q_ASSERT(parallel->firstEdge->type == AnchorData::Sequential
+                 || parallel->secondEdge->type == AnchorData::Sequential);
+        restoreSimplifiedAnchor(parallel->firstEdge);
+        restoreSimplifiedAnchor(parallel->secondEdge);
+
+        delete parallel;
+    }
+}
+
+void QGraphicsAnchorLayoutPrivate::restoreSimplifiedConstraints(ParallelAnchorData *parallel)
+{
+    if (!parallel->isCenterAnchor)
+        return;
+
+    for (int i = 0; i < parallel->m_firstConstraints.count(); ++i) {
+        QSimplexConstraint *c = parallel->m_firstConstraints[i];
+        qreal v = c->variables[parallel];
+        c->variables.remove(parallel);
+        c->variables.insert(parallel->firstEdge, v);
+    }
+
+    for (int i = 0; i < parallel->m_secondConstraints.count(); ++i) {
+        QSimplexConstraint *c = parallel->m_secondConstraints[i];
+        qreal v = c->variables[parallel];
+        c->variables.remove(parallel);
+        c->variables.insert(parallel->secondEdge, v);
     }
 }
 
@@ -902,19 +1143,93 @@ void QGraphicsAnchorLayoutPrivate::restoreSimplifiedGraph(Orientation orientatio
            orientation == Horizontal ? "Horizontal" : "Vertical");
 #endif
 
+    // Restore anchor simplification
     Graph<AnchorVertex, AnchorData> &g = graph[orientation];
-
     QList<QPair<AnchorVertex*, AnchorVertex*> > connections = g.connections();
     for (int i = 0; i < connections.count(); ++i) {
         AnchorVertex *v1 = connections.at(i).first;
         AnchorVertex *v2 = connections.at(i).second;
         AnchorData *edge = g.edgeData(v1, v2);
-        if (edge->type != AnchorData::Normal) {
-            AnchorData *oldEdge = g.takeEdge(v1, v2);
-            restoreSimplifiedAnchor(g, edge, v1, v2);
-            delete oldEdge;
+
+        // We restore only sequential anchors and parallels that were not created by
+        // vertex simplification.
+        if (edge->type == AnchorData::Sequential
+            || (edge->type == AnchorData::Parallel &&
+                !anchorsFromSimplifiedVertices[orientation].contains(edge))) {
+
+            g.takeEdge(v1, v2);
+            restoreSimplifiedAnchor(edge);
         }
     }
+
+    restoreVertices(orientation);
+}
+
+void QGraphicsAnchorLayoutPrivate::restoreVertices(Orientation orientation)
+{
+    Q_Q(QGraphicsAnchorLayout);
+
+    Graph<AnchorVertex, AnchorData> &g = graph[orientation];
+    QList<AnchorVertexPair *> &toRestore = simplifiedVertices[orientation];
+
+    // We will restore the vertices in the inverse order of creation, this way we ensure that
+    // the vertex being restored was not wrapped by another simplification.
+    for (int i = toRestore.count() - 1; i >= 0; --i) {
+        AnchorVertexPair *pair = toRestore[i];
+        QList<AnchorVertex *> adjacents = g.adjacentVertices(pair);
+
+        // Restore the removed edge, this will also restore both vertices 'first' and 'second' to
+        // the graph structure.
+        AnchorVertex *first = pair->m_first;
+        AnchorVertex *second = pair->m_second;
+        g.createEdge(first, second, pair->m_removedAnchor);
+
+        // Restore the anchors for the first child vertex
+        for (int j = 0; j < pair->m_firstAnchors.count(); ++j) {
+            AnchorData *ad = pair->m_firstAnchors[j];
+            Q_ASSERT(ad->from == pair || ad->to == pair);
+
+            replaceVertex_helper(ad, pair, first);
+            g.createEdge(ad->from, ad->to, ad);
+        }
+
+        // Restore the anchors for the second child vertex
+        for (int j = 0; j < pair->m_secondAnchors.count(); ++j) {
+            AnchorData *ad = pair->m_secondAnchors[j];
+            Q_ASSERT(ad->from == pair || ad->to == pair);
+
+            replaceVertex_helper(ad, pair, second);
+            g.createEdge(ad->from, ad->to, ad);
+        }
+
+        for (int j = 0; j < adjacents.count(); ++j) {
+            g.takeEdge(pair, adjacents[j]);
+        }
+
+        // The pair simplified a layout vertex, so place back the correct vertex in the variable
+        // that track layout vertices
+        if (pair->m_item == q) {
+            AnchorVertex *layoutVertex = first->m_item == q ? first : second;
+            Q_ASSERT(layoutVertex->m_item == q);
+            changeLayoutVertex(orientation, pair, layoutVertex);
+        }
+
+        delete pair;
+    }
+    toRestore.clear();
+
+    // The restoration process for vertex simplification also restored the effect of the
+    // parallel anchors created during vertex simplification, so we just need to restore
+    // the constraints in case of parallels that contain center anchors. For the same
+    // reason as above, order matters here.
+    QList<AnchorData *> &parallelAnchors = anchorsFromSimplifiedVertices[orientation];
+
+    for (int i = parallelAnchors.count() - 1; i >= 0; --i) {
+        ParallelAnchorData *parallel = static_cast<ParallelAnchorData *>(parallelAnchors[i]);
+        restoreSimplifiedConstraints(parallel);
+        delete parallel;
+    }
+    parallelAnchors.clear();
 }
 
 QGraphicsAnchorLayoutPrivate::Orientation
@@ -1068,7 +1383,6 @@ void QGraphicsAnchorLayoutPrivate::createCenterAnchors(
     if (item == q) {
         layoutCentralVertex[orientation] = internalVertex(q, centerEdge);
     }
-
 }
 
 void QGraphicsAnchorLayoutPrivate::removeCenterAnchors(
@@ -1730,6 +2044,15 @@ void QGraphicsAnchorLayoutPrivate::calculateGraphs(
     lastCalculationUsedSimplex[orientation] = false;
 #endif
 
+    // ### This is necessary because now we do vertex simplification, we still don't know
+    // differentiate between invalidate()s that doesn't need resimplification and those which
+    // need. For example, when size hint of an item changes, this may cause an anchor to reach 0 or to
+    // leave 0 and get a size. In both cases we need resimplify.
+    //
+    // ### one possible solution would be tracking all the 0-sized anchors, if this set change, we need
+    // resimplify.
+    restoreSimplifiedGraph(orientation);
+
     // Reset the nominal sizes of each anchor based on the current item sizes.  This function
     // works with both simplified and non-simplified graphs, so it'll work when the
     // simplification is going to be reused.
@@ -2298,6 +2621,21 @@ void QGraphicsAnchorLayoutPrivate::setItemsGeometries(const QRectF &geom)
 }
 
 /*!
+    \internal
+
+    Fill the distance in the vertex and in the sub-vertices if its a combined vertex.
+*/
+static void setVertexDistance(AnchorVertex *v, qreal distance)
+{
+    v->distance = distance;
+    if (v->m_type == AnchorVertex::Pair) {
+        AnchorVertexPair *pair = static_cast<AnchorVertexPair *>(v);
+        setVertexDistance(pair->m_first, distance);
+        setVertexDistance(pair->m_second, distance);
+    }
+}
+
+/*!
   \internal
 
   Calculate the position of each vertex based on the paths to each of
@@ -2312,7 +2650,7 @@ void QGraphicsAnchorLayoutPrivate::calculateVertexPositions(
     // Get root vertex
     AnchorVertex *root = layoutFirstVertex[orientation];
 
-    root->distance = 0;
+    setVertexDistance(root, 0);
     visited.insert(root);
 
     // Add initial edges to the queue
@@ -2336,7 +2674,7 @@ void QGraphicsAnchorLayoutPrivate::calculateVertexPositions(
             continue;
 
         visited.insert(pair.second);
-        interpolateEdge(pair.first, edge, orientation);
+        interpolateEdge(pair.first, edge);
 
         QList<AnchorVertex *> adjacents = graph[orientation].adjacentVertices(pair.second);
         for (int i = 0; i < adjacents.count(); ++i) {
@@ -2390,10 +2728,9 @@ void QGraphicsAnchorLayoutPrivate::setupEdgesInterpolation(
    vertices to be initalized, so it calls specialized functions that
    will recurse back to interpolateEdge().
  */
-void QGraphicsAnchorLayoutPrivate::interpolateEdge(AnchorVertex *base,
-                                                   AnchorData *edge,
-                                                   Orientation orientation)
+void QGraphicsAnchorLayoutPrivate::interpolateEdge(AnchorVertex *base, AnchorData *edge)
 {
+    const Orientation orientation = Orientation(edge->orientation);
     const QPair<Interval, qreal> factor(interpolationInterval[orientation],
                                         interpolationProgress[orientation]);
 
@@ -2402,24 +2739,21 @@ void QGraphicsAnchorLayoutPrivate::interpolateEdge(AnchorVertex *base,
 
     Q_ASSERT(edge->from == base || edge->to == base);
 
-    if (edge->from == base)
-        edge->to->distance = base->distance + edgeDistance;
-    else
-        edge->from->distance = base->distance - edgeDistance;
+    // Calculate the distance for the vertex opposite to the base
+    if (edge->from == base) {
+        setVertexDistance(edge->to, base->distance + edgeDistance);
+    } else {
+        setVertexDistance(edge->from, base->distance - edgeDistance);
+    }
 
     // Process child anchors
     if (edge->type == AnchorData::Sequential)
-        interpolateSequentialEdges(edge->from,
-                                   static_cast<SequentialAnchorData *>(edge),
-                                   orientation);
+        interpolateSequentialEdges(static_cast<SequentialAnchorData *>(edge));
     else if (edge->type == AnchorData::Parallel)
-        interpolateParallelEdges(edge->from,
-                                 static_cast<ParallelAnchorData *>(edge),
-                                 orientation);
+        interpolateParallelEdges(static_cast<ParallelAnchorData *>(edge));
 }
 
-void QGraphicsAnchorLayoutPrivate::interpolateParallelEdges(
-    AnchorVertex *base, ParallelAnchorData *data, Orientation orientation)
+void QGraphicsAnchorLayoutPrivate::interpolateParallelEdges(ParallelAnchorData *data)
 {
     // In parallels the boundary vertices are already calculate, we
     // just need to look for sequential groups inside, because only
@@ -2427,46 +2761,44 @@ void QGraphicsAnchorLayoutPrivate::interpolateParallelEdges(
 
     // First edge
     if (data->firstEdge->type == AnchorData::Sequential)
-        interpolateSequentialEdges(base,
-                                   static_cast<SequentialAnchorData *>(data->firstEdge),
-                                   orientation);
+        interpolateSequentialEdges(static_cast<SequentialAnchorData *>(data->firstEdge));
     else if (data->firstEdge->type == AnchorData::Parallel)
-        interpolateParallelEdges(base,
-                                 static_cast<ParallelAnchorData *>(data->firstEdge),
-                                 orientation);
+        interpolateParallelEdges(static_cast<ParallelAnchorData *>(data->firstEdge));
 
     // Second edge
     if (data->secondEdge->type == AnchorData::Sequential)
-        interpolateSequentialEdges(base,
-                                   static_cast<SequentialAnchorData *>(data->secondEdge),
-                                   orientation);
+        interpolateSequentialEdges(static_cast<SequentialAnchorData *>(data->secondEdge));
     else if (data->secondEdge->type == AnchorData::Parallel)
-        interpolateParallelEdges(base,
-                                 static_cast<ParallelAnchorData *>(data->secondEdge),
-                                 orientation);
+        interpolateParallelEdges(static_cast<ParallelAnchorData *>(data->secondEdge));
 }
 
-void QGraphicsAnchorLayoutPrivate::interpolateSequentialEdges(
-    AnchorVertex *base, SequentialAnchorData *data, Orientation orientation)
+void QGraphicsAnchorLayoutPrivate::interpolateSequentialEdges(SequentialAnchorData *data)
 {
-    AnchorVertex *prev = base;
+    // This method is supposed to handle any sequential anchor, even out-of-order
+    // ones. However, in the current QGAL implementation we should get only the
+    // well behaved ones.
+    Q_ASSERT(data->m_edges.first()->from == data->from);
+    Q_ASSERT(data->m_edges.last()->to == data->to);
 
-    // ### I'm not sure whether this assumption is safe. If not,
-    // consider that m_edges.last() could be used instead (so
-    // at(0) would be the one to be treated specially).
-    Q_ASSERT(base == data->m_edges.at(0)->to || base == data->m_edges.at(0)->from);
+    // At this point, the two outter vertices already have their distance
+    // calculated.
+    // We use the first as the base to calculate the internal ones
+
+    AnchorVertex *prev = data->from;
 
-    // Skip the last
     for (int i = 0; i < data->m_edges.count() - 1; ++i) {
-        AnchorData *child = data->m_edges.at(i);
-        interpolateEdge(prev, child, orientation);
-        prev = child->to;
+        AnchorData *edge = data->m_edges.at(i);
+        interpolateEdge(prev, edge);
+
+        // Use the recently calculated vertex as the base for the next one
+        const bool edgeIsForward = (edge->from == prev);
+        prev = edgeIsForward ? edge->to : edge->from;
     }
 
     // Treat the last specially, since we already calculated it's end
     // vertex, so it's only interesting if it's a complex one
     if (data->m_edges.last()->type != AnchorData::Normal)
-        interpolateEdge(prev, data->m_edges.last(), orientation);
+        interpolateEdge(prev, data->m_edges.last());
 }
 
 bool QGraphicsAnchorLayoutPrivate::solveMinMax(const QList<QSimplexConstraint *> &constraints,
diff --git a/src/gui/graphicsview/qgraphicsanchorlayout_p.h b/src/gui/graphicsview/qgraphicsanchorlayout_p.h
index 1e11ee2..3ef37f9 100644
--- a/src/gui/graphicsview/qgraphicsanchorlayout_p.h
+++ b/src/gui/graphicsview/qgraphicsanchorlayout_p.h
@@ -78,66 +78,30 @@ QT_BEGIN_NAMESPACE
   Represents a vertex (anchorage point) in the internal graph
 */
 struct AnchorVertex {
+    enum Type {
+        Normal = 0,
+        Pair
+    };
+
     AnchorVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge)
-        : m_item(item), m_edge(edge) {}
+        : m_item(item), m_edge(edge), m_type(Normal) {}
 
     AnchorVertex()
-        : m_item(0), m_edge(Qt::AnchorPoint(0)) {}
+        : m_item(0), m_edge(Qt::AnchorPoint(0)), m_type(Normal) {}
 
 #ifdef QT_DEBUG
     inline QString toString() const;
 #endif
+
     QGraphicsLayoutItem *m_item;
     Qt::AnchorPoint m_edge;
+    uint m_type : 1;
 
     // Current distance from this vertex to the layout edge (Left or Top)
     // Value is calculated from the current anchors sizes.
     qreal distance;
 };
 
-#ifdef QT_DEBUG
-inline QString AnchorVertex::toString() const
-{
-    if (!this || !m_item) {
-        return QLatin1String("NULL");
-    }
-    QString edge;
-    switch (m_edge) {
-    case Qt::AnchorLeft:
-        edge = QLatin1String("Left");
-        break;
-    case Qt::AnchorHorizontalCenter:
-        edge = QLatin1String("HorizontalCenter");
-        break;
-    case Qt::AnchorRight:
-        edge = QLatin1String("Right");
-        break;
-    case Qt::AnchorTop:
-        edge = QLatin1String("Top");
-        break;
-    case Qt::AnchorVerticalCenter:
-        edge = QLatin1String("VerticalCenter");
-        break;
-    case Qt::AnchorBottom:
-        edge = QLatin1String("Bottom");
-        break;
-    default:
-        edge = QLatin1String("None");
-        break;
-    }
-    QString itemName;
-    if (m_item->isLayout()) {
-        itemName = QLatin1String("layout");
-    } else {
-        if (QGraphicsItem *item = m_item->graphicsItem()) {
-            itemName = item->data(0).toString();
-        }
-    }
-    edge.insert(0, QLatin1String("%1_"));
-    return edge.arg(itemName);
-}
-#endif
-
 /*!
   \internal
 
@@ -256,10 +220,11 @@ struct ParallelAnchorData : public AnchorData
         type = AnchorData::Parallel;
         orientation = first->orientation;
 
-        // ### Those asserts force that both child anchors have the same direction,
-        // but can't we simplify a pair of anchors in opposite directions?
-        Q_ASSERT(first->from == second->from);
-        Q_ASSERT(first->to == second->to);
+        // This assert whether the child anchors share their vertices
+        Q_ASSERT(((first->from == second->from) && (first->to == second->to)) ||
+                 ((first->from == second->to) && (first->to == second->from)));
+
+        // We arbitrarily choose the direction of the first child as "our" direction
         from = first->from;
         to = first->to;
 #ifdef QT_DEBUG
@@ -274,8 +239,73 @@ struct ParallelAnchorData : public AnchorData
 
     AnchorData* firstEdge;
     AnchorData* secondEdge;
+
+    QList<QSimplexConstraint *> m_firstConstraints;
+    QList<QSimplexConstraint *> m_secondConstraints;
 };
 
+struct AnchorVertexPair : public AnchorVertex {
+    AnchorVertexPair(AnchorVertex *v1, AnchorVertex *v2, AnchorData *data)
+        : AnchorVertex(), m_first(v1), m_second(v2), m_removedAnchor(data) {
+        m_type = AnchorVertex::Pair;
+    }
+
+    AnchorVertex *m_first;
+    AnchorVertex *m_second;
+
+    AnchorData *m_removedAnchor;
+    QList<AnchorData *> m_firstAnchors;
+    QList<AnchorData *> m_secondAnchors;
+};
+
+#ifdef QT_DEBUG
+inline QString AnchorVertex::toString() const
+{
+    if (!this) {
+        return QLatin1String("NULL");
+    } else if (m_type == Pair) {
+        const AnchorVertexPair *vp = static_cast<const AnchorVertexPair *>(this);
+        return QString::fromAscii("(%1, %2)").arg(vp->m_first->toString()).arg(vp->m_second->toString());
+    } else if (!m_item) {
+        return QString::fromAscii("NULL_%1").arg(int(this));
+    }
+    QString edge;
+    switch (m_edge) {
+    case Qt::AnchorLeft:
+        edge = QLatin1String("Left");
+        break;
+    case Qt::AnchorHorizontalCenter:
+        edge = QLatin1String("HorizontalCenter");
+        break;
+    case Qt::AnchorRight:
+        edge = QLatin1String("Right");
+        break;
+    case Qt::AnchorTop:
+        edge = QLatin1String("Top");
+        break;
+    case Qt::AnchorVerticalCenter:
+        edge = QLatin1String("VerticalCenter");
+        break;
+    case Qt::AnchorBottom:
+        edge = QLatin1String("Bottom");
+        break;
+    default:
+        edge = QLatin1String("None");
+        break;
+    }
+    QString itemName;
+    if (m_item->isLayout()) {
+        itemName = QLatin1String("layout");
+    } else {
+        if (QGraphicsItem *item = m_item->graphicsItem()) {
+            itemName = item->data(0).toString();
+        }
+    }
+    edge.insert(0, QLatin1String("%1_"));
+    return edge.arg(itemName);
+}
+#endif
+
 /*!
   \internal
 
@@ -432,20 +462,33 @@ public:
 
     QLayoutStyleInfo &styleInfo() const;
 
-    // Activation methods
-    bool simplifyGraph(Orientation orientation);
-    bool simplifyGraphIteration(Orientation orientation, bool *feasible);
-    void restoreSimplifiedGraph(Orientation orientation);
+    AnchorData *addAnchorMaybeParallel(AnchorData *newAnchor, bool *feasible);
 
+    // Activation
     void calculateGraphs();
     void calculateGraphs(Orientation orientation);
 
+    // Simplification
+    bool simplifyGraph(Orientation orientation);
+    bool simplifyVertices(Orientation orientation);
+    bool simplifyGraphIteration(Orientation orientation, bool *feasible);
+
+    bool replaceVertex(Orientation orientation, AnchorVertex *oldV,
+                       AnchorVertex *newV, const QList<AnchorData *> &edges);
+
+
+    void restoreSimplifiedGraph(Orientation orientation);
+    void restoreSimplifiedAnchor(AnchorData *edge);
+    void restoreSimplifiedConstraints(ParallelAnchorData *parallel);
+    void restoreVertices(Orientation orientation);
+
     bool calculateTrunk(Orientation orientation, const GraphPath &trunkPath,
                         const QList<QSimplexConstraint *> &constraints,
                         const QList<AnchorData *> &variables);
     bool calculateNonTrunk(const QList<QSimplexConstraint *> &constraints,
                            const QList<AnchorData *> &variables);
 
+    // Support functions for calculateGraph()
     bool refreshAllSizeHints(Orientation orientation);
     void findPaths(Orientation orientation);
     void constraintsFromPaths(Orientation orientation);
@@ -465,6 +508,17 @@ public:
         return internalVertex(qMakePair(const_cast<QGraphicsLayoutItem *>(item), edge));
     }
 
+    inline void changeLayoutVertex(Orientation orientation, AnchorVertex *oldV, AnchorVertex *newV)
+    {
+        if (layoutFirstVertex[orientation] == oldV)
+            layoutFirstVertex[orientation] = newV;
+        else if (layoutCentralVertex[orientation] == oldV)
+            layoutCentralVertex[orientation] = newV;
+        else if (layoutLastVertex[orientation] == oldV)
+            layoutLastVertex[orientation] = newV;
+    }
+
+
     AnchorVertex *addInternalVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge);
     void removeInternalVertex(QGraphicsLayoutItem *item, Qt::AnchorPoint edge);
 
@@ -473,11 +527,9 @@ public:
 
     void calculateVertexPositions(Orientation orientation);
     void setupEdgesInterpolation(Orientation orientation);
-    void interpolateEdge(AnchorVertex *base, AnchorData *edge, Orientation orientation);
-    void interpolateSequentialEdges(AnchorVertex *base, SequentialAnchorData *edge,
-                                    Orientation orientation);
-    void interpolateParallelEdges(AnchorVertex *base, ParallelAnchorData *edge,
-                                  Orientation orientation);
+    void interpolateEdge(AnchorVertex *base, AnchorData *edge);
+    void interpolateSequentialEdges(SequentialAnchorData *edge);
+    void interpolateParallelEdges(ParallelAnchorData *edge);
 
     // Linear Programming solver methods
     bool solveMinMax(const QList<QSimplexConstraint *> &constraints,
@@ -510,6 +562,10 @@ public:
     AnchorVertex *layoutCentralVertex[2];
     AnchorVertex *layoutLastVertex[2];
 
+    // Combined anchors in order of creation
+    QList<AnchorVertexPair *> simplifiedVertices[2];
+    QList<AnchorData *> anchorsFromSimplifiedVertices[2];
+
     // Graph paths and constraints, for both orientations
     QMultiHash<AnchorVertex *, GraphPath> graphPaths[2];
     QList<QSimplexConstraint *> constraints[2];