cassgowary

package module
v0.0.0-...-0b3bf43 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 24, 2018 License: BSD-3-Clause Imports: 9 Imported by: 0

README

cassgowary

Go implementation of Cassowary constraint solver

Solving constraint systems

Constraint solving systems are an algorithmic approach to solving Linear Programming problems. A linear programming problem is a mathematical problem where you have a set of non- negative, real valued variables (x[1], x[2], ... x[n]), and a series of linear constraints (i.e, no exponential Terms) on those variables. These constraints are expressed as a set of equations of the form:

``a[1]x[1] + ... + a[n]x[n] = b``,

``a[1]x[1] + ... + a[n]x[n] <= b``, or

``a[1]x[1] + ... + a[n]x[n] >= b``,

Given these constraints, the problem is to find the values of x[i] that minimize or maximize the value of an objective function:

``c + d[1]x[1] + ... + d[n]x[n]``

Cassowary is an algorithm designed to solve linear programming problems of this type. Published in 1997, it now forms the basis for the UI layout tools in OS X Lion, and iOS 6+ (the approach known as Auto Layout_). The Cassowary algorithm (and this implementation of it) provides the tools to describe a set of constraints, and then find an optimal solution for that set of constraints.

Auto Layout docs for iOS

Variables

At the core of the constraint problem are the variables in the system. In the formal mathematical system, these are the x[n] Terms; in Python, these are rendered as instances of the Variable class.

Each variable is named, and can accept a default value. To create a variable, instantiate an instance of Variable

from cassowary import Variable

# Create a variable with a default value.
x1 = Variable('x1')

# Create a variable with a specific value
x2 = Variable('x1', 42.0)

Any value provided for the variable is just a starting point. When constraints are imposed, this value can and will change, subject to the requirements of the constraints. However, providing an initial value may affect the search process; if there's an ambiguity in the constraints (i.e., there's more than one possible solution), the initial value provided to variables will affect the solution on which the system converges.

Constraints

A constraint is a mathematical equality or inequality that defines the linear programming system.

A constraint is declared by providing the Python expression that encompasses the logic described by the constraint. The syntax looks essentially the same as the raw mathematical expression::

from cassowary import Variable

# Create a variable with a default value.
x1 = Variable('x1')
x2 = Variable('x2')
x3 = Variable('x4')

# Define the constraint
constraint = x1 + 3 * x2 <= 4 * x3 + 2

In this example, constraint holds the definition for the constraint system. Although the statement uses the Python comparison operator <=, the result is not a boolean. The comparison operators <=, <, >=, >, and == have been overridden for instances of Variable to enable you to easily define constraints.

Solvers

The solver is the engine that resolves the linear constraints into a solution. There are many approaches to this problem, and the development of algorithmic approaches has been the subject of math and computer science research for over 70 years. Cassowary provides one implementation -- a :class:~cassowary.SimplexSolver, implementing the Simplex algorithm defined by Dantzig in the 1940s.

The solver takes no arguments during constructions; once constructed, you simply add constraints to the system.

As a simple example, let's solve the problem posed in Section 2 of the Badros & Borning's paper on Cassowary_. In this problem, we have a 1 dimensional number line spanning from 0 to 100. There are three points on it (left, middle and right), with the following constraints:

  • The middle point must be halfway between the left and right point;
  • The left point must be at least 10 to the left of the right point;
  • All points must fall in the range 0-100.

This system can be defined in Python as follows::

from cassowary import SimplexSolver, Variable

solver = SimplexSolver()

left = Variable('left')
middle = Variable('middle')
right = Variable('right')

solver.add_constraint(middle == (left + right) / 2)
solver.add_constraint(right == left + 10)
solver.add_constraint(right <= 100)
solver.add_constraint(left >= 0)

There are an infinite number of possible solutions to this system; if we interrogate the variables, you'll see that the solver has provided one possible solution::

>>> left.value
90.0
>>> middle.value
95.0
>>> right.value
100.0

Badros & Borning's paper on Cassowary

Stay constraints

If we want a particular solution to our left/right/middle problem, we need to fix a value somewhere. To do this, we add a Stay - a special constraint that says that the value should not be altered.

For example, we might want to enforce the fact that the middle value should stay at a value of 45. We construct the system as before, but add::

