A Polynomial Time Local Propagation Algorithm for General Datafow Constraint Problems

The multi-way dataflow constraint model allows a user to describe interactive applications whose consistency is maintained by a local propagation algorithm. Local propagation applies a sequence of methods that solve the constraints individually. The local aspect of this solving process makes this model sensitive to cycles in the constraint graph. We use a formalism which overcomes this major limitation by allowing the definition of general methods that can solve several constraints simultaneously. This paper presents an algorithm called General-PDOF to deal with these methods which has a polynomial worst case time complexity. This algorithm therefore has the potential to tackle numerous real-life applications where cycles make local propagation unfeasible. Especially, general methods can implement “ruler and compass” rules to solve geometric constraints.