ptolemy.graph

## Class InequalitySolver

• java.lang.Object
• ptolemy.graph.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: InequalitySolver.java 69602 2014-07-30 14:20:15Z cxh \$
Author:
Yuhong Xiong
Accepted Rating:
 Red (cxh)
Proposed Rating:
 Green (cxh)
• ### Constructor Summary

Constructors
Constructor and Description
InequalitySolver(CPO cpo)
Construct an inequality solver.
• ### Method Summary

All Methods
Modifier and Type Method and Description
Add a group of inequalities to the set of constraints.
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

Add a group of inequalities to the set of constraints.
Parameters:
inequalities - An Iterator for instances of Inequality.

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