User Interface Applications of a Multi-way Constraint Solver

T. Paul McCartney

Constraints are widely recognized as a useful tool for user interface construction. Through constraints, relationships among user interface components can be defined declaratively, leaving the task of relationship management to a constraint solver. Multi-way constraint solvers supporting constraint hierarchies provide a means to specify preferential constraint relationships with a dynamically changing computation flow, making them especially well suited to interactive user interfaces. However, previous such constraint solvers lack the ability to enforce inequalities or to effectively handle cyclic constraint relationships. These deficiencies limit the problems that could be solved using a constraint-based approach.

This paper presents a new algorithm called UltraBlue for solving hierarchies of multi-way constraints and discusses its application to the architecture of the EUPHORIA, user interface management system. Contributions of UltraBlue include a value consistency mechanism for maintaining arbitrary assertions (e.g., inequality relationships) and a cycle avoidance heuristic algorithm for eliminating cyclic constraint relationships. Cycles of constraints are resolved with respect to each constraint's relative strength, making it possible to construct acyclic constraint graphs that can be efficiently solved, while preferring constraints of greater importance.

KEYWORDS: constraints, constraint hierarchies, cycle avoidance, incremental constraint satisfaction, interactive techniques, multi-way constraints, user interface management system

Technical report version is available as postscript (.ps) or compressed postscript (.ps.Z).

Washington University Department of Computer Science WUCS-95-22, October 1995.

C++ source code for the UltraBlue algorithm v1.0 is available: uncompressed, compressed.

Prepared by T. Paul McCartney (paul@cs.wustl.edu)

Washington University Department of Computer Science