google/cassowary.dart

Cassowary constraint solving algorithm in Dart

Cassowary in Dart

This is an implementation of the Cassowary constraint solving algorithm in Dart. The initial implementation was based on the Kiwi toolkit written in C++. Implements a subset of the functionality described in the Cassowary paper and makes specific affordances for the needs of Flutter

The Solver

A solver is the object that accepts constraints and updates member variables in an attempt to satisfy the same.

Parameters

In order to create constraints, the user needs to take specific parameter objects vended by elements in the view hierarchy and create expression from these. Constraints can then be obtained from these expressions. If the solver needs to update these parameters to satisfy constraints, it will call callbacks on these parameters.

Constructing Constraints

A constraint is a linear equation of the form ax + by + cz + ... + k == 0. Constraints need not be equality relationships. Less/greater-than-or-equal-to (<= or >=) relationships can also be specified. In addition, each constraint is specified at a given priority to help resolve constraint ambiguities. A system can also be overconstrained.

The constraint as a whole is represented by an instance of the Constraint object. This in turn references an instance of an Expression (ax + by + cz + ... k), a realtionship and the finally the priority.

Each expression in turn is made up of a list of Terms and a constant. The term ax has the coefficient a and Variable x. The Param that is vended to the user is nothing but a wrapper for this variable and deals with detecting changes to it and updating the underlying view in the hierarchy.

Once the user obtains specific parameter objects, it is straightforward to create constraints. The following example sets up constraints that specify that the width of the element must be at least 100 units. It is assumed that the left and right Param objects have been obtained from the view in question.

var widthAtLeast100 = right - left >= cm(100.0);

Lets go over this one step at a time: The expression right - left creates an instance of an Expression object. The expression consists of two terms. The right and left params wrap variables. The coefficients are 1.0 and -1.0 respectively and the constant -100.0. Constants need to be decorated with CM to aid with the operator overloading mechanism in Dart.

All variables are unrestricted. So there is nothing preventing the solver from making the left and right edges negative. We can specify our preference against this by specifying another constraint like so:

var edgesPositive = (left >= cm(0.0));

When we construct these constraints for the solver, they are created at the default Priority.required. This means that the solver will resist adding constraints where there are ambiguities between two required constraints. To specify a weaker priority, you can use the priority setter or use the | symbol with the priority while constructing the constraint. Like so:

var edgesPositive = (left >= cm(0.0))..priority = Priority.weak;

Once the set of constraints are constructed, they are added to the solver and the results of the solution flushed out.

solver
    ..addConstraints([widthAtLeast100, edgesPositive])
    ..flushUpdates();

Edit Constraints

When updates need to be applied to parameters that are a part of the solver, edit variables may be used. To illustrate this, we try to express the following case in terms of constraints and their update: On mouse down, we want to update the midpoint of our view and have the left and right parameters automatically updated (subject to the constraints already setup).

We create a parameter that we will use to represent the mouse coordinate.

var mid = new Variable(coordinate);

Then, we add a constraint that expresses the midpoint in terms of the parameters we already have.

solver.addConstraint((left + right).equals(Term(mid, 1.0) * cm(2.0)));

Then, we specify that we intend to edit the midpoint. As we get updates, we tell the solver to satisfy all other constraints (admittedly our example is trivial).

solver.addEditVariable(mid, Priority.strong);

and finally

solver.flushUpdates();

cassowary.dart's Issues

What would active resizing constraints look like?

Hello, I've been exploring the library and it's been great, however I was wondering if I could get help building constraints for a specific case.

Imagine I make a box. It's easy to add constraints for a normal box, it would just look something like

[
        pos.top >= cm(0),
        pos.left >= cm(0),
        pos.right >= cm(0),
        pos.bottom >= cm(0),
        (pos.right).equals(pos.left + pos.w) | Priority.strong,
        (pos.bottom).equals(pos.top + pos.h) | Priority.strong,
        (pos.centerX).equals((pos.left + pos.right) / cm(2.0)) |
            Priority.strong,
        (pos.centerY).equals((pos.top + pos.bottom) / cm(2.0)) |
            Priority.strong,
      ];

