ptolemy.graph

Interface CPO<T>

All Known Implementing Classes:

ConceptGraph, DAGConceptGraph, DirectedAcyclicGraph, ProductLatticeCPO

public interface CPO<T>

An interface defining the operations on complete partial order (CPO). The definitions of these operations can be found in "Introduction to Lattices and Order," Cambridge University Press, 1990, by B. A. Davey and H. A. Priestley. Informal definitions are given in the code comments. Each element in the CPO is represented by an Object. For infinite CPOs, the result of some of the operations may be an infinite set, in which case, the class implementing those operations can throw an Exception.

Since:

Ptolemy II 0.2

Version:

$Id$

Author:

Yuhong Xiong

Pt.AcceptedRating:

Green (kienhuis)

Pt.ProposedRating:

Green (yuhong)

Nested Class Summary

Nested Classes

Modifier and Type	Interface and Description
static class	CPO.BoundType An enumeration type to represent the two different types of bounds that can be calculated on a set of nodes in a CPO; either a greatest lower bound or least upper bound.

Field Summary

Fields

Modifier and Type	Field and Description
static int	HIGHER One of the return values of compare, indicating that the first element is higher than the second.
static int	INCOMPARABLE One of the return values of compare, indicating that the two elements are incomparable.
static int	LOWER One of the return values of compare, indicating that the first element is lower than the second.
static int	SAME One of the return values of compare, indicating that the two elements are the same.

Method Summary

Modifier and Type	Method and Description
java.lang.Object	bottom() Return the bottom element of this CPO.
int	compare(java.lang.Object e1, java.lang.Object e2) Compare two elements in this CPO.
java.lang.Object[]	downSet(java.lang.Object e) Compute the down-set of an element in this CPO.
java.lang.Object	greatestElement(java.util.Set<T> subset) Compute the greatest element of a subset.
java.lang.Object	greatestLowerBound(java.lang.Object e1, java.lang.Object e2) Compute the greatest lower bound (GLB) of two elements.
T	greatestLowerBound(java.util.Set<T> subset) Compute the greatest lower bound (GLB) of a subset.
boolean	isLattice() Test if this CPO is a lattice.
java.lang.Object	leastElement(java.util.Set<T> subset) Compute the least element of a subset.
java.lang.Object	leastUpperBound(java.lang.Object e1, java.lang.Object e2) Compute the least upper bound (LUB) of two elements.
T	leastUpperBound(java.util.Set<T> subset) Compute the least upper bound (LUB) of a subset.
java.lang.Object	top() Return the top element of this CPO.
java.lang.Object[]	upSet(java.lang.Object e) Compute the up-set of an element in this CPO.

Field Detail

HIGHER

static final int HIGHER

One of the return values of compare, indicating that the first element is higher than the second.

See Also:

compare(java.lang.Object, java.lang.Object), Constant Field Values

INCOMPARABLE

static final int INCOMPARABLE

One of the return values of compare, indicating that the two elements are incomparable.

See Also:

compare(java.lang.Object, java.lang.Object), Constant Field Values

LOWER

static final int LOWER

One of the return values of compare, indicating that the first element is lower than the second.

See Also:

compare(java.lang.Object, java.lang.Object), Constant Field Values

SAME

static final int SAME

One of the return values of compare, indicating that the two elements are the same.

See Also:

compare(java.lang.Object, java.lang.Object), Constant Field Values

Method Detail

bottom

java.lang.Object bottom()

Return the bottom element of this CPO. The bottom element is the element in the CPO that is lower than all the other elements.

Returns:

An Object representing the bottom element, or null if the bottom does not exist.

compare

int compare(java.lang.Object e1,
            java.lang.Object e2)

Compare two elements in this CPO.

Parameters:

e1 - An Object representing a CPO element.

e2 - An Object representing a CPO element.

Returns:

One of CPO.LOWER, CPO.SAME, CPO.HIGHER, CPO.INCOMPARABLE.

Throws:

java.lang.IllegalArgumentException - If at least one of the specified Objects is not an element of this CPO.

downSet

java.lang.Object[] downSet(java.lang.Object e)

