An incremental algorithm for satisfying hierarchies of multiway dataflow constraints

ABSTRACT

One-way dataflow constraints have gained popularity in many types of interactive systems because of their simplicity, efficiency, and manageability. Although it is widely acknowledged that multiway dataflow constraint could make it easier to specify certain relationships in these applications, concerns about their predictability and efficiency have impeded their acceptance. Constraint hierarchies have been developed to address the predictability problem, and incremental algorithms have been developed to address the efficiency problem. However, existing incremental alogrithms for satisfying constraint hierarchies encounter two difficulties : (1) they are incapable of guaranteeing an acylic solution if a constraint hierarchy has one or more cyclic solutions and (2) they require worst-case exponential time to satisfy systems of multioutput constriants. This article surmounts these difficulties by presenting an incremental algorithm called QuickPlan that satisfies in worst-case O(N2) time any hierarchy of multiway, multiout-put dataflow constraint that has at least one acyclic solution, where N is the number of constraints. With benchmarks and real problems that can be solved efficiently using exisitng algorithms, its performance is competitive or superior. With benchmarks and real problems that cannot be solved using exisitng algorithms or that cannot be solved efficiently, QuickPlan finds solutions and does so efficiently, typically in O(N) time or less. QuickPlan is based on the strategy of propagation of degrees of freedom. The only restriction it imposes is that every constraint method must use all of the variables in the constraint as either an input or an output variable. This requirement is met in every constraint-based, interactive application that we have developed or seen.

REFERENCES