middle.value = 45.0
solver.add_stay(middle)

Now when we interrogate the solver, we'll get values that reflect this fixed point::

>>> left.value
40.0
>>> middle.value
45.0
>>> right.value
50.0

Constraint strength

Not all constraints are equal. Some are absolute requirements - for example, a requirement that all values remain in a specific range. However, other constraints may be suggestions, rather than hard requirements.

To accommodate this, Cassowary allows all constraints to have a strength. Strength can be one of:

  • Required
  • Strong
  • Medium
  • Weak

Required constraints must be satisfied; the remaining strengths will be satisfied with declining priority.

To define a strength, provide the strength value as an argument when adding the constraint (or stay)::

from cassowary import SimplexSolver, Variable, STRONG, WEAK

solver = SimplexSolver()
x = Variable('x')

# Define some non-required constraints
solver.add_constraint(x <= 100, strength=STRONG)
solver.add_stay(x, strength=WEAK)

Unless otherwise specified, all constraints are Required.

Constraint weight

If you have multiple constraints of the same strength, you may want to have a tie-breaker between them. To do this, you can set a weight, in addition to a strength::

from cassowary import SimplexSolver, Variable, Strong

solver = SimplexSolver()
x = Variable('x')

# Define some non-required constraints
solver.add_constraint(x <= 100, strength=STRONG, weight=10)
solver.add_constraint(x >= 50, strength=STRONG, weight=20)

Editing constraints

Any constraint can be removed from a system; just retain the reference provided when you add the constraint::

from cassowary import SimplexSolver, Variable

solver = SimplexSolver()
x = Variable('x')

# Define a constraint
constraint = solver.add_constraint(x <= 100)

# Remove it again
solver.remove_constraint(constraint)

Once a constraint is removed, the system will be automatically re-evaluated, with the possible side effect that the values in the system will change.

But what if you want to change a variable's value without introducing a new constraint? In this case, you can use an edit context.

Here's an example of an edit context in practice::

from cassowary import SimplexSolver, Variable

solver = SimplexSolver()
x = Variable('x')

# Add a stay to x - that is, don't change the value.
solver.add_stay(x)

# Now, mark x as being editable...
solver.add_edit_variable(x)

# ... start and edit context...
with solver.edit():
    # ... and suggest a new value for the variable.

    solver.suggest_value(x, 42.0)

When the edit context exits, the system will re-evaluate itself, and the variable will have the new value. However, the variable isn't guaranteed to have the value you suggested - in this case it will, but if your constraint system has other constraints, they may affect the value of the variable after the suggestion has been applied.

All variables in the system will be re-evaluated when you leave the edit context; however, if you need to force a re-evaluation in the middle of an edit context, you can do so by calling cassgowary.Solver.resolve().

Documentation

Index

Constants

View Source 
const Epsilon = 1.0e-12

Variables

View Source 
var (
	DuplicateConstraintErr     = constraintError("unsatisfiable constraint")
	DuplicateEditVariableErr   = errors.New("duplicate edit variable")
	InternalSolverErr          = errors.New("internal solver error")
	NonLinearExpressionErr     = errors.New("non-linear expression")
	RequiredFailureErr         = errors.New("required failure")
	UnknownConstraintErr       = constraintError("unknown constraint")
	UnknownEditVariableErr     = errors.New("unknown edit variable")
	UnsatisfiableConstraintErr = constraintError("unsatisfiable constraint")
)
View Source 
var (
	Required = CreateStrengthWithDefaultWeight(1000, 1000, 1000)
	Strong   = CreateStrengthWithDefaultWeight(1, 0, 0)
	Medium   = CreateStrengthWithDefaultWeight(0, 1, 0)
	Weak     = CreateStrengthWithDefaultWeight(0, 0, 1)
)
View Source 
var OperationFromString = map[string]RelationalOperator{
	"LEQ": OP_LE,
	"GEQ": OP_GE,
	"EQ":  OP_EQ,
}
View Source 
var OperationNames = map[RelationalOperator]string{
	OP_LE: "LEQ",
	OP_GE: "GEQ",
	OP_EQ: "EQ",
}

Functions

func FloatEquals 

func FloatEquals(f, other float64) bool

func FloatNearZero 

func FloatNearZero(f float64) bool

Types

type Constraint 

