Package ptolemy.graph

Class InequalitySolver

  • public class InequalitySolver
extends java.lang.Object
    An algorithm to solve a set of inequality constraints. This algorithm is based on J. Rehof and T. Mogensen, "Tractable Constraints in Finite Semilattices," Third International Static Analysis Symposium, pp. 285-301, Vol 1145 of Lecture Notes in Computer Science, Springer, Sept., 1996.

    The algorithm in Rehof works for definite inequalities. This class does not enforce this requirement. However, if the inequalities are not definite, this solver may not be able to find the solution even when the set of inequalities is satisfiable. See the above paper for details.

    This solver supports finding both the least and greatest solutions (if they exist). It assumes that the CPO passed to the constructor is a lattice, but it does not verify it. If the algorithm finds that the LUB or GLB of some elements does not exist, an Exception is thrown.

    Since:
    Ptolemy II 0.2
    Version:
    $Id$
    Author:
    Yuhong Xiong
    Pt.AcceptedRating:
    Red (cxh)
    Pt.ProposedRating:
    Green (cxh)

    • Constructor Summary

      Constructors 
      Constructor Description
      InequalitySolver​(CPO cpo)
      Construct an inequality solver.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void addInequalities​(java.util.Iterator inequalities)
      Add a group of inequalities to the set of constraints.
      void addInequality​(Inequality ineq)
      Add an Inequality to the set of constraints.
      java.util.Iterator bottomVariables()
      Return an Iterator of the variables whose current values are the bottom of the underlying CPO.
      java.lang.String description()
      Return a description of this solver as a String.
      boolean solveGreatest()
      Solve the set of inequalities for the greatest solution.
      boolean solveLeast()
      Solve the set of inequalities for the least solution.
      java.util.Iterator topVariables()
      Return an Iterator of the variables whose current values are the top of the underlying CPO.
      java.util.Iterator unsatisfiedInequalities()
      Return an Iterator of Inequalities that are not satisfied with the current value of variables.
      java.util.Iterator variables()
      Return an Iterator of all the variables in the inequality constraints.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Constructor Detail

      • InequalitySolver

        public InequalitySolver​(CPO cpo)
        Construct an inequality solver.
        Parameters:
        cpo - The CPO over which the inequalities are defined.

    • Method Detail

      • addInequalities

        public void addInequalities​(java.util.Iterator inequalities)
        Add a group of inequalities to the set of constraints.
        Parameters:
        inequalities - An Iterator for instances of Inequality.

      • addInequality

        public void addInequality​(Inequality ineq)
        Add an Inequality to the set of constraints.
        Parameters:
        ineq - An Inequality.

      • bottomVariables

        public java.util.Iterator bottomVariables()
                                   throws IllegalActionException
        Return an Iterator of the variables whose current values are the bottom of the underlying CPO. If none of the variables have its current value set to the bottom, an empty Iterator is returned.
        Returns:
        An Iterator of InequalityTerms
        Throws:
        InvalidStateException - If the underlying CPO does not have a bottom element.
        IllegalActionException - If testing any one of the variables throws an exception.

      • description

        public java.lang.String description()
        Return a description of this solver as a String.
        Returns:
        A description of this solver.

      • solveGreatest

        public boolean solveGreatest()
                      throws IllegalActionException
        Solve the set of inequalities for the greatest solution. If the set of inequalities is definite (when solving for the greatest solution, definite means that the lesser terms of all the inequalities are either constants or single variables), this method can always determine satisfiability. In this case, if the set of inequalities is satisfiable, this method returns true, and the variables are set to the greatest solution. If the set of inequalities is not satisfiable, this method returns false.

        If the set of inequalities is not definite, this method cannot always determine satisfiability. In this case, if the set of inequalities is satisfiable, this method may or may not return true. If this method returns true, the variables are set to the greatest solution. If the set of inequalities is not satisfiable, this method returns false.

        In any case, if this method returns false, the variables are set to the greatest solution for the subset of inequalities whose lesser terms are a single variable. See the paper referred in the class document for details.

        Returns:
        True if a solution for the inequalities is found, false otherwise.
        Throws:
        IllegalActionException - If testing any one of the inequalities throws an exception.

      • solveLeast

        public boolean solveLeast()
                   throws IllegalActionException
        Solve the set of inequalities for the least solution. If the set of inequalities is definite (when solving for the least solution, definite means that the greater terms of all the inequalities are either constants or single variables), this method can always determine satisfiability. In this case, if the set of inequalities is satisfiable, this method returns true, and the variables are set to the least solution. If the set of inequalities is not satisfiable, this method returns false.

        If the set of inequalities is not definite, this method cannot always determine satisfiability. In this case, if the set of inequalities is satisfiable, this method may or may not return true. If this method returns true, the variables are set to the least solution. If the set of inequalities is not satisfiable, this method returns false.

        In any case, if this method returns false, the variables are set to the least solution for the subset of inequalities whose greater terms are a single variable. See the paper referred to in the class document for details.

        Returns:
        True if a solution for the inequalities is found, false otherwise.
        Throws:
        IllegalActionException - If testing any one of the inequalities throws an exception.

      • topVariables

        public java.util.Iterator topVariables()
                                throws IllegalActionException
        Return an Iterator of the variables whose current values are the top of the underlying CPO. If none of the variables have the current value set to the top, an empty Iterator is returned.
        Returns:
        An Iterator of InequalityTerms
        Throws:
        InvalidStateException - If the underlying CPO does not have a top element.
        IllegalActionException - If testing any one of the variables throws an exception.

      • unsatisfiedInequalities

        public java.util.Iterator unsatisfiedInequalities()
                                           throws IllegalActionException
        Return an Iterator of Inequalities that are not satisfied with the current value of variables. If all the inequalities are satisfied, an empty Iterator is returned.
        Returns:
        An Iterator of Inequalities
        Throws:
        IllegalActionException - If testing any one of the inequalities throws an exception.

      • variables

        public java.util.Iterator variables()
        Return an Iterator of all the variables in the inequality constraints.
        Returns:
        An Iterator of InequalityTerms