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

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;