type Constraint struct {
	Strength Strength
	Op       RelationalOperator
	// contains filtered or unexported fields
}

func FloatEqualsExpression 

func FloatEqualsExpression(f float64, e *Expression) *Constraint

func FloatEqualsTerm 

func FloatEqualsTerm(f float64, t Term) *Constraint

func FloatEqualsVariable 

func FloatEqualsVariable(f float64, v *Variable) *Constraint

func FloatGreaterThanOrEqualToTerm 

func FloatGreaterThanOrEqualToTerm(f float64, t *Term) *Constraint

func FloatGreaterThanOrEqualToVariable 

func FloatGreaterThanOrEqualToVariable(f float64, v *Variable) *Constraint

func FloatLessThanOrEqualToExpression 

func FloatLessThanOrEqualToExpression(f float64, e *Expression) *Constraint

func FloatLessThanOrEqualToTerm 

func FloatLessThanOrEqualToTerm(f float64, t *Term) *Constraint

func FloatLessThanOrEqualToVariable 

func FloatLessThanOrEqualToVariable(f float64, v *Variable) *Constraint

func FloatModifyStrength 

func FloatModifyStrength(f float64, c *Constraint) *Constraint

func NewConstraint 

func NewConstraint(expr *Expression, op RelationalOperator, strength Strength) *Constraint

func NewConstraintFrom 

func NewConstraintFrom(other *Constraint, s Strength) *Constraint

func NewConstraintRequired 

func NewConstraintRequired(expr *Expression, op RelationalOperator) *Constraint

func (*Constraint) NewModifyStrength 

func (c *Constraint) NewModifyStrength(strength Strength) *Constraint

func (*Constraint) String 

func (c *Constraint) String() string

type ConstraintParser 

type ConstraintParser struct {
	// contains filtered or unexported fields
}

func NewConstraintParser 

func NewConstraintParser() *ConstraintParser

func (*ConstraintParser) ParseConstraint 

func (cp *ConstraintParser) ParseConstraint(rawConstraint string, variableResolver VariableResolver) (*Constraint, error)

type Expression 

type Expression struct {
	Terms    Terms
	Constant float64
}

func NewExpression 

func NewExpression(constant float64, terms ...*Term) *Expression

func NewExpressionFrom 

func NewExpressionFrom(terms ...*Term) *Expression

func (*Expression) Add 

func (e *Expression) Add(other *Expression) *Expression

func (*Expression) AddFloat 

func (e *Expression) AddFloat(constant float64) *Expression

func (*Expression) AddTerm 

func (e *Expression) AddTerm(t *Term) *Expression

func (*Expression) AddVariable 

func (e *Expression) AddVariable(v *Variable) *Expression

func (*Expression) Divide 

func (e *Expression) Divide(other *Expression) (*Expression, error)

func (*Expression) DivideFloat 

func (e *Expression) DivideFloat(denominator float64) *Expression

func (*Expression) Equals 

func (e *Expression) Equals(other *Expression) *Constraint

Expression relations

func (*Expression) EqualsFloat 

func (e *Expression) EqualsFloat(constant float64) *Constraint

func (*Expression) EqualsTerm 

func (e *Expression) EqualsTerm(t *Term) *Constraint

func (*Expression) EqualsVariable 

func (e *Expression) EqualsVariable(v *Variable) *Constraint

func (*Expression) GreaterThanOrEqualTo 

func (e *Expression) GreaterThanOrEqualTo(other *Expression) *Constraint

func (*Expression) GreaterThanOrEqualToFloat 

func (e *Expression) GreaterThanOrEqualToFloat(constant float64) *Constraint

func (*Expression) GreaterThanOrEqualToTerm 

func (e *Expression) GreaterThanOrEqualToTerm(t *Term) *Constraint

func (*Expression) GreaterThanOrEqualToVariable 

func (e *Expression) GreaterThanOrEqualToVariable(v *Variable) *Constraint

func (*Expression) IsConstant 

func (e *Expression) IsConstant() bool

func (*Expression) LessThanOrEqualTo 

func (e *Expression) LessThanOrEqualTo(other *Expression) *Constraint

func (*Expression) LessThanOrEqualToFloat 

func (e *Expression) LessThanOrEqualToFloat(constant float64) *Constraint

