6 ms·

Cassowary – A Constraint Solving Toolkit

43 points by joubert 11y ago

runspired 11y ago
You should probably point out that this repo is a much better JS version: https://github.com/slightlyoff/cassowary.js/ https://github.com/slightlyoff/cassowary.js/
afsina 11y ago
There is also a Dart version: https://github.com/domokit/cassowary https://github.com/domokit/cassowary
malkia 11y ago
For python + qt version check enaml - https://github.com/nucleic/enaml https://github.com/nucleic/enaml - it was posted here from 28 days ago - https://news.ycombinator.com/item?id=9677375 https://news.ycombinator.com/item?id=9677375
Quequau 11y ago
I'm not really sure why we're talking about this now, as it's been some time since it's seen a major update and there are other more active projects now. In any case, I think the title is a bit vague and should more complete stated; such as: Cassowary - an incremental constraint solving toolkit for linear equation systems.
rurban 11y ago
You should use this nowadays: https://github.com/nucleic/kiwi https://github.com/nucleic/kiwi Kiwi is an implementation of the algorithm based on the seminal Cassowary paper. It is not a refactoring of the original C++ solver. Kiwi has been designed from the ground up to be lightweight and fast. Kiwi ranges from 10x to 500x faster than the original Cassowary solver with typical use cases gaining a 40x improvement. Memory savings are consistently > 5x.
- arximboldi 11y ago
  I had good experiences with this one too: https://github.com/Nocte-/rhea https://github.com/Nocte-/rhea
rimantas 11y ago
Since nobody mentioned it yet: iOS autolayout has its roots in Cassowary.
vdm 11y ago
The React Native people looked at this and stuck with Flexbox. https://twitter.com/nikitonsky/status/561941079038390273 https://twitter.com/nikitonsky/status/561941079038390273
bergie 11y ago
http://gridstylesheets.org/ http://gridstylesheets.org/ is built on Cassowary
arximboldi 11y ago
Here is an implementation for Qt/QML that we use at Ableton: https://github.com/AbletonAG/aqt-cassowary https://github.com/AbletonAG/aqt-cassowary Edit: Anyone interested in modern implementations and participating in the community of library implementers and users can check this website: http://overconstrained.io/ http://overconstrained.io/ :-)
saosebastiao 11y ago
I'm a huge fan of constraint programming, but everything I've read about layout problems makes me think that LP or MIP is a better fit for the domain. Solving systems of linear equalities and inequalities is what LP solvers do, and they've got decades of research into how to do it extremely fast. Most commercial solvers can solve systems with tens of millions of constraints in mere seconds. Is there a reason why cassowary took the constraint solver approach other than the fact that it is called constraint-based layout?
- ridiculous_fish 11y ago
  (I worked on autolayout at Apple) Cassowary is LP - it's just the Simplex method. Constraints become equalities and inequalities in the tableau, and the objective function is constructed from non-required ("best effort") constraints. The novel contribution from Cassowary is its incrementalism technique. It can add, remove, and edit constraints without having to re-solve the whole LP problem over again. So it's well suited for interactive applications. An example is dragging. You establish a constraint that sets the position of the dragged object, and then modify that constraint during the drag. Cassowary can re-use the old computation to solve the new one very efficiently.
  - saosebastiao 11y ago
    That's interesting! Is it using Lagrangian duality to do any sort of shadow pricing for incremental changes? I guess I should probably read the paper by now.
  - junkor 11y ago
    @ridiculous_fish: Hi, I just found that you are worked on autolayout, I have a little question about autolayout. There is a simple view as follow, a subView with some Constraints, they are all UILayoutPriorityRequired,when superview frame change, system will break the subView's height Constraint(300), but the top||bottom Constraint(30). they are all UILayoutPriorityRequired, why the system did things like this, and how does AutoLayout work (what's the calculate order? superView->subView->subviews'subview?),and where can I find the docs about this? :) |-----------------------------| | | | | 30 | | | | |-60-[subView(height:300)]-60-| | | | | 30 | | | | |-----------------------------| (maybe this case is not much suitable,because I should remove or change some constraints, I just want to use this case to explain the question)

