Annotation of OpenXM_contrib/PHC/Ada/Root_Counts/Stalift/normal_cone_intersections.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 Arrays_of_Integer_Vector_Lists; use Arrays_of_Integer_Vector_Lists;
! 5:
! 6: package Normal_Cone_Intersections is
! 7:
! 8: -- DESCRIPTION :
! 9: -- This package provides a data abstraction to represent the intersections
! 10: -- of the generators of a normal cone with a tuple of normal cone complexes.
! 11:
! 12: -- DATA STRUCTURE :
! 13:
! 14: type Intersection_Matrix ( n,m,nc : natural ) is record
! 15: sv : Vector(1..n);
! 16: im : Matrix(0..m,1..nc);
! 17: end record;
! 18:
! 19: -- The aim of an intersection matrix is to answer the question :
! 20: -- does the ith generator of the normal cone of the point x
! 21: -- belong to the normal cone of the kth point of the jth support?
! 22:
! 23: -- The parameters of the three-dimensional intersection matrix are
! 24: -- n : number of supports to consider the point x to;
! 25: -- m : number of generators of the normal cone to x;
! 26: -- nc : total number of normal cones that need to be considered.
! 27:
! 28: -- The data of the intersection matrix are
! 29: -- sv(1..n) a vector whose entries indicates the starting position of the
! 30: -- the supports in the matrix im, i.e., sv(i) gives the first column in
! 31: -- the matrix im that collects the data of the normal cone of the first
! 32: -- points in the ith support;
! 33: -- im(0..m,1..nc) is a matrix that contains the answers to the question:
! 34: -- im(i,sv(j)+k) equals 0 or 1, 0 when the ith generator does not belong
! 35: -- to the normal cone of the kth points in the jth support, 1 otherwise;
! 36: -- im(0,sv(j)+k) is the sum of im(i,sv(j)+k) for all i in 1..m.
! 37:
! 38: -- CONSTRUCTORS :
! 39:
! 40: function Number_of_Cones ( l : Array_of_Lists; i : natural ) return natural;
! 41:
! 42: -- DESCRIPTION :
! 43: -- Computes the number of cones, i.e.: returns the sum of the lengths of
! 44: -- all lists of l, without consider the ith one.
! 45: -- This is an auxiliary for determining the third dimension of the
! 46: -- intersection matrix.
! 47:
! 48: function Lengths ( l : Array_of_Lists; i : natural ) return Vector;
! 49:
! 50: -- DESCRIPTION :
! 51: -- Returns a vector of dimension equal to l that accumulates the lengths
! 52: -- of the lists of l, without considering the ith component.
! 53: -- More precisely, the jth component of the vector on return equals
! 54: -- one plus the sum of all lengths of the lists in l(l'first..j),
! 55: -- minus the length of l(i), if i < j. So the vector on return can serve
! 56: -- as the vector sv, except for the last component that equals one plus
! 57: -- the total number of cones to consider.
! 58:
! 59: function Create ( l : Array_of_Lists; g : List; i : natural )
! 60: return Intersection_Matrix;
! 61:
! 62: -- DESCRIPTION :
! 63: -- Returns the intersection matrix of the list of generators of the normal
! 64: -- cone of a point that belongs to the list l(i).
! 65:
! 66: -- ELEMENTARY SELECTORS :
! 67:
! 68: function Is_In ( ima : Intersection_Matrix; i,j,k : natural ) return boolean;
! 69:
! 70: -- DESCRIPTION :
! 71: -- Returns true when the ith generator belongs to the normal cone of the
! 72: -- kth point of the jth support list.
! 73:
! 74: function Maximal_Column ( ima : Intersection_Matrix ) return natural;
! 75:
! 76: -- DESCRIPTION :
! 77: -- Returns the index to the column in the intersection matrix with
! 78: -- the maximal column sum.
! 79:
! 80: function Component ( ima : Intersection_Matrix; column : natural )
! 81: return natural;
! 82:
! 83: -- DESCRIPTION :
! 84: -- Returns the number of the component of the intersection matrix the
! 85: -- given column index corresponds to. The number on return equals the
! 86: -- index of the support of the corresponding column.
! 87:
! 88: function Length ( ima : Intersection_Matrix; i : natural ) return natural;
! 89:
! 90: -- DESCRIPTION :
! 91: -- Returns the length of the ith component of the matrix, i.e., returns
! 92: -- the length of the ith support list.
! 93:
! 94: function Row_Sum ( ima : Intersection_Matrix; i,j : natural ) return natural;
! 95:
! 96: -- DESCRIPTION :
! 97: -- Returns the sum of the elements on the ith row, for all normal cones
! 98: -- of the points of the jth support.
! 99:
! 100: -- ENUMERATING COMPLEMENTARY COLUMS :
! 101:
! 102: generic
! 103:
! 104: with procedure Process ( cols : in Vector; continue : out boolean );
! 105:
! 106: -- DESCRIPTION :
! 107: -- This procedure is invoked each time a set of complementary columns
! 108: -- has been found. The vector on return has the following meaning:
! 109: -- cols(i) = 0 means that no normal cone of the ith component is taken,
! 110: -- cols(i) = j means that the jth normal cone of the ith component
! 111: -- belongs to the complementary columns.
! 112: -- Note that the range of cols is 1..n-1, with n = #supports.
! 113:
! 114: procedure Complementary_Columns ( ima : in Intersection_Matrix );
! 115:
! 116: -- DESCRIPTION :
! 117: -- This procedure enumerates all complementary columns.
! 118: -- A set of columns, at most one of each component, is said to be
! 119: -- complementary if its union contains all generators of a normal cone.
! 120:
! 121: function Partition ( ima : Intersection_Matrix; cols : Vector; g : List )
! 122: return Array_of_Lists;
! 123:
! 124: -- DESCRIPTION :
! 125: -- Returns a partition of the set of generators g w.r.t. the columns cols
! 126: -- in the intersection matrix ima. More precisely: the ith list on return
! 127: -- contains those generators that belong to the normal cone cols(i) of the
! 128: -- ith component.
! 129: -- If the same generator belongs to several cones, it will be contained
! 130: -- only in the list with smallest index.
! 131:
! 132: -- REQUIRED : cols is a set of complementary columns.
! 133:
! 134: function Partition_in_Union ( partg,points : Array_of_Lists; i : natural;
! 135: cols : Vector ) return boolean;
! 136:
! 137: -- DESCRIPTION :
! 138: -- Returns true if the set of generators of a normal cones of the ith
! 139: -- component of the point lists belongs to the union of normal cones,
! 140: -- as indicated by the set of complementary columns.
! 141:
! 142: function Contained_in_Union
! 143: ( l : Array_of_Lists; i : natural; g : List;
! 144: ima : Intersection_Matrix; cols : Vector ) return boolean;
! 145:
! 146: -- DESCRIPTION :
! 147: -- Returns true if the list of generators g is contained in the normal
! 148: -- cones to the point selected by the columns of the intersection matrix.
! 149:
! 150: -- FINAL TARGET ROUTINE :
! 151:
! 152: function Contained_in_Union
! 153: ( l : Array_of_Lists; i : natural; g : List;
! 154: ima : Intersection_Matrix ) return boolean;
! 155:
! 156: -- DESCRIPTION :
! 157: -- Enumerates all sets of complementary columns, until its union
! 158: -- contains the convex cone spanned by the list of generators,
! 159: -- until all possibilities are exhausted.
! 160: -- In the first case, true is returned, otherwise false is returned.
! 161:
! 162: end Normal_Cone_Intersections;
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to normal_cone_intersections.ads CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / PHC / Ada / Root_Counts / Stalift