What is Auto Layout

Auto Layout is a constrained layout library that dynamically calculates the size and position of views and is integrated into the Xcode development environment. The following two points need to be noted.

  1. Cassorwary, the layout algorithm used by Auto Layout, was invented in 1997.
  2. In 2011, Apple applied Cassowary’s algorithm to its layout engine, Auto Layout

Life cycle of Autolayout

Auto Layout not only contains the Layout algorithm Casswory, but also includes a complete Layout engine system such as the runtime life cycle of the Layout, which agrees to manage the creation, update and destruction of the Layout.

This set of Layout Engine system is called Layout Engine, is the core of Auto Layout, leading the entire interface Layout.

Before each view gets its own Layout, the Layout Engine computates attempts, constraints, priorities, and fixed sizes into the final size and position. Each time a constraint changes, the Deffered Layout Pass is triggered and the constraint changes. When the constraint changes are listened for again, the next loop is entered. The process is shown below.




UIStackView

UIStackView is a container that determines the layout mode of the layout. Changes in the size of the container affect the layout of the children. Similar to a simplified version of flexbox in the front-end system.

  1. UIStackView is a virtual container, its layer is not drawn, setting the background, border, shadow and other appearance is invalid.
  2. If we use a constraint that does not define the stack view’s size, but only its position, the stack view will no longer change the size of the managed content, but it will automatically calculate its desired size, that is, become a run-away layout without line breaks. That is, an inherent size is generated for adaptive content typesetting.

Linear programming problem

Linear programming (LP) is an important branch of operations research, which is studied earlier, developed faster, widely used and has mature methods. LP is a mathematical method to assist people in scientific management. The mathematical theory and method of extremum problem of linear objective function under linear constraint are studied.

For example, the following is a linear programming problem:










Inequality groups can be listed:




This is a linear programming problem.

The feasible region

For an example, consider the following linear programming:




The following diagram can be drawn:




The gray area is called feasible region. It can be seen intuitively on the way that when X1 = 2 and x2 = 6, the maximum value is 8.

There’s a theorem here that you can prove that you always get a maximum at the intersection.

Standard form

The standard form is:

min        cT X
s.t.       A X <= b

Copy the code

Loose form

min        cT X

s.t.       A X = b
		   X >= 0
Copy the code

Note:

  1. All linear programs are of the form >= or <=, and the equals sign cannot be removed, otherwise there may be no solution.
  2. All of the above variables are column vectors, and cT represents the transpose matrix of C.
  3. Relaxation forms and relaxation variables are discussed later.
  4. Notice that the standard form is <=, min, if it’s the other way around, you just add a minus sign and you flip the inequality.

Simplex algorithm

The simplex method is a classical method for solving linear programs, and while its execution time is at worst non-polynomial (exponential time complexity), in most cases, or in the real world, it is polynomial time.

Steps:

  1. Find an initial basic feasible solution.
  2. Pivot operation is performed continuously.
  3. Repeat step 2 until the result cannot be improved.

sample

Consider the following linear programming problem:




The form after the relaxation variable is introduced:




Separating basic and non-basic variables:




Note: The ones on the right of the equals sign are called basic variables, and the ones on the left are called non-basic variables. That is, the relaxation variable introduced is the fundamental variable and the original variable is the non-fundamental variable.

Consider that the fundamental solution is, set the non-fundamental variable to 0, and compute the value of the fundamental variable on the left-hand side, which is easy to get here, the fundamental solution is :(0, 0, 0, 4, 2, 3, 6)T. In general, the fundamental solution works, and we call it the fundamental feasible solution (the non-feasible problem will be discussed later).

Now for the second step, the rotation operation:

Pick a non-basic variable Xe with negative coefficients in the objective function at a time, increase Xe as much as possible without violating the constraint, and pick the basic variable Xi, then swap them.

For example, we choose to substitute in variable X1 and out variable X5, and then replace the roles of both. The process of performing one rotation is equivalent to the linear programming described earlier. The replacement is as follows:




Similarly, the non-fundamental variable is set to 0, so the solution is :(2, 0, 0, 2, 0, 3, 6)T, and the value of the objective function is reduced to -2. If YOU keep going, you can only pick X2 or X3, you can’t pick X5, because the coefficient of X5 is positive. Assuming that variable X2 is selected and variable X4 is substituted, the following results will be obtained:




Continue to increase X5, select the strictest equation 4 for replacement, and get:




The fundamental solution becomes (2, 2, 0, 0, 0, 3, 0)T, and the target function is minus 30.

And then you can rotate X3, you omit it, and then you end up with a target of -32, because you’re running out of things to rotate, so you end up with a target of -32.

A special case

The degradation of

In the process of rotation, there may be a situation where the target value remains unchanged, which is called degeneration. For example, minus 30 appears twice in the example above. But there is no loop.

  1. In the target condition, the first one with a negative coefficient is used as the substitution variable.
  2. Of all constraints, select the first one closest to the XE constraint.
  3. Add a random perturbation.

unbounded

In the process of operation, there may be unbounded situations, which need to be paid attention to, for example, when two parallel lines are drawn

Matrix & program

For the example above:




We can obtain the following matrices:

C = (-1, -14, -6, 0, 0, 0, 0)

B = (4, 2, 3, 6)T

The < img style = "border - the radius: 0.3125 em." src="https://p6-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/20f1e8f4192a4b4ab499c1feab89a775~tplv-k3u1fbpfcp-zoom-1.image">Copy the code











Now we need to concatenate these matrices into a matrix:




You can see here that B is in the bottom left corner, C is in the top right corner, A is in the bottom right corner, and the number in the top left corner is -z.

You can see that if you rewrite this equation in terms of the fundamental variable equals F, B and C are the same, and the A matrix has the same fundamental variable sign, and the non-fundamental variable sign is the opposite.

Here, we take X1 and X5 and flip them to get the matrix as follows:




So how does this translate?

So first of all, row three, we need to rewrite it as X1 is equal to X5, which is really easy, just divide each of the elements in this row by the coefficients on X1.

And what about the other rows, the other rows are actually getting rid of X1, for example, the first row, and essentially making the coefficients of X1 the same as the coefficients of X1 in the third row. Let’s say I have row 1 times minus 1 minus row 3. Same thing for all the other lines.

So if you try it out here, the top left corner is actually -z, and you can see why.

You keep substituting and substituting until all the coefficients in the first row are positive.

Here we post the demo code so you can try it yourself:

import numpy as np class Simplex(object): def __init__(self, obj, max_mode=False): self.max_mode = max_mode self.mat = np.array([[0] + obj]) * (-1 if max_mode else 1) def add_constraint(self, a, b): self.mat = np.vstack([self.mat, [b] + a]) def solve(self): m, n = self.mat.shape temp, B = np.vstack([np.zeros((1, m - 1)), np.eye(m - 1)]), list(range(n - 1, n + m - 1)) # add diagonal array mat = self.mat = np.hstack([self.mat, temp]) while mat[0, 1:].min() < 0: col = np.where(mat[0, 1:] < 0)[0][0] + 1 row = np.array([mat[i][0] / mat[i][col] if mat[i][col] > 0 else 0x7fffffff for i in range(1, mat.shape[0])]).argmin() + 1 # find the theta index if mat[row][col] <= 0: return None mat[row] /= mat[row][col] ids = np.arange(mat.shape[0]) ! = row mat[ids] -= mat[row] * mat[ids, col:col + 1] B[row] = col return mat[0][0] * (1 if self.max_mode else -1), {B[i]: mat[i, 0] for i in range(1, m) if B[i] < n}Copy the code
from Simplex import Simplex
 
t = Simplex([-1, -14, -6])
t.add_constraint([1, 1, 1], 4)
t.add_constraint([1, 0, 0], 2)
t.add_constraint([0, 0, 1], 3)
t.add_constraint([0, 3, 1], 6)
print(t.solve())
print(t.mat)
Copy the code

Welcome to point out any mistakes in this article.

reference

  • [1] – [linear programming simplex algorithm explanation] www.hrwhisper.me/introductio…
  • [2] [Auto Layout is how to carry out automatic Layout, performance?] Time.geekbang.org/column/arti…
  • [3] [Solving Linear Arithmetic Constraints for User Interface Applications] constraints.cs.washington.edu/solvers/uis…