func (*Expression) LessThanOrEqualToTerm 

func (e *Expression) LessThanOrEqualToTerm(t *Term) *Constraint

func (*Expression) LessThanOrEqualToVariable 

func (e *Expression) LessThanOrEqualToVariable(v *Variable) *Constraint

func (*Expression) Multiply 

func (e *Expression) Multiply(other *Expression) (*Expression, error)

func (*Expression) MultiplyFloat 

func (e *Expression) MultiplyFloat(coefficient float64) *Expression

Expression multiply, divide, and unary invert

func (*Expression) Negate 

func (e *Expression) Negate() *Expression

func (*Expression) Reduce 

func (e *Expression) Reduce() *Expression

func (*Expression) String 

func (e *Expression) String() string

func (*Expression) Subtract 

func (e *Expression) Subtract(other *Expression) *Expression

func (*Expression) SubtractFloat 

func (e *Expression) SubtractFloat(constant float64) *Expression

func (*Expression) SubtractTerm 

func (e *Expression) SubtractTerm(t *Term) *Expression

func (*Expression) SubtractVariable 

func (e *Expression) SubtractVariable(v *Variable) *Expression

func (*Expression) Value 

func (e *Expression) Value() float64

type RelationalOperator 

type RelationalOperator int
const (
	OP_LE RelationalOperator = iota
	OP_GE
	OP_EQ
)

type Solver 

type Solver struct {
	// contains filtered or unexported fields
}

func NewSolver 

func NewSolver() *Solver

func (*Solver) AddConstraint 

func (s *Solver) AddConstraint(c *Constraint) error

AddConstraint adds a constraint to the solver.

func (*Solver) AddEditVariable 

func (s *Solver) AddEditVariable(v *Variable, strength Strength) error

func (*Solver) AddVariable 

func (s *Solver) AddVariable(name string)

func (*Solver) HasConstraint 

func (s *Solver) HasConstraint(c Constraint) bool

func (*Solver) HasEditVariable 

func (s *Solver) HasEditVariable(v *Variable) bool

func (*Solver) RemoveConstraint 

func (s *Solver) RemoveConstraint(c *Constraint) error

func (*Solver) RemoveEditVariable 

func (s *Solver) RemoveEditVariable(v *Variable) error

func (*Solver) SuggestValue 

func (s *Solver) SuggestValue(v Variable, value float64) error

func (*Solver) UpdateVariables 

func (s *Solver) UpdateVariables()

type Strength 

type Strength float64

func ClipStrength 

func ClipStrength(value Strength) Strength

func CreateStrength 

func CreateStrength(a, b, c, w float64) Strength

func CreateStrengthWithDefaultWeight 

func CreateStrengthWithDefaultWeight(a, b, c float64) Strength

type Term 

type Term struct {
	Variable    *Variable
	Coefficient float64
}

func NewTerm 

func NewTerm(v *Variable, coefficient float64) *Term

func NewTermFrom 

func NewTermFrom(variable *Variable) *Term

func (*Term) Add 

func (t *Term) Add(other *Term) *Expression

func (*Term) AddExpression 

func (t *Term) AddExpression(e *Expression) *Expression

func (*Term) AddFloat 

func (t *Term) AddFloat(constant float64) *Expression

func (*Term) AddVariable 

func (t *Term) AddVariable(v *Variable) *Expression

func (*Term) Divide 

func (t *Term) Divide(denominator float64) *Term

func (*Term) Equals 

func (t *Term) Equals(other *Term) *Constraint

func (*Term) EqualsExpression 

func (t *Term) EqualsExpression(e *Expression) *Constraint

func (*Term) EqualsFloat 

func (t *Term) EqualsFloat(constant float64) *Constraint

func (*Term) EqualsVariable 

func (t *Term) EqualsVariable(v *Variable) *Constraint

func (*Term) GreaterThanOrEqualTo 

func (t *Term) GreaterThanOrEqualTo(other *Term) *Constraint

func (*Term) GreaterThanOrEqualToExpression 

func (t *Term) GreaterThanOrEqualToExpression(e *Expression) *Constraint

func (*Term) GreaterThanOrEqualToFloat 

func (t *Term) GreaterThanOrEqualToFloat(constant float64) *Constraint

func (*Term) GreaterThanOrEqualToVariable 