Compute the down-set of an element in this CPO. The down-set of an element is the subset consisting of all the elements lower than or the same as the specified element.

Parameters:

e - An Object representing an element in this CPO.

Returns:

An array of Objects representing the elements in the down-set of the specified element.

Throws:

java.lang.IllegalArgumentException - If the specified Object is not an element in this CPO, or the resulting set is infinite.

greatestElement

java.lang.Object greatestElement(java.util.Set<T> subset)

Compute the greatest element of a subset. The greatest element of a subset is an element in the subset that is higher than all the other elements in the subset.

Parameters:

subset - A set of Objects representing the subset.

Returns:

An Object representing the greatest element of the subset, or null if the greatest element does not exist.

Throws:

java.lang.IllegalArgumentException - If at least one Object in the specified array is not an element of this CPO.

greatestLowerBound

java.lang.Object greatestLowerBound(java.lang.Object e1,
                                    java.lang.Object e2)

Compute the greatest lower bound (GLB) of two elements. The GLB of two elements is the greatest element in the CPO that is lower than or the same as both of the two elements.

Parameters:

e1 - An Object representing an element in this CPO.

e2 - An Object representing an element in this CPO.

Returns:

An Object representing the GLB of the two specified elements, or null if the GLB does not exist.

Throws:

java.lang.IllegalArgumentException - If at least one of the specified Objects is not an element of this CPO.

greatestLowerBound

T greatestLowerBound(java.util.Set<T> subset)

Compute the greatest lower bound (GLB) of a subset. The GLB of a subset is the greatest element in the CPO that is lower than or the same as all the elements in the subset.

Parameters:

subset - A set of Objects representing the subset.

Returns:

An Object representing the GLB of the subset, or null if the GLB does not exist.

Throws:

java.lang.IllegalArgumentException - If at least one Object in the specified array is not an element of this CPO.

isLattice

boolean isLattice()

Test if this CPO is a lattice. A lattice is a CPO where the LUB and GLB of any pair of elements exist.

Returns:

True if this CPO is a lattice; false otherwise.

leastElement

java.lang.Object leastElement(java.util.Set<T> subset)

Compute the least element of a subset. The least element of a subset is an element in the subset that is lower than all the other element in the subset.

Parameters:

subset - A set of Objects representing the subset.

Returns:

An Object representing the least element of the subset, or null if the least element does not exist.

Throws:

java.lang.IllegalArgumentException - If at least one Object in the specified array is not an element of this CPO.

leastUpperBound

java.lang.Object leastUpperBound(java.lang.Object e1,
                                 java.lang.Object e2)

Compute the least upper bound (LUB) of two elements. The LUB of two elements is the least element in the CPO that is greater than or the same as both of the two elements.

Parameters:

e1 - An Object representing an element in this CPO.

e2 - An Object representing an element in this CPO.

Returns:

An Object representing the LUB of the two specified elements, or null if the LUB does not exist.

Throws:

java.lang.IllegalArgumentException - If at least one of the specified Objects is not an element of this CPO.

leastUpperBound

T leastUpperBound(java.util.Set<T> subset)

Compute the least upper bound (LUB) of a subset. The LUB of a subset is the least element in the CPO that is greater than or the same as all the elements in the subset.

Parameters:

subset - A set of Objects representing the subset.

Returns:

An Object representing the LUB of the subset, or null if the LUB does not exist.

Throws:

java.lang.IllegalArgumentException - If at least one Object in the specified array is not an element of this CPO.

top

java.lang.Object top()

Return the top element of this CPO. The top element is the element in the CPO that is higher than all the other elements.

Returns:

An Object representing the top element, or null if the top does not exist.

upSet

java.lang.Object[] upSet(java.lang.Object e)

Compute the up-set of an element in this CPO. The up-set of an element is the subset consisting of all the elements higher than or the same as the specified element.

Parameters:

e - An Object representing an element in this CPO.

Returns:

An array of Objects representing the elements in the up-set of the specified element.

Throws:

java.lang.IllegalArgumentException - If the specified Object is not an element of this CPO, or the resulting set is infinite.