Return to inner_normal_cones.ads CVS log

Up to [local] / OpenXM_contrib / PHC / Ada / Root_Counts / Stalift

Annotation of OpenXM_contrib/PHC/Ada/Root_Counts/Stalift/inner_normal_cones.ads, Revision 1.1

1.1     ! maekawa     1: with Standard_Integer_Vectors;           use Standard_Integer_Vectors;
        !             2: with Standard_Integer_Matrices;          use Standard_Integer_Matrices;
        !             3: with Lists_of_Integer_Vectors;           use Lists_of_Integer_Vectors;
        !             4: with Integer_Faces_of_Polytope;          use Integer_Faces_of_Polytope;
        !             5:
        !             6: package Inner_Normal_Cones is
        !             7:
        !             8: -- DESCRIPTION :
        !             9: --   This package contains facilities for dealing with inner normal cones,
        !            10: --   that are cones normal to some faces of a given polytope, with apex
        !            11: --   at the origin.  Especially the normal cones to vertices are of great
        !            12: --   interest to determine which points contribute to the mixed volume.
        !            13: --   The primal representation of a normal cone consists in the generators
        !            14: --   of the cone.  A matrix of inequalities defines the dual representation.
        !            15:
        !            16: -- CONSTRUCTORS FOR PRIMAL REPRESENTATION :
        !            17:
        !            18:   function Generators ( l : List; facets : Faces; x : Vector ) return List;
        !            19:
        !            20:   -- DESCRIPTION :
        !            21:   --   Returns the generators of the polyhedral cone, which lies in the
        !            22:   --   dual space of the polytope spanned by l and is enclosed by the facets,
        !            23:   --   which all contain the vector x.
        !            24:   --   The list on return contains all inner normals to the facets.
        !            25:
        !            26:   function Generators ( l : List; x : Vector ) return List;
        !            27:
        !            28:   -- DESCRIPTION :
        !            29:   --   Returns the generators of the polyhedral cone to conv(l),
        !            30:   --   normal at the vector x.
        !            31:
        !            32: -- CONSTRUCTOR FOR DUAL REPRESENTATION :
        !            33:
        !            34:   function Inner_Normal_Cone ( l : List; x : Vector ) return Matrix;
        !            35:
        !            36:   -- DESCRIPTION :
        !            37:   --   Returns the inequalities that define the normal cone to the vector x,
        !            38:   --   normal to the polytope spanned by the points in l.
        !            39:   --   The range of the matrix on return is (x'range,1..Length_Of(l)-1),
        !            40:   --   which implies that the inequalities are stored columnwise.
        !            41:   --   The type of the inequalities is >= 0.
        !            42:
        !            43:   function Included_Normal_Cone ( gx : List; x : Vector ) return Matrix;
        !            44:
        !            45:   -- DESCRIPTION :
        !            46:   --   Returns the inequalities that define the inner normal cone to the
        !            47:   --   vector x, such that these normals are pointing in the interior of
        !            48:   --   the polytope spanned by l, when their basis is the point x.
        !            49:   --   The walls of this cone are the facets, the list gx should
        !            50:   --   contain all inner normal to the facets at the vertex x.
        !            51:
        !            52:   -- RANGE FORMATS :
        !            53:   --   The matrix on return has ranges (x'first-1..x'last,1..Length_Of(gx)).
        !            54:   --   The first row of the matrix contains <gx,x>,
        !            55:   --   to be used in the right-hand side of the inequalities.
        !            56:
        !            57: -- PRIMITIVE SELECTORS :
        !            58:
        !            59:   function Evaluate ( m : Matrix; i : integer; v : Vector ) return integer;
        !            60:
        !            61:   -- DESCRIPTION :
        !            62:   --   Evaluates the vector in the ith hyperplane of the inequality matrix.
        !            63:
        !            64:   function Satisfies ( m : Matrix; i : integer; v : Vector ) return boolean;
        !            65:   function Strictly_Satisfies ( m : Matrix; i : integer; v : Vector )
        !            66:                               return boolean;
        !            67:
        !            68:   -- DESCRIPTION :
        !            69:   --   Returns true if the vector v satisfies the ith inequality of the matrix.
        !            70:   --   With Strictly_ true is only returned if the evaluation yields a
        !            71:   --   positive result.
        !            72:
        !            73:   function Satisfies ( m : Matrix; v : Vector ) return boolean;
        !            74:   function Strictly_Satisfies ( m : Matrix; v : Vector ) return boolean;
        !            75:
        !            76:   -- DESCRIPTION :
        !            77:   --   Returns true if the vector v satisfies all inequalities defined by m.
        !            78:
        !            79:   function Satisfies ( m : Matrix; v : List ) return boolean;
        !            80:   function Strictly_Satisfies ( m : Matrix; v : List ) return boolean;
        !            81:
        !            82:   -- DESCRIPTION :
        !            83:   --   Returns true if all vectors in v satisfy all inequalities defined by m.
        !            84:
        !            85: -- SECONDARY SELECTORS :
        !            86:
        !            87:   function Satisfy ( m : Matrix; l : List ) return List;
        !            88:   function Strictly_Satisfy ( m : Matrix; l : List ) return List;
        !            89:
        !            90:   -- DESCRIPTION :
        !            91:   --   Returns a list of points from l that (strictly) satisfy the
        !            92:   --   inequalities in the matrix.
        !            93:
        !            94:   function Contained_in_Cone ( l : List; x : Vector; v : List ) return boolean;
        !            95:   function Strictly_Contained_in_Cone ( l : List; x : Vector; v : List )
        !            96:                                       return boolean;
        !            97:
        !            98:   -- DESCRIPTION :
        !            99:   --   Returns true when all vectors in v are contained in the normal cone
        !           100:   --   to the points in l, at the vector x.
        !           101:
        !           102:   function Contained_in_Cone ( l,v : List ) return boolean;
        !           103:   function Strictly_Contained_in_Cone ( l,v : List ) return boolean;
        !           104:
        !           105:   -- DESCRIPTION :
        !           106:   --   Returns true when there exists a normal cone to the points in l
        !           107:   --   that entirely contains the points in v.
        !           108:
        !           109: -- CONCERNING THE UNION OF CONES :
        !           110:
        !           111:   function In_Union ( v1,v2 : Vector; k1,k2 : Matrix ) return boolean;
        !           112:
        !           113:   -- DESCRIPTION :
        !           114:   --   Returns true if the convex combination of v1 and v2 is contained
        !           115:   --   in the union of the convex cones k1 and k2, given by their
        !           116:   --   inequality matrix.
        !           117:
        !           118:   -- REQUIRED : Satisfies(k1,v1) and Satisfies(k2,v2).
        !           119:
        !           120:   function In_Union ( v1,v2 : List; k1,k2 : Matrix ) return boolean;
        !           121:
        !           122:   -- DESCRIPTION :
        !           123:   --   Returns true if every convex combination of a vector from v1
        !           124:   --   and a vector from v2 is contained in the union of the convex
        !           125:   --   cones k1 and k2, given by their inequality matrix.
        !           126:
        !           127:   -- REQUIRED : Satisfies(k1,v1) and Satisfies(k2,v2).
        !           128:
        !           129: end Inner_Normal_Cones;