This is just describing a solid box. I set the right/bottom/centerX/centerY to strong because other constraints may want to modify the size later on.

For translating the top and left position, we just do

[
      (pos.left).equals(bounds.left + cm(offset.dx)) | Priority.strong,
      (pos.top).equals(bounds.top + cm(offset.dy)) | Priority.strong,
]

This is making so if the offset x/y change, the left and top must change (theoretically)

Changing the width and height works well too, the right and bottom edges resize as needed and the top and left edges remain in place. This is because the constraints are satisfied well.

To get width/height to work, we add the following constraints:

[
    (pos.right).equals(pos.left + cm(width)) | Priority.required,
    (pos.bottom).equals(pos.top + cm(height)) | Priority.required,
]

This is making so if the width or height change, the right and bottom edges must change (theoretically).

The offset, width and height may change, when they do, the solver rebuilds the constraints with the updated values.

However, if you resize from the top left corner, or the top corner, or the left corner, you will translate the box instead of resize + change top/left. I expected the translation constraints to run, finish, then the sizing constraints to run, then finish, but clearly that's not what's happening. So I was wondering what flaw exists in my logic when thinking about this.

I wanted to translate, and then resize, not simutaeniously. Should I flush translation first then flush resize second to enforce an order?
My best guess is that Stays have not been implemented here and the solver is forcing the equation by changing the width and height variables, which are unused. Like if Stays existed, I would've set width/height to stayed values so they don't change.

Is the sample working as expected?

I tried the example in https://github.com/google/cassowary.dart/blob/master/example/main.dart .
I'm getting these results:

left: -0.0, right: 100.0
left: -50.0, mid: 0.0, right: 50.0

The first line of results looks ok.
However I don't understand why adding the midpoint Variable would change left to -50, therefore breaking the edgesPositive constraint.

I would have expected.

left: -0.0, mid: 50.0, right: 100.0

Maybe I'm missing something.

Log constraints for debug purpose

When I create a constraint and print it to logs I end up with something like:

+Instance of 'Variable' >= 0  | priority = 1000000000.0 (required)

This happens even after I set a name to the variable. Is there a way to get variable names when printing constraints?
I looked at the Variable class and toString() is not implemented.

[BUG] Can't remove unsatisfiable constraint

Reproducible example

    final a = Param();
    final b = Param();
    final c1 = a >= cm(10);
    final c2 = b <= cm(5);
    final c3 = b >= a;

    final solver = Solver();
    print('add c1 ${solver.addConstraint(c1).message}');
    print('add c2 ${solver.addConstraint(c2).message}');
    print('add c3 ${solver.addConstraint(c3).message}');
    print('remove c3 ${solver.removeConstraint(c3).message}');
    solver1.flushUpdates();
    print('vars a=${a.value} b=${b.value}');

Output

add c1 Success
add c2 Success
add c3 Unsatisfiable constraint
remove c3 Unknown constraint
vars a=10 b=10

Solver says "Unknown constraint" on removing c3 constraint, but c3 constraint has an impact on the solution.

problem discussion

Here's a description of my problem:

The customer has various walls of a fixed length, and hes want to efficiently dress them with segments of a material i have in fixed lengths (let's say lengths of a 2 meters and b 3 meters).
I have an unlimited supply of these components, but you I want to count how many of each component are to be used to fill the wall while minimizing waste.

Constraints:

• We care only about the length not the width or any other dimension either for the wall or the components.
• Wall Size: The walls lengths are known to us (e.g., 16 meters and 5 meters).
• Component and Segment Lengths: You have components with fixed lengths (let's say for example a) 2 meters and b) 3 meters). We can cut the a or b to a desired length. Generalise here the Components and their lengths are an input parameter.
• Waste : waste is considered to be the part of the component that is cut and the other part is never used. one part is used to fill the wall and the other is cosidered as discarded/waste.
• Objective: packing the entire walls with components and their segments.
• Objective: You need to keep track of the number of a and b components and their segments used to fill each wall.
• Objective: We must minimize waste while packing.

The goal is to find an arrangement of components and their segmenting on the wall that minimizes the number of segments used and counts how many of each segment length is used in each wall.

Do you think this solver help me solve my problem?