func (t *Term) GreaterThanOrEqualToVariable(v *Variable) *Constraint

func (*Term) LessThanOrEqualTo 

func (t *Term) LessThanOrEqualTo(other *Term) *Constraint

func (*Term) LessThanOrEqualToExpression 

func (t *Term) LessThanOrEqualToExpression(e *Expression) *Constraint

func (*Term) LessThanOrEqualToFloat 

func (t *Term) LessThanOrEqualToFloat(constant float64) *Constraint

func (*Term) LessThanOrEqualToVariable 

func (t *Term) LessThanOrEqualToVariable(v *Variable) *Constraint

func (*Term) Multiply 

func (t *Term) Multiply(coefficient float64) *Term

func (*Term) Negate 

func (t *Term) Negate() *Term

func (*Term) String 

func (t *Term) String() string

func (*Term) Subtract 

func (t *Term) Subtract(other *Term) *Expression

func (*Term) SubtractExpression 

func (t *Term) SubtractExpression(e *Expression) *Expression

func (*Term) SubtractFloat 

func (t *Term) SubtractFloat(constant float64) *Expression

func (*Term) Value 

func (t *Term) Value() float64

type Terms 

type Terms []*Term

type Variable 

type Variable struct {
	Name  string
	Value float64
}

func NewVariable 

func NewVariable(name string) *Variable

func NewVariableWithValue 

func NewVariableWithValue(name string, value float64) *Variable

func (*Variable) Add 

func (v *Variable) Add(other *Variable) *Expression

func (*Variable) AddExpression 

func (v *Variable) AddExpression(e *Expression) *Expression

func (*Variable) AddFloat 

func (v *Variable) AddFloat(constant float64) *Expression

func (*Variable) AddTerm 

func (v *Variable) AddTerm(t *Term) *Expression

func (*Variable) Divide 

func (v *Variable) Divide(denominator float64) *Term

func (*Variable) Equals 

func (v *Variable) Equals(other *Variable) *Constraint

func (*Variable) EqualsExpression 

func (v *Variable) EqualsExpression(e *Expression) *Constraint

Variable relations

func (*Variable) EqualsFloat 

func (v *Variable) EqualsFloat(constant float64) *Constraint

func (*Variable) EqualsTerm 

func (v *Variable) EqualsTerm(t Term) *Constraint

func (*Variable) GreaterThanOrEqualTo 

func (v *Variable) GreaterThanOrEqualTo(other *Variable) *Constraint

func (*Variable) GreaterThanOrEqualToExpression 

func (v *Variable) GreaterThanOrEqualToExpression(e *Expression) *Constraint

func (*Variable) GreaterThanOrEqualToFloat 

func (v *Variable) GreaterThanOrEqualToFloat(constant float64) *Constraint

func (*Variable) GreaterThanOrEqualToTerm 

func (v *Variable) GreaterThanOrEqualToTerm(t Term) *Constraint

func (*Variable) LessThanOrEqualTo 

func (v *Variable) LessThanOrEqualTo(other *Variable) *Constraint

func (*Variable) LessThanOrEqualToExpression 

func (v *Variable) LessThanOrEqualToExpression(e *Expression) *Constraint

func (*Variable) LessThanOrEqualToFloat 

func (v *Variable) LessThanOrEqualToFloat(constant float64) *Constraint

func (*Variable) LessThanOrEqualToTerm 

func (v *Variable) LessThanOrEqualToTerm(t *Term) *Constraint

func (*Variable) Multiply 

func (v *Variable) Multiply(coefficient float64) *Term

Variable multiply, divide, and unary invert

func (*Variable) Negate 

func (v *Variable) Negate() *Term

func (*Variable) String 

func (v *Variable) String() string

func (*Variable) Subtract 

func (v *Variable) Subtract(other *Variable) *Expression

func (*Variable) SubtractExpression 

func (v *Variable) SubtractExpression(e *Expression) *Expression

func (*Variable) SubtractFloat 

func (v *Variable) SubtractFloat(constant float64) *Expression

func (*Variable) SubtractTerm 

func (v *Variable) SubtractTerm(t Term) *Expression

type VariableResolver 

type VariableResolver interface {
	ResolveVariable(name string) (*Variable, error)
	ResolveConstant(name string) (*Expression, error)
}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.