43 points by joubert 11y ago

You should probably point out that this repo is a much better JS version: https://github.com/slightlyoff/cassowary.js/ https://github.com/slightlyoff/cassowary.js/

afsina 11y ago

There is also a Dart version: https://github.com/domokit/cassowary https://github.com/domokit/cassowary

malkia 11y ago

For python + qt version check enaml - https://github.com/nucleic/enaml https://github.com/nucleic/enaml - it was posted here from 28 days ago - https://news.ycombinator.com/item?id=9677375 https://news.ycombinator.com/item?id=9677375

Quequau 11y ago

I'm not really sure why we're talking about this now, as it's been some time since it's seen a major update and there are other more active projects now. In any case, I think the title is a bit vague and should more complete stated; such as: Cassowary - an incremental constraint solving toolkit for linear equation systems.

rurban 11y ago

You should use this nowadays: https://github.com/nucleic/kiwi https://github.com/nucleic/kiwi Kiwi is an implementation of the algorithm based on the seminal Cassowary paper. It is not a refactoring of the original C++ solver. Kiwi has been designed from the ground up to be lightweight and fast. Kiwi ranges from 10x to 500x faster than the original Cassowary solver with typical use cases gaining a 40x improvement. Memory savings are consistently > 5x.

arximboldi 11y ago
I had good experiences with this one too: https://github.com/Nocte-/rhea https://github.com/Nocte-/rhea

rimantas 11y ago

Since nobody mentioned it yet: iOS autolayout has its roots in Cassowary.

vdm 11y ago

The React Native people looked at this and stuck with Flexbox. https://twitter.com/nikitonsky/status/561941079038390273 https://twitter.com/nikitonsky/status/561941079038390273

bergie 11y ago

http://gridstylesheets.org/ http://gridstylesheets.org/ is built on Cassowary

arximboldi 11y ago

Here is an implementation for Qt/QML that we use at Ableton: https://github.com/AbletonAG/aqt-cassowary https://github.com/AbletonAG/aqt-cassowary Edit: Anyone interested in modern implementations and participating in the community of library implementers and users can check this website: http://overconstrained.io/ http://overconstrained.io/ :-)

saosebastiao 11y ago

I'm a huge fan of constraint programming, but everything I've read about layout problems makes me think that LP or MIP is a better fit for the domain. Solving systems of linear equalities and inequalities is what LP solvers do, and they've got decades of research into how to do it extremely fast. Most commercial solvers can solve systems with tens of millions of constraints in mere seconds. Is there a reason why cassowary took the constraint solver approach other than the fact that it is called constraint-based layout?

ridiculous_fish 11y ago
(I worked on autolayout at Apple) Cassowary is LP - it's just the Simplex method. Constraints become equalities and inequalities in the tableau, and the objective function is constructed from non-required ("best effort") constraints. The novel contribution from Cassowary is its incrementalism technique. It can add, remove, and edit constraints without having to re-solve the whole LP problem over again. So it's well suited for interactive applications. An example is dragging. You establish a constraint that sets the position of the dragged object, and then modify that constraint during the drag. Cassowary can re-use the old computation to solve the new one very efficiently.
- saosebastiao 11y ago
  That's interesting! Is it using Lagrangian duality to do any sort of shadow pricing for incremental changes? I guess I should probably read the paper by now.
- junkor 11y ago
  @ridiculous_fish: Hi, I just found that you are worked on autolayout, I have a little question about autolayout. There is a simple view as follow, a subView with some Constraints, they are all UILayoutPriorityRequired,when superview frame change, system will break the subView's height Constraint(300), but the top||bottom Constraint(30). they are all UILayoutPriorityRequired, why the system did things like this, and how does AutoLayout work (what's the calculate order? superView->subView->subviews'subview?),and where can I find the docs about this? :) |-----------------------------| | | | | 30 | | | | |-60-[subView(height:300)]-60-| | | | | 30 | | | | |-----------------------------| (maybe this case is not much suitable,because I should remove or change some constraints, I just want to use this case to explain the question)