[ENH] Cassowary

Alan Borning borning at cs.washington.edu
Thu May 24 22:51:35 UTC 2001


Hi all -

I have been working with Joshua to include some technical improvements in
his Squeak port of Cassowary.  They're now incorporated into the code.  We
thought it would be better for Joshua to keep the baton on the code, since
he's making various changes to integrate it better with Morphic.  It will
be really nice to have a generally-accessible version of Cassowary in
Squeak - embarrassingly, a couple of folks did ports in the past but we
never made them generally available.

The current version is at http://penguin.cc.gt.atl.ga.us:8080/schwa/63

Unfortunately it's quite slow right now - but Joshua is looking into this.
(It looks like the slowdown is on the graphics/drawing side, rather than
the constraint side, so it shouldn't be that hard to fix.)

To respond to a few of the points made in previous messages:

It's probably impossible to come up with a single constraint satisfaction
algorithm that's the right one for all situations: there are tradeoffs
between the class of constraints that can be solved, solver speed, and
completeness.  

So there are some good reasons to use a simpler solver, for example, a
one-way constraint solver, or a local propagation solver like DeltaBlue,
when the constraints can be solved that way.  

One-way constraints are the right thing when, for each constraint, there is
only one target variable that should be changed to keep the constraint
satisfied; and when there are no cycles in the constraint graph.  They are
fast and easy to understand. (Spreadsheets in effect use one-way constraints.)

Local propagation solvers are a good choice when each constraint uniquely
determines the value for each constrained variable given values for the
other variables, and again when there are no cycles.  An example of a
constraint that doesn't uniquely determine the value of each constrained
variable is an inequality: given a value for y, the constraint x<=y doesn't
give me a unique x.  An example of a cycle is a pair of simultaneous
equations, or harder, simultaneous inequalities.

Cassowary is a good choice if the constraints are linear.  It does just
fine with inequalities as well as equalities, simultaneous equality and
inequality constraints, and over- and underconstrained systems.

A couple of recent applications that we built using Cassowary were a
constraint-based window manager, and two web-related applications: an
extension to Cascading Style Sheets (Constraint Cascading Style Sheets),
and an extension to Structured Vector Graphics (Constraint Structured
Vector Graphics).  (Papers available from
www.cs.washington.edu/research/constraints)

You want a different solver (e.g. an iterative numeric one, or a geometric
solver) for nonlinear constraints, or where you want a least-squares
solution.  Boxes and glue, or spring models, find least-squares solutions
(or something close to a least-squares solution).

One approach to the issue of which is the right solver is to have a hybrid
solver that has different subsolvers for the different classes of
constraints - an example of this architecture is Ultraviolet:

  Alan Borning and Bjorn Freeman-Benson, "Ultraviolet: A Constraint
  Satisfaction Algorithm for Interactive Graphics," Constraints, Vol 3 No 1,
  April 1998.

Cheers,
Alan





More information about the Squeak-dev mailing list