• 1: Bowen Alpern , Roger Hoover , Barry K. Rosen , Peter F. Sweeney , F. Kenneth Zadeck, Incremental evaluation of computational circuits, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.32-42, January 22-24, 1990, San Francisco, California, United States
• 2: Paul S. Barth, An object-oriented approach to graphical interfaces, ACM Transactions on Graphics (TOG), v.5 n.2, p.142-172, April 1986 [doi>10.1145/22949.22951]
• 3: Alan Borning, The Programming Language Aspects of ThingLab, a Constraint-Oriented Simulation Laboratory, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.4, p.353-387, Oct. 1981 [doi>10.1145/357146.357147]
• 4: Alan Borning , Robert Duisberg, Constraint-based tools for building user interfaces, ACM Transactions on Graphics (TOG), v.5 n.4, p.345-374, Oct. 1986 [doi>10.1145/27623.29354]
• 5: Alan Borning , Robert Duisberg , Bjorn Freeman-Benson , Axel Kramer , Michael Woolf, Constraint hierarchies, Conference proceedings on Object-oriented programming systems, languages and applications, p.48-60, October 04-08, 1987, Orlando, Florida, United States
• 6: Alan Borning , Bjorn Freeman-Benson , Molly Wilson, Constraint hierarchies, Lisp and Symbolic Computation, v.5 n.3, p.223-270, Sept. 1992 [doi>10.1007/BF01807506]
• 7: BORNING, A., MAHER, M., MARTINDALE, A., AND WILSON, M. 1989. Constraint hierarchies and logic programming. In Proceedings of the 6th International Logic Programming Conference (Lisbon, Portugal). 149-164.
• 8: Jacques Cohen, Constraint logic programming languages, Communications of the ACM, v.33 n.7, p.52-68, July 1990 [doi>10.1145/79204.79209]
• 9: J. E. Dennis, Jr. , Robert B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Classics in Applied Mathematics, 16), Soc for Industrial & Applied Math, 1996
• 10: DINCBAS, M., HENTENRYCK, P. V., SIMONIS, H., AGGOUN, A., GRAF, T., AND BERTHEIR, F. 1988. The constraint logic programming language Chip. In Proceedings of the International Conference on Fifth Generation Computer Systems 1988. ICOT, Tokyo, 249-264.
• 11: Robert Adamy Duisberg, Constraint-based animation: temporal constraints in the animus system, 1986
• 12: Bjorn N. Freeman-Benson, Kaleidoscope: mixing objects, constraints, and imperative programming, Proceedings of the European conference on object-oriented programming on Object-oriented programming systems, languages, and applications, p.77-88, September 1990, Ottawa, Canada
• 13: Bjorn N. Freeman-Benson , John Maloney , Alan Borning, An incremental constraint solver, Communications of the ACM, v.33 n.1, p.54-63, Jan. 1990 [doi>10.1145/76372.77531]
• 14: GANGNET, M. AND ROSENBERG, B. 1992. Constraint programming and graph algorithms. In the 2nd International Symposium on Artificial Intelligence and Mathematics.
• 15: GLEICHER, M. AND WITKIN, A. 1991. Differential manipulation. In Proceedings of Graphics Interface. 61-67.
• 16: Michael Gleicher , Andrew Witkin, Through-the-lens camera control, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.331-340, July 1992
• 17: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 18: GOSLING, J. 1983. Algebraic constraints. Tech. Rep. CMU-(X-83-132, Computer Science Dept., Carnegie Mellon Univ., Pittsburgh, Pa.
• 19: Richard Helm , Tien Huynh , Catherine Lassez , Kim Marriot, A linear constraint technology for interactive graphic systems, Proceedings of the conference on Graphics interface '92, p.301-309, September 1992, Vancouver, British Columbia, Canada
• 20: Tyson R. Henry , Scott E. Hudson, Using active data in a UIMS, Proceedings of the 1st annual ACM SIGGRAPH symposium on User Interface Software, p.167-178, October 17-19, 1988, Alberta, Canada [doi>10.1145/62402.62429]
• 21: Ralph D. Hill, The Rendezvous constraint maintenance system, Proceedings of the 6th annual ACM symposium on User interface software and technology, p.225-234, December 1993, Atlanta, Georgia, United States [doi>10.1145/168642.168665]
• 22: Ralph D. Hill , Tom Brinck , Steven L. Rohall , John F. Patterson , Wayne Wilner, The Rendezvous architecture and language for constructing multiuser applications, ACM Transactions on Computer-Human Interaction (TOCHI), v.1 n.2, p.81-125, June 1994 [doi>10.1145/180171.180172]
• 23: R. Hoover, Incremental graph evaluation (attribute grammar), Cornell University, Ithaca, NY, 1987
• 24: Roger Hoover, Alphonse: incremental computation as a programming abstraction, ACM SIGPLAN Notices, v.27 n.7, p.261-272, July 1992
• 25: Scott E. Hudson, Incremental attribute evaluation: a flexible algorithm for lazy update, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.3, p.315-341, July 1991 [doi>10.1145/117009.117012]
• 26: Scott E. Hudson, User interface specification using an enhanced spreadsheet model, ACM Transactions on Graphics (TOG), v.13 n.3, p.209-239, July 1994 [doi>10.1145/195784.195787]
• 27: HUYNH, T., b%SEZ, C., AND LASSEZ, J.-L. 1992. Practical issues on the projection of polyhedral sets. Ann. Math. Artif. Zntell. 6, 295-316.
• 28: Joxan Jaffar , Spiro Michaylov , Peter J. Stuckey , Roland H. C. Yap, The CLP( R ) language and system, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.3, p.339-395, July 1992 [doi>10.1145/129393.129398]
• 29: LASSEZ, C. AND bSSEZ, J.-L. 1991. Quantifier elimination for conjunctions of linear constraints via a convex hull algorithm. Tech. Rep. Res. Rep. RC 16779, IBM.
• 30: Jean-Louis Lassez , Ken McAloon, A canonical form for generalized linear constraints, Journal of Symbolic Computation, v.13 n.1, p.1-24, Jan. 1992 [doi>10.1016/0747-7171(92)90002-L]
• 31: John Harold Maloney, Using constraints for user interface construction, University of Washington, Seattle, WA, 1992
• 32: Brad A. Myers, Creating user interfaces using programming by example, visual programming, and constraints, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.2, p.143-177, April 1990 [doi>10.1145/78942.78943]
• 33: Brad A. Myers , Dario A. Giuse , Roger B. Dannenberg , David S. Kosbie , Edward Pervin , Andrew Mickish , Brad Vander Zanden , Philippe Marchal, Garnet: Comprehensive Support for Graphical, Highly Interactive User Interfaces, Computer, v.23 n.11, p.71-85, November 1990 [doi>10.1109/2.60882]
• 34: Thomas Reps , Tim Teitelbaum , Alan Demers, Incremental Context-Dependent Analysis for Language-Based Editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.3, p.449-477, July 1983 [doi>10.1145/2166.357218]
• 35: William Joseph Rosener, Integrating multi-way and structural constraints into spreadsheet programming, University of Tennessee, Knoxville, TN, 1994
• 36: Michael John Sannella, Constraint satisfaction and debugging for interactive user interfaces, University of Washington, Seattle, WA, 1994
• 37: Michael Sannella, Skyblue: a multi-way local propagation constraint solver for user interface construction, Proceedings of the 7th annual ACM symposium on User interface software and technology, p.137-146, November 02-04, 1994, Marina del Rey, California, United States [doi>10.1145/192426.192485]
• 38: SANNELLA, M. AND BORNING, A. 1992. Multi-Garnet: Integrating multi-way constraints with Garnet. Tech. Rep. 92-07-01, Dept. of Computer Science and Engineering, University of Wash., Seattle, Wash. Sept.
• 39: Michael Sannella , John Maloney , Bjorn Freeman-Benson , Alan Borning, Multi-way versus one-way constraints in user interfaces: experience with the DeltaBlue algorithm, Software—Practice & Experience, v.23 n.5, p.529-566, May 1993 [doi>10.1002/spe.4380230507]
• 40: Vijay Anand Saraswat , Dana S. Scott, Concurrent constraint programming languages, 1989
• 41: STEELE, G. L., JR. 1980. The definition and implementation of a computer programming language based on constraints. Ph.D. thesis, Dept. of Computer Science, MIT, Boston, Mass.
• 42: SUTHERLAND, I. E. 1963. Sketchpad.: A man-machine graphical communication system. In the AFIPS Spring Joint Computer Conference. Vol. 23. AFIPS, Montvale, N.J., 329-346.
• 43: Pedro Szekely , Brad Myers, A user interface toolkit based on graphical objects and constraints, ACM SIGPLAN Notices, v.23 n.11, p.36-45, Nov. 1988
• 44: Bradley T. Vander Zanden, Incremental constraint satisfaction and its application to graphical interfaces, 1989
• 45: Bradley T. V Zanden, A Domain-Independent Algorithm for Incrementally Satisfying Multi-Way Constraints, University of Tennessee, Knoxville, TN, 1992
• 46: Brad V Zanden, An Incremental Algorithm for Satisfying Hierarchies of Multi-way, Dataflow Constraints, University of Tennessee, Knoxville, TN, 1995
• 47: Brad Vander Zanden , Brad A. Myers , Dario A. Giuse , Pedro Szekely, Integrating pointer variables into one-way constraint models, ACM Transactions on Computer-Human Interaction (TOCHI), v.1 n.2, p.161-213, June 1994 [doi>10.1145/180171.180174]
• 48: Andrew Witkin , Michael Gleicher , William Welch, Interactive dynamics, ACM SIGGRAPH Computer Graphics, v.24 n.2, p.11-21, Mar. 1990
• 49: WITKIN, A. AND WELCH, W. 1990. Fast animation and control of nonrigid structures. Comput. Graph. 24, 243-252.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: User interfaces

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Nonalgebraic algorithms
      I.1.3 Languages and Systems
          Subjects: Evaluation strategies

General Terms:
Algorithms, Design, Languages, Performance

Keywords:
constraints, incremental constraint satisfaction, interactive systems