1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head><meta http-equiv="Content-Type" content="text/html;charset=UTF-8">
<title>polylib: ranking.c Source File</title>
<link href="doxygen.css" rel="stylesheet" type="text/css">
<link href="tabs.css" rel="stylesheet" type="text/css">
</head><body>
<!-- Generated by Doxygen 1.5.6 -->
<div class="navigation" id="top">
<div class="tabs">
<ul>
<li><a href="main.html"><span>Main Page</span></a></li>
<li><a href="annotated.html"><span>Classes</span></a></li>
<li class="current"><a href="files.html"><span>Files</span></a></li>
</ul>
</div>
<h1>ranking.c</h1><a href="ranking_8c.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 <span class="comment">/**</span>
<a name="l00002"></a>00002 <span class="comment"> * Tools to compute the ranking function of an iteration J: the number of</span>
<a name="l00003"></a>00003 <span class="comment"> * integer points in P that are lexicographically inferior to J </span>
<a name="l00004"></a>00004 <span class="comment"> * B. Meister</span>
<a name="l00005"></a>00005 <span class="comment"> * 6/2005</span>
<a name="l00006"></a>00006 <span class="comment"> * LSIIT-ICPS, UMR 7005 CNRS Universit Louis Pasteur</span>
<a name="l00007"></a>00007 <span class="comment"> * HiPEAC Network</span>
<a name="l00008"></a>00008 <span class="comment"> */</span>
<a name="l00009"></a>00009
<a name="l00010"></a>00010 <span class="preprocessor">#include <<a class="code" href="polylib_8h.html">polylib/polylib.h</a>></span>
<a name="l00011"></a>00011 <span class="preprocessor">#include <<a class="code" href="ranking_8h.html">polylib/ranking.h</a>></span>
<a name="l00012"></a>00012 <span class="comment"></span>
<a name="l00013"></a>00013 <span class="comment">/**</span>
<a name="l00014"></a>00014 <span class="comment"> * Returns a list of polytopes needed to compute</span>
<a name="l00015"></a>00015 <span class="comment"> * the number of points in P that are lexicographically</span>
<a name="l00016"></a>00016 <span class="comment"> * smaller than a given point in D.</span>
<a name="l00017"></a>00017 <span class="comment"> * Only the first dim dimensions are taken into account</span>
<a name="l00018"></a>00018 <span class="comment"> * for computing the lexsmaller relation.</span>
<a name="l00019"></a>00019 <span class="comment"> * The remaining variables are assumed to be extra</span>
<a name="l00020"></a>00020 <span class="comment"> * existential/control variables.</span>
<a name="l00021"></a>00021 <span class="comment"> * When P == D, this is the conventional ranking function.</span>
<a name="l00022"></a>00022 <span class="comment"> * P and D are assumed to have the same parameter domain C.</span>
<a name="l00023"></a>00023 <span class="comment"> *</span>
<a name="l00024"></a>00024 <span class="comment"> * The first polyhedron in the list returned is the</span>
<a name="l00025"></a>00025 <span class="comment"> * updated context: a combination of D and C or an extended C.</span>
<a name="l00026"></a>00026 <span class="comment"> *</span>
<a name="l00027"></a>00027 <span class="comment"> * The order of the variables in the remaining polyhedra is</span>
<a name="l00028"></a>00028 <span class="comment"> * - first dim variables of P</span>
<a name="l00029"></a>00029 <span class="comment"> * - existential variables of P</span>
<a name="l00030"></a>00030 <span class="comment"> * - existential variables of D</span>
<a name="l00031"></a>00031 <span class="comment"> * - first dim variables of D</span>
<a name="l00032"></a>00032 <span class="comment"> * - the parameters</span>
<a name="l00033"></a>00033 <span class="comment"> */</span>
<a name="l00034"></a><a class="code" href="ranking_8h.html#1bcb45db9576a3016be0eab5d32f4741">00034</a> <a class="code" href="structpolyhedron.html">Polyhedron</a> *<a class="code" href="ranking_8c.html#1bcb45db9576a3016be0eab5d32f4741" title="Tools to compute the ranking function of an iteration J: the number of integer points...">LexSmaller</a>(<a class="code" href="structpolyhedron.html">Polyhedron</a> *P, <a class="code" href="structpolyhedron.html">Polyhedron</a> *D, <span class="keywordtype">unsigned</span> dim,
<a name="l00035"></a>00035 <a class="code" href="structpolyhedron.html">Polyhedron</a> *C, <span class="keywordtype">unsigned</span> <a class="code" href="verif__ehrhart_8c.html#89fd83aa168651629c012d8655635588">MAXRAYS</a>)
<a name="l00036"></a>00036 {
<a name="l00037"></a>00037 <span class="keywordtype">unsigned</span> i, j, k, r;
<a name="l00038"></a>00038 <span class="keywordtype">unsigned</span> nb_parms = C-><a class="code" href="structpolyhedron.html#2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a>;
<a name="l00039"></a>00039 <span class="keywordtype">unsigned</span> nb_vars = dim;
<a name="l00040"></a>00040 <span class="keywordtype">unsigned</span> P_extra = P-><a class="code" href="structpolyhedron.html#2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a> - nb_vars - nb_parms;
<a name="l00041"></a>00041 <span class="keywordtype">unsigned</span> D_extra = D-><a class="code" href="structpolyhedron.html#2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a> - nb_vars - nb_parms;
<a name="l00042"></a>00042 <span class="keywordtype">unsigned</span> nb_new_parms;
<a name="l00043"></a>00043 <span class="keywordtype">unsigned</span> ncons;
<a name="l00044"></a>00044 <a class="code" href="structmatrix.html">Matrix</a> * cur_element, * C_times_J, * Klon;
<a name="l00045"></a>00045 <a class="code" href="structpolyhedron.html">Polyhedron</a> * P1, *C1;
<a name="l00046"></a>00046 <a class="code" href="structpolyhedron.html">Polyhedron</a> * lexico_lesser_union = NULL;
<a name="l00047"></a>00047
<a name="l00048"></a>00048 <a class="code" href="polyhedron_8h.html#54a764faf683e794f4db092c8d050104">POL_ENSURE_INEQUALITIES</a>(C);
<a name="l00049"></a>00049 <a class="code" href="polyhedron_8h.html#54a764faf683e794f4db092c8d050104">POL_ENSURE_INEQUALITIES</a>(D);
<a name="l00050"></a>00050 <a class="code" href="polyhedron_8h.html#54a764faf683e794f4db092c8d050104">POL_ENSURE_INEQUALITIES</a>(P);
<a name="l00051"></a>00051
<a name="l00052"></a>00052 <a class="code" href="assert_8h.html#07d17d6d5d1074c0969bc5d3c3d1d84a">assert</a>(P-><a class="code" href="structpolyhedron.html#2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a> >= C-><a class="code" href="structpolyhedron.html#2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a> + dim);
<a name="l00053"></a>00053 <a class="code" href="assert_8h.html#07d17d6d5d1074c0969bc5d3c3d1d84a">assert</a>(D-><a class="code" href="structpolyhedron.html#2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a> >= C-><a class="code" href="structpolyhedron.html#2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a> + dim);
<a name="l00054"></a>00054 nb_new_parms = nb_vars;
<a name="l00055"></a>00055
<a name="l00056"></a>00056 <span class="comment">/* the number of variables must be positive */</span>
<a name="l00057"></a>00057 <span class="keywordflow">if</span> (nb_vars<=0) {
<a name="l00058"></a>00058 printf(<span class="stringliteral">"\nRanking > No variables, returning NULL.\n"</span>);
<a name="l00059"></a>00059 <span class="keywordflow">return</span> NULL;
<a name="l00060"></a>00060 }
<a name="l00061"></a>00061 <span class="comment">/*</span>
<a name="l00062"></a>00062 <span class="comment"> * if D has extra variables, then we can't squeeze the contraints</span>
<a name="l00063"></a>00063 <span class="comment"> * of D in the new context, so we simply add them to each element.</span>
<a name="l00064"></a>00064 <span class="comment"> */</span>
<a name="l00065"></a>00065 <span class="keywordflow">if</span> (D_extra)
<a name="l00066"></a>00066 cur_element = <a class="code" href="matrix_8c.html#c0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(P-><a class="code" href="structpolyhedron.html#2db05293e731089b9198d45cf027bd1c">NbConstraints</a>+D-><a class="code" href="structpolyhedron.html#2db05293e731089b9198d45cf027bd1c">NbConstraints</a>+nb_new_parms,
<a name="l00067"></a>00067 P-><a class="code" href="structpolyhedron.html#2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a>+D_extra+nb_new_parms+2);
<a name="l00068"></a>00068 <span class="keywordflow">else</span>
<a name="l00069"></a>00069 cur_element = <a class="code" href="matrix_8c.html#c0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(P-><a class="code" href="structpolyhedron.html#2db05293e731089b9198d45cf027bd1c">NbConstraints</a>+nb_new_parms,
<a name="l00070"></a>00070 P-><a class="code" href="structpolyhedron.html#2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a>+D_extra+nb_new_parms+2);
<a name="l00071"></a>00071
<a name="l00072"></a>00072
<a name="l00073"></a>00073 <span class="comment">/* 0- Put P in the first rows of cur_element */</span>
<a name="l00074"></a>00074 <span class="keywordflow">for</span> (i=0; i < P-><a class="code" href="structpolyhedron.html#2db05293e731089b9198d45cf027bd1c">NbConstraints</a>; i++) {
<a name="l00075"></a>00075 <a class="code" href="vector_8c.html#b6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(P-><a class="code" href="structpolyhedron.html#b2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i], cur_element-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i], nb_vars+P_extra+1);
<a name="l00076"></a>00076 <a class="code" href="vector_8c.html#b6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(P-><a class="code" href="structpolyhedron.html#b2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i]+1+nb_vars+P_extra,
<a name="l00077"></a>00077 cur_element-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i]+1+nb_vars+P_extra+D_extra+nb_new_parms,
<a name="l00078"></a>00078 nb_parms+1);
<a name="l00079"></a>00079 }
<a name="l00080"></a>00080 ncons = P-><a class="code" href="structpolyhedron.html#2db05293e731089b9198d45cf027bd1c">NbConstraints</a>;
<a name="l00081"></a>00081 <span class="keywordflow">if</span> (D_extra) {
<a name="l00082"></a>00082 <span class="keywordflow">for</span> (i=0; i < D-><a class="code" href="structpolyhedron.html#2db05293e731089b9198d45cf027bd1c">NbConstraints</a>; i++) {
<a name="l00083"></a>00083 r = P-><a class="code" href="structpolyhedron.html#2db05293e731089b9198d45cf027bd1c">NbConstraints</a> + i;
<a name="l00084"></a>00084 <a class="code" href="vector_8c.html#b6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(D-><a class="code" href="structpolyhedron.html#b2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i], cur_element-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r], 1);
<a name="l00085"></a>00085 <a class="code" href="vector_8c.html#b6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(D-><a class="code" href="structpolyhedron.html#b2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i]+1,
<a name="l00086"></a>00086 cur_element-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r]+1+nb_vars+P_extra+D_extra, nb_new_parms);
<a name="l00087"></a>00087 <a class="code" href="vector_8c.html#b6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(D-><a class="code" href="structpolyhedron.html#b2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i]+1+nb_new_parms,
<a name="l00088"></a>00088 cur_element-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r]+1+nb_vars+P_extra, D_extra);
<a name="l00089"></a>00089 <a class="code" href="vector_8c.html#b6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(D-><a class="code" href="structpolyhedron.html#b2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i]+1+nb_new_parms+D_extra,
<a name="l00090"></a>00090 cur_element-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r]+1+nb_vars+P_extra+D_extra+nb_new_parms,
<a name="l00091"></a>00091 nb_parms+1);
<a name="l00092"></a>00092 }
<a name="l00093"></a>00093 ncons += D-><a class="code" href="structpolyhedron.html#2db05293e731089b9198d45cf027bd1c">NbConstraints</a>;
<a name="l00094"></a>00094 }
<a name="l00095"></a>00095
<a name="l00096"></a>00096 <span class="comment">/* 1- compute the Ehrhart polynomial of each disjoint polyhedron defining the</span>
<a name="l00097"></a>00097 <span class="comment"> lexicographic order */</span>
<a name="l00098"></a>00098 <span class="keywordflow">for</span> (k=0, r = ncons; k < nb_vars; k++, r++) {
<a name="l00099"></a>00099
<a name="l00100"></a>00100 <span class="comment">/* a- build the corresponding matrix</span>
<a name="l00101"></a>00101 <span class="comment"> * the nb of rows of cur_element is fake, so that we do not have to</span>
<a name="l00102"></a>00102 <span class="comment"> * re-allocate it. */</span>
<a name="l00103"></a>00103 cur_element-><a class="code" href="structmatrix.html#16ad614d15c6e81c0041e877b623c72d">NbRows</a> = r+1;
<a name="l00104"></a>00104
<a name="l00105"></a>00105 <span class="comment">/* convert the previous (strict) inequality into an equality */</span>
<a name="l00106"></a>00106 <span class="keywordflow">if</span> (k>=1) {
<a name="l00107"></a>00107 <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(cur_element-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r-1][0], 0);
<a name="l00108"></a>00108 <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(cur_element-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r-1][cur_element-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-1], 0);
<a name="l00109"></a>00109 }
<a name="l00110"></a>00110 <span class="comment">/* build the k-th inequality from P */</span>
<a name="l00111"></a>00111 <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(cur_element-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r][0], 1);
<a name="l00112"></a>00112 <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(cur_element-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r][k+1], -1);
<a name="l00113"></a>00113 <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(cur_element-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r][nb_vars+P_extra+D_extra+k+1], 1);
<a name="l00114"></a>00114 <span class="comment">/* we want a strict inequality */</span>
<a name="l00115"></a>00115 <a class="code" href="source_2arith_2arithmetique_8h.html#8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(cur_element-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r][cur_element-><a class="code" href="structmatrix.html#68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-1], -1);
<a name="l00116"></a>00116 <span class="preprocessor">#ifdef ERDEBUG</span>
<a name="l00117"></a>00117 <span class="preprocessor"></span> <a class="code" href="matrix__addon_8h.html#11468159c7fa7d75fadfa10e2e929fee" title="Polylib matrix addons Mainly, deals with polyhedra represented in implicit form (set...">show_matrix</a>(cur_element);
<a name="l00118"></a>00118 <span class="preprocessor">#endif</span>
<a name="l00119"></a>00119 <span class="preprocessor"></span>
<a name="l00120"></a>00120 <span class="comment">/* b- add it to the current union</span>
<a name="l00121"></a>00121 <span class="comment"> as Constraints2Polyhedron modifies its input, we must clone cur_element */</span>
<a name="l00122"></a>00122 Klon = <a class="code" href="Matop_8c.html#9d027e9fc6b85e6fa37fc284bf1b5e06">Matrix_Copy</a>(cur_element);
<a name="l00123"></a>00123 P1 = <a class="code" href="polyhedron_8c.html#efb77665a187d751bdd44f106b12465e" title="Given a matrix of constraints (&#39;Constraints&#39;), construct and return a polyhedron...">Constraints2Polyhedron</a>(Klon, MAXRAYS);
<a name="l00124"></a>00124 <a class="code" href="matrix_8c.html#fcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(Klon);
<a name="l00125"></a>00125 P1-><a class="code" href="structpolyhedron.html#ab97126cb9e56431d40eaf4e68b3953d">next</a> = lexico_lesser_union;
<a name="l00126"></a>00126 lexico_lesser_union = P1;
<a name="l00127"></a>00127 }
<a name="l00128"></a>00128
<a name="l00129"></a>00129 <span class="comment">/* 2- as we introduce n parameters, we must introduce them into the context</span>
<a name="l00130"></a>00130 <span class="comment"> * as well. </span>
<a name="l00131"></a>00131 <span class="comment"> * The added constraints are P.M.(J N 1 )^T >=0 */</span>
<a name="l00132"></a>00132 <span class="keywordflow">if</span> (D_extra)
<a name="l00133"></a>00133 C_times_J = <a class="code" href="matrix_8c.html#c0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(C-><a class="code" href="structpolyhedron.html#2db05293e731089b9198d45cf027bd1c">NbConstraints</a>, nb_new_parms+nb_parms+2);
<a name="l00134"></a>00134 <span class="keywordflow">else</span>
<a name="l00135"></a>00135 C_times_J = <a class="code" href="matrix_8c.html#c0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(C-><a class="code" href="structpolyhedron.html#2db05293e731089b9198d45cf027bd1c">NbConstraints</a> + D-><a class="code" href="structpolyhedron.html#2db05293e731089b9198d45cf027bd1c">NbConstraints</a>, D-><a class="code" href="structpolyhedron.html#2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a>+2);
<a name="l00136"></a>00136 <span class="comment">/* copy the initial context while adding the new parameters */</span>
<a name="l00137"></a>00137 <span class="keywordflow">for</span> (i = 0; i < C-><a class="code" href="structpolyhedron.html#2db05293e731089b9198d45cf027bd1c">NbConstraints</a>; i++) {
<a name="l00138"></a>00138 <a class="code" href="source_2arith_2arithmetique_8h.html#864613888dc46f15679aa4f63e468f89">value_assign</a>(C_times_J-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][0], C-><a class="code" href="structpolyhedron.html#b2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i][0]);
<a name="l00139"></a>00139 <a class="code" href="vector_8c.html#b6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(C-><a class="code" href="structpolyhedron.html#b2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i]+1, C_times_J-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i]+1+nb_new_parms, nb_parms+1);
<a name="l00140"></a>00140 }
<a name="l00141"></a>00141
<a name="l00142"></a>00142 <span class="comment">/* copy constraints from evaluation domain */</span>
<a name="l00143"></a>00143 <span class="keywordflow">if</span> (!D_extra)
<a name="l00144"></a>00144 <span class="keywordflow">for</span> (i = 0; i < D-><a class="code" href="structpolyhedron.html#2db05293e731089b9198d45cf027bd1c">NbConstraints</a>; i++)
<a name="l00145"></a>00145 <a class="code" href="vector_8c.html#b6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(D-><a class="code" href="structpolyhedron.html#b2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i], C_times_J-><a class="code" href="structmatrix.html#2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[C-><a class="code" href="structpolyhedron.html#2db05293e731089b9198d45cf027bd1c">NbConstraints</a>+i],
<a name="l00146"></a>00146 D-><a class="code" href="structpolyhedron.html#2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a>+2);
<a name="l00147"></a>00147
<a name="l00148"></a>00148 <span class="preprocessor">#ifdef ERDEBUG</span>
<a name="l00149"></a>00149 <span class="preprocessor"></span> <a class="code" href="matrix__addon_8h.html#11468159c7fa7d75fadfa10e2e929fee" title="Polylib matrix addons Mainly, deals with polyhedra represented in implicit form (set...">show_matrix</a>(C_times_J);
<a name="l00150"></a>00150 <span class="preprocessor">#endif</span>
<a name="l00151"></a>00151 <span class="preprocessor"></span> C1 = <a class="code" href="polyhedron_8c.html#efb77665a187d751bdd44f106b12465e" title="Given a matrix of constraints (&#39;Constraints&#39;), construct and return a polyhedron...">Constraints2Polyhedron</a>(C_times_J, <a class="code" href="types_8h.html#754586a0aee88f21ad4c98b1cddee1be">POL_NO_DUAL</a>);
<a name="l00152"></a>00152
<a name="l00153"></a>00153 <span class="comment">/* 4- clean up */</span>
<a name="l00154"></a>00154 <a class="code" href="matrix_8c.html#fcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(cur_element);
<a name="l00155"></a>00155 <a class="code" href="matrix_8c.html#fcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(C_times_J);
<a name="l00156"></a>00156
<a name="l00157"></a>00157 C1-><a class="code" href="structpolyhedron.html#ab97126cb9e56431d40eaf4e68b3953d">next</a> = P1;
<a name="l00158"></a>00158
<a name="l00159"></a>00159 <span class="keywordflow">return</span> C1;
<a name="l00160"></a>00160 } <span class="comment">/* LexSmaller */</span>
<a name="l00161"></a>00161
<a name="l00162"></a>00162 <span class="comment"></span>
<a name="l00163"></a>00163 <span class="comment">/**</span>
<a name="l00164"></a>00164 <span class="comment"> * Returns the number of points in P that are lexicographically</span>
<a name="l00165"></a>00165 <span class="comment"> * smaller than a given point in D.</span>
<a name="l00166"></a>00166 <span class="comment"> * Only the first dim dimensions are taken into account</span>
<a name="l00167"></a>00167 <span class="comment"> * for computing the lexsmaller relation.</span>
<a name="l00168"></a>00168 <span class="comment"> * The remaining variables are assumed to be extra</span>
<a name="l00169"></a>00169 <span class="comment"> * existential/control variables.</span>
<a name="l00170"></a>00170 <span class="comment"> * When P == D, this is the conventional ranking function.</span>
<a name="l00171"></a>00171 <span class="comment"> * P and D are assumed to have the same parameter domain C.</span>
<a name="l00172"></a>00172 <span class="comment"> * The variables in the Enumeration correspond to the first dim variables</span>
<a name="l00173"></a>00173 <span class="comment"> * in D followed by the parameters of D (the variables of C).</span>
<a name="l00174"></a>00174 <span class="comment"> */</span>
<a name="l00175"></a><a class="code" href="ranking_8h.html#89beba033ab097fc0bda2e685d292d0b">00175</a> <a class="code" href="struct__enumeration.html">Enumeration</a> *<a class="code" href="ranking_8c.html#89beba033ab097fc0bda2e685d292d0b" title="Returns the number of points in P that are lexicographically smaller than a given...">Polyhedron_LexSmallerEnumerate</a>(<a class="code" href="structpolyhedron.html">Polyhedron</a> *P, <a class="code" href="structpolyhedron.html">Polyhedron</a> *D,
<a name="l00176"></a>00176 <span class="keywordtype">unsigned</span> dim,
<a name="l00177"></a>00177 <a class="code" href="structpolyhedron.html">Polyhedron</a> *C, <span class="keywordtype">unsigned</span> <a class="code" href="verif__ehrhart_8c.html#89fd83aa168651629c012d8655635588">MAXRAYS</a>)
<a name="l00178"></a>00178 {
<a name="l00179"></a>00179 <a class="code" href="struct__enumeration.html">Enumeration</a> * ranking;
<a name="l00180"></a>00180 <a class="code" href="structpolyhedron.html">Polyhedron</a> *RC, *RD;
<a name="l00181"></a>00181
<a name="l00182"></a>00182 RC = <a class="code" href="ranking_8c.html#1bcb45db9576a3016be0eab5d32f4741" title="Tools to compute the ranking function of an iteration J: the number of integer points...">LexSmaller</a>(P, D, dim, C, MAXRAYS);
<a name="l00183"></a>00183 RD = RC-><a class="code" href="structpolyhedron.html#ab97126cb9e56431d40eaf4e68b3953d">next</a>;
<a name="l00184"></a>00184 RC-><a class="code" href="structpolyhedron.html#ab97126cb9e56431d40eaf4e68b3953d">next</a> = NULL;
<a name="l00185"></a>00185
<a name="l00186"></a>00186 <span class="comment">/* Compute the ranking, which is the sum of the Ehrhart polynomials of the n</span>
<a name="l00187"></a>00187 <span class="comment"> disjoint polyhedra we just put in P1. */</span>
<a name="l00188"></a>00188 <span class="comment">/* OPT : our polyhdera are (already) disjoint, so Domain_Enumerate does</span>
<a name="l00189"></a>00189 <span class="comment"> probably too much work uselessly */</span>
<a name="l00190"></a>00190 ranking = <a class="code" href="ext__ehrhart_8c.html#1a7c95208634df638d39a6656d4abb76">Domain_Enumerate</a>(RD, RC, MAXRAYS, NULL);
<a name="l00191"></a>00191
<a name="l00192"></a>00192 <a class="code" href="polyhedron_8c.html#e6d0a7daf8e801a777fc8e93d8cfe43a">Domain_Free</a>(RD);
<a name="l00193"></a>00193 <a class="code" href="polyhedron_8c.html#4ae97b9794e3a616f1d38c68e6515cc3">Polyhedron_Free</a>(RC);
<a name="l00194"></a>00194
<a name="l00195"></a>00195 <span class="keywordflow">return</span> ranking;
<a name="l00196"></a>00196 }
<a name="l00197"></a>00197
<a name="l00198"></a>00198
<a name="l00199"></a>00199 <span class="comment">/*</span>
<a name="l00200"></a>00200 <span class="comment"> * Returns a function that assigns a unique number to each point in the</span>
<a name="l00201"></a>00201 <span class="comment"> * polytope P ranging from zero to (number of points in P)-1.</span>
<a name="l00202"></a>00202 <span class="comment"> * The order of the numbers corresponds to the lexicographical order.</span>
<a name="l00203"></a>00203 <span class="comment"> *</span>
<a name="l00204"></a>00204 <span class="comment"> * C is the parameter context of the polytope</span>
<a name="l00205"></a>00205 <span class="comment"> */</span>
<a name="l00206"></a><a class="code" href="ranking_8h.html#f8c8c703fc5a2eb9572decbce6a8f09b">00206</a> <a class="code" href="struct__enumeration.html">Enumeration</a> *<a class="code" href="ranking_8c.html#f8c8c703fc5a2eb9572decbce6a8f09b">Polyhedron_Ranking</a>(<a class="code" href="structpolyhedron.html">Polyhedron</a> *P, <a class="code" href="structpolyhedron.html">Polyhedron</a> *C, <span class="keywordtype">unsigned</span> <a class="code" href="verif__ehrhart_8c.html#89fd83aa168651629c012d8655635588">MAXRAYS</a>)
<a name="l00207"></a>00207 {
<a name="l00208"></a>00208 <span class="keywordflow">return</span> <a class="code" href="ranking_8c.html#89beba033ab097fc0bda2e685d292d0b" title="Returns the number of points in P that are lexicographically smaller than a given...">Polyhedron_LexSmallerEnumerate</a>(P, P, P-><a class="code" href="structpolyhedron.html#2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a>-C-><a class="code" href="structpolyhedron.html#2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a>,
<a name="l00209"></a>00209 C, MAXRAYS);
<a name="l00210"></a>00210 }
</pre></div></div>
<hr size="1"><address style="text-align: right;"><small>Generated on Tue Sep 15 18:34:00 2009 for polylib by
<a href="http://www.doxygen.org/index.html">
<img src="doxygen.png" alt="doxygen" align="middle" border="0"></a> 1.5.6 </small></address>
</body>
</html>
|
