martindevans / cassowary.net

An incremental constraint solver for .NET

Cassowary.net README

Cassowary.net [1] is a port of the Cassowary constraint solving toolkit [2] to the .NET platform. It is based on the Java version by Greg J. Badros, which in turn is based on the Smalltalk version by Alan Borning.

This fork of Cassowary.net initially began as a simple cleanup effort, refactoring the ported Java style code to a C# style of code. A new expression based constraint composition system has been added.

Nuget

The easiest way to use this fork is from the nuget package manager.

Status

I am not personally actively using this at the moment. I will accept PRs but I am unlikely to dedicate much time to fixing bugs. I would recommend using the far more powerful Z3 solver built by Microsoft instead. In my tests Z3 has shown itself to be generally faster than Cassowary at solving linear problems, whilst having the capacity to solve non-linear problems when required.

Composing Constraints

Creating complex constraints is very easy using the expression based extensions to the system:

var solver = new ClSimplexSolver();

solver.AddConstraint(a => a > 10);

This basic expression will create a constraint which operates on one variable, named "a", and adds a constraint that "a" must be greater than 10. Much more complex constraints than this can be created:

solver.AddConstraint((bl, br, wl, wr) => bl == wl && br == wr || br > 100);

Of course, it may not be convenient to include your variable names directly in your C# variable definitions, the above example is difficult to read because we have no idea what the definitions means. However if we rewrite it with meaningful names...

solver.AddConstraint((buttonLeft, buttonRight, windowLeft, windowRight) => buttonLeft == windowLeft && buttonRight == windowRight || buttonRight > 100);

...it becomes very long and tiresome. To solve this problem you can pass in your variable objects directly, and then bind them to temporary names:

var buttonLeft = new ClVariable("buttonLeft");
var buttonRight = new ClVariable("buttonRight");
var windowLeft = new ClVariable("windowLeft");
var windowRight = new ClVariable("windowRight");

solver.AddConstraint(
    buttonLeft, buttonRight, windowLeft, windowRight        // Pass in the variables here
    (bl, br, wl, wr) =>                                     // Bind them to temporary names in this expression
    bl == wl && br == wr || br > 100);                  // Define the constraints, using the temporary names
);

cassowary.net's Issues

ClSimplexSolverExtensions.AddConstraint (versions without variables as parameters) are recreating variables then called multiple times

ClSimplexSolverExtensions.AddConstraint (ones which do not receive variables as parameters) generating new variables each time they called.
I'm not sure is it intended behavior or not.

Example:

var solver = new ClSimplexSolver();
solver.AutoSolve = false;

var _L = new ClVariable("L", 0);
var _R = new ClVariable("R", 500);

var _W = new ClVariable("W");

solver.AddStay(_L);
solver.AddStay(_R);

//solver.AddConstraint(
//    _L, _R, _W,
//    (L, R, W) => L + W == R
//);
solver.AddConstraint(
    (L, R, W) => L + W == R
);

solver.Solve();

Console.WriteLine(_W);

Output:
[W:0]

Expected output:
[W:500]

Description of the solver:

{Tableau:
[99971e14-f8d4-4d10-9bc6-c2d8dfc611bf:obj] <==> 1*[ep1:slack] + 1*[em1:slack] + 1*[ep2:slack] + 1*[em2:slack]
[L:0] <==> -1*[ep1:slack] + 1*[em1:slack]
[R:500] <==> 500 + -1*[ep2:slack] + 1*[em2:slack]
[W:500] <==> 500 + 1*[ep1:slack] + -1*[em1:slack] + -1*[ep2:slack] + 1*[em2:slack] + -1*[d1:dummy]

so, there is a W variable, but not the one I created. Also stays somehow survived.

Performance improvements

It is something I did in my branch, but it heavily altered, so, I can't just make a merge request:

I used AddDel test as performance test:

nCns = 5000;
nVars = 6000;
nResolves = 1;
Strong constraints
12 sec before changes

You can replace ClDouble with double. (in some methods you need to pass it by ref to make it work)
8 sec after that change

overriding ClAbstraitVariable's GtHashCode and Equal implementations with ones returning int variable id (according to profiler lib spends 97% of time looking in dictionaries with ClAbstraitVariable as a key)
7 sec

Replacing rows Dictionary with sparse array:
4 sec

Sparse array implementation I used is not scaleable unfortunately. It requires a dedicated field in key for each array.
Using sparse array for columns have no effect on performance.
The implementation I used:
https://github.com/krypt-lynx/Cassowary.net/blob/master/Cassowary/ClSparseArray.cs

Edit context variable not found

The following test (sent to me in an email) fails:

//Create a solver
var solver = new ClSimplexSolver();
var variable = new ClVariable(0f);

//Add a stay, indicating this var should stay at it's current value if possible
solver.AddStay(variable, ClStrength.Strong, 1);

const double EXPECTED_VALUE = 10.0;

//Suggest a value for the variable in an edit context
var editContext = solver.BeginEdit(variable);
editContext.SuggestValue(variable, EXPECTED_VALUE);
editContext.EndEdit();

//Assert that the value has changed to the suggested value
Assert.AreEqual(EXPECTED_VALUE, variable.Value);

KeyNotFoundException when editing stay variable

The following minimal sample raises a System.Collections.Generic.KeyNotFoundException

var value = new ClVariable("value", 0);

var solver = new ClSimplexSolver();

solver.AddStay(value, ClStrength.Strong);

solver.BeginEdit(value)
    .SuggestValue(value, 25)
    .EndEdit(); // <- Exception raised here

Full stack trace:

Test method PixUITests.LayoutSystem.LayoutConstraintSolverTests.TestMinimal threw exception: 
System.Collections.Generic.KeyNotFoundException: A chave fornecida não estava presente no dicionário.
    em System.Collections.Generic.Dictionary`2.get_Item(TKey key)
   em Cassowary.ClLinearExpression.AddVariable(ClAbstractVariable v, Double c, ClAbstractVariable subject, ClTableau solver)
   em Cassowary.ClSimplexSolver.RemoveConstraint(ClConstraint cn)
   em Cassowary.ClSimplexSolver.RemoveEditVar(ClVariable v)
   em Cassowary.ClSimplexSolver.RemoveEditVarsTo(Int32 n)
   em Cassowary.ClSimplexSolver.Cassowary.IEditContext.EndEdit()
   em PixUITests.LayoutSystem.LayoutConstraintSolverTests.TestMinimal()

Few questions

• how to do constraint priority in this implementation? I see ClStrength and ClSymbolicWeight, first requires second and ClSymbolicWeight requires 3 numbers to init. What are those numbers?
• I'm trying to wrap my head around and don't see solution yet: how to do nested constraints?
  For example: I have a view inside a view, and I need size of external view is constrained by one set of rules and internal one depends on size of external

Basically, I'm trying to understood it in terms of Apple's AutoLayout

Test PassingValueIntoConstructor_SetsValueProperty fails on non-English locale system

variable.ToString() outputs "[name:111,1]" (comma instead of period) on my system
Looks like this (not checked others yet) using system default locale instead of CultureInfo.InvariantCulture