Return to integer_face_enumerators.ads CVS log

Up to [local] / OpenXM_contrib / PHC / Ada / Math_Lib / Supports

Annotation of OpenXM_contrib/PHC/Ada/Math_Lib/Supports/integer_face_enumerators.ads, Revision 1.1.1.1

1.1       maekawa     1: with Standard_Integer_Vectors;           use Standard_Integer_Vectors;
                      2: with Standard_Integer_VecVecs;           use Standard_Integer_VecVecs;
                      3:
                      4: package Integer_Face_Enumerators is
                      5:
                      6: -- DESCRIPTION :
                      7: --   This package contains procedures which allow the efficient
                      8: --   enumeration of all vertices, edges and k-faces of a polytope.
                      9: --   The polytope is spanned by a given vector of points in a general
                     10: --   dimensional space.
                     11: --   In addition, a procedure has been added for enumerating all
                     12: --   facets of a certain type of the sum of a tuple of polytopes.
                     13:
                     14:   generic
                     15:
                     16:     with procedure Process ( i : in integer; cont : out boolean );
                     17:
                     18:   procedure Enumerate_Vertices ( pts : in VecVec );
                     19:
                     20:   -- DESCRIPTION :
                     21:   --   The vector pts contains the points which span the polytope.
                     22:   --   The candidate vertices are enumerated in order of occurrence in pts.
                     23:   --   Each time a vertex has been found, the procedure Process is invoked,
                     24:   --   which returns then the entry of the vertex in pts.
                     25:   --   When cont is set to false, the enumeration stops.
                     26:
                     27:   generic
                     28:
                     29:     with procedure Process ( i,j : in integer; cont : out boolean );
                     30:
                     31:   procedure Enumerate_Edges ( pts : in VecVec );
                     32:
                     33:   -- DESCRIPTION :
                     34:   --   The vector pts contains the points which span the polytope.
                     35:   --   The candidate edges are enumerated in lexicographic order.
                     36:   --   Each time an edge has been found, the procedure Process is
                     37:   --   invoked, which returns the entries of the edge in pts.
                     38:   --   When cont is set to be false, the enumeration stops.
                     39:
                     40:   generic
                     41:
                     42:     with procedure Process ( i,j : in integer; cont : out boolean );
                     43:
                     44:   procedure Enumerate_Lower_Edges ( pts : in VecVec );
                     45:
                     46:   -- DESCRIPTION :
                     47:   --   Enumerates only the edges on the lower hull of the polytope.
                     48:
                     49:   generic
                     50:
                     51:     with procedure Process ( face : in Vector; cont : out boolean );
                     52:
                     53:     -- REQUIRED :
                     54:     --   The range of face must be 0..k.
                     55:
                     56:   procedure Enumerate_Faces ( k : in natural; pts : in VecVec );
                     57:
                     58:   -- DESCRIPTION :
                     59:   --   The vector pts contains the points which span the polytope.
                     60:   --   A k-face is a face spanned by k affine linearly independent points.
                     61:   --   The candidate k-faces are enumerated in lexicographic order.
                     62:   --   Each time an edge has been found, the procedure Process is
                     63:   --   invoked, which returns the entries of the k-face in pts.
                     64:   --   When cont is set to be false, the enumeration stops.
                     65:
                     66:   generic
                     67:
                     68:     with procedure Process ( face : in Vector; cont : out boolean );
                     69:
                     70:     -- REQUIRED :
                     71:     --   The range of face must be 0..k.
                     72:
                     73:   procedure Enumerate_Lower_Faces ( k : in natural; pts : in VecVec );
                     74:
                     75:   -- DESCRIPTION :
                     76:   --   Enumerates only the k-faces on the lower hull of the polytope.
                     77:
                     78:   generic
                     79:
                     80:     with procedure Process ( faces : in VecVec; cont : out boolean );
                     81:
                     82:     -- DESCRIPTION :
                     83:     --   The parameter faces has the following meaning:
                     84:     --   faces(i) contains the entries of points in pts which span
                     85:     --   the k-face of the ith polytope, with k = typ(i).
                     86:     --   When cont is set to false, the enumeration stops.
                     87:
                     88:   procedure Enumerate_Faces_of_Sum
                     89:                ( ind,typ : in vector; k : in natural; pts : in VecVec );
                     90:
                     91:   -- DESCRIPTION :
                     92:   --   Enumerates the points which span faces of a certain type
                     93:   --   of the polytope in lexicographic order.
                     94:
                     95:   -- ON ENTRY :
                     96:   --   ind       ind(i) indicates where the points of the ith polytope
                     97:   --             in the vector pts begin;
                     98:   --   typ       typ(i) contains the dimension k of the k-face of the ith
                     99:   --             polytope which spans the facet of the sum;
                    100:   --   k         sum of the entries in typ, must be less than
                    101:   --             or equal to the dimension of the space;
                    102:   --   pts       contains all points of the polytopes.
                    103:
                    104:   -- ON RETURN :
                    105:   --   Each time a face of the sum has been found, Process is invoked.
                    106:
                    107: end Integer_Face_Enumerators;