Annotation of OpenXM_contrib/PHC/Ada/Root_Counts/Stalift/normal_cone_intersections.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 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