``An Incremental Algorithm for Satisfying Hierarchies of
Multi-way, Dataflow Constraints''
Bradley T. Vander Zanden
Appears in ACM Transactions on Programming Languages and Systems,
18(1), January 1996, pp. 30-72.
Available via anonymous ftp to cs.utk.edu in
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 multi-way
dataflow constraints 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
algorithms for satisfying constraint hierarchies encounter two
difficulties: (1) they are incapable of guaranteeing an acyclic
solution if a constraint hierarchy has one or more cyclic solutions,
and (2) they require worst-case exponential time to satisfy systems
of multi-output constraints. This paper surmounts these difficulties
by presenting an incremental algorithm called QuickPlan that satisfies
in worst case O(N^2))
time any hierarchy of multi-way, multi-output dataflow constraints
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 existing algorithms,
its performance is competitive or superior. With benchmarks and real
problems that cannot be solved using existing 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.