Both Apple’s AutoLayout and Google’s new Constraint layout systems are based on the Casowary algorithm. Speaking with one of the Apple engineers that implemented AutoLayout for Apple, he told me that they chose this particular algorithm because of its ability to update a set of constraints independently without having to update every constraint on the view, something especially useful for mobile layouts where the user can move objects with their finger.
The original paper, re-published in 2002, details a linear arithmetic constraint solving algorithm that allows the user to specify linear equality and inequality constraints, that are either required or a preference. The constraint with the highest strength dominates constraints with a lower strength.
I assume you’ve used AutoLayout or Constraint layout before, and understand the concepts like constraint priority and content hugging and compression resistance priority – these are all things detailed in the Cassowary algorithm. There are four ways that constraint strengths can be compared:
One: A local comparator – Compare on a constraint-by-constraint basis
Two: A global comparator – Take some aggregate measure of the unsatisfied constraints of a given strength
Three: A predicate comparator: Whether we’re concerned only with whether a constraint is satisfied or not
Four: A metric comparator: How nearly satisfied a constraint is using an error function
Constraints can be expressed purely through linear programming. Let’s take a look at how the algorithm works by actually graphing a set of constraints.
Imagine I want to constraint a UITextField and a UILabel horizontally. Like the following:
To do this, I need to define a few constraints. Let’s say:
1. The text field must be at least twice the size of the button
2. The text field and the button must not exceed 300 points
3. The button must be at least 50 points wide
These three constraints are totally satisfiable with the Cassowary algorithm. We can start to graph these to get an idea of how the algorithm works. Let graph numbers 1 and 3:
What we’ve got here is two constraints set. Everything in the light red tint satisfies the set constraints. If we tried to build the interface now, the algorithm is going to encounter a problem whereby the constraints aren’t fully set. Because we’ve said the text field must be at least as wide as the width of the button * 2, we’ve created a maximisation function that has no upper limit. So the algorithm will see it’s at y = 100, x = 50, which satisfies the two constraints we’ve set. But we defined a maximisation function, the algorithm will try to grow the y axis as much as it can. So it’ll get to y = 250, x = 125, which still satisfies the two set constraints. And it’ll keep going: y = 1500, x = 750? Still satisfies and it can go bigger so it will. y = 1,500,000,000, x = 7,500,000,000? Still satisfies the constraints, etc. It could go on forever. Luckily, the cassowary algorithm accounts for this possibility and prevents a situation like this by adding in its own constraint to set an upper limit. So we need one more constraint to constraint the upper bound. That’s where UITextField + UIButton <= 300 comes in:
Now we’ve added that final constraint, what will happen is that the UITextField >= 2UIButton constant will continue to be maximised until it gets to the point where maximising it further will break the UITextField + UIButton <= 300 constraint. So now we get the final results of y = 200, x = 100, which satisfies all three constraints. Notice also how the result is in the left corner of that triangle – most of the times the best fit for a set of given constraints will be in one of the corners like this.
JORDAN DIXON 