Package 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 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 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

      All Methods Instance Methods Abstract Methods 
      Modifier and Type Method 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.

    • 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.