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
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>polylib: ranking.c Source File</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- Generated by Doxygen 1.6.1 -->
<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>
<div class="tabs">
<ul>
<li><a href="files.html"><span>File List</span></a></li>
<li><a href="globals.html"><span>File Members</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"> This file is part of PolyLib.</span>
<a name="l00003"></a>00003 <span class="comment"></span>
<a name="l00004"></a>00004 <span class="comment"> PolyLib is free software: you can redistribute it and/or modify</span>
<a name="l00005"></a>00005 <span class="comment"> it under the terms of the GNU General Public License as published by</span>
<a name="l00006"></a>00006 <span class="comment"> the Free Software Foundation, either version 3 of the License, or</span>
<a name="l00007"></a>00007 <span class="comment"> (at your option) any later version.</span>
<a name="l00008"></a>00008 <span class="comment"></span>
<a name="l00009"></a>00009 <span class="comment"> PolyLib is distributed in the hope that it will be useful,</span>
<a name="l00010"></a>00010 <span class="comment"> but WITHOUT ANY WARRANTY; without even the implied warranty of</span>
<a name="l00011"></a>00011 <span class="comment"> MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the</span>
<a name="l00012"></a>00012 <span class="comment"> GNU General Public License for more details.</span>
<a name="l00013"></a>00013 <span class="comment"></span>
<a name="l00014"></a>00014 <span class="comment"> You should have received a copy of the GNU General Public License</span>
<a name="l00015"></a>00015 <span class="comment"> along with PolyLib. If not, see <http://www.gnu.org/licenses/>.</span>
<a name="l00016"></a>00016 <span class="comment">*/</span>
<a name="l00017"></a>00017 <span class="comment"></span>
<a name="l00018"></a>00018 <span class="comment">/**</span>
<a name="l00019"></a>00019 <span class="comment"> * Tools to compute the ranking function of an iteration J: the number of</span>
<a name="l00020"></a>00020 <span class="comment"> * integer points in P that are lexicographically inferior to J </span>
<a name="l00021"></a>00021 <span class="comment"> * B. Meister</span>
<a name="l00022"></a>00022 <span class="comment"> * 6/2005</span>
<a name="l00023"></a>00023 <span class="comment"> * LSIIT-ICPS, UMR 7005 CNRS Universit� Louis Pasteur</span>
<a name="l00024"></a>00024 <span class="comment"> * HiPEAC Network</span>
<a name="l00025"></a>00025 <span class="comment"> */</span>
<a name="l00026"></a>00026
<a name="l00027"></a>00027 <span class="preprocessor">#include <<a class="code" href="polylib_8h.html">polylib/polylib.h</a>></span>
<a name="l00028"></a>00028 <span class="preprocessor">#include <<a class="code" href="ranking_8h.html">polylib/ranking.h</a>></span>
<a name="l00029"></a>00029 <span class="comment"></span>
<a name="l00030"></a>00030 <span class="comment">/**</span>
<a name="l00031"></a>00031 <span class="comment"> * Returns a list of polytopes needed to compute</span>
<a name="l00032"></a>00032 <span class="comment"> * the number of points in P that are lexicographically</span>
<a name="l00033"></a>00033 <span class="comment"> * smaller than a given point in D.</span>
<a name="l00034"></a>00034 <span class="comment"> * Only the first dim dimensions are taken into account</span>
<a name="l00035"></a>00035 <span class="comment"> * for computing the lexsmaller relation.</span>
<a name="l00036"></a>00036 <span class="comment"> * The remaining variables are assumed to be extra</span>
<a name="l00037"></a>00037 <span class="comment"> * existential/control variables.</span>
<a name="l00038"></a>00038 <span class="comment"> * When P == D, this is the conventional ranking function.</span>
<a name="l00039"></a>00039 <span class="comment"> * P and D are assumed to have the same parameter domain C.</span>
<a name="l00040"></a>00040 <span class="comment"> *</span>
<a name="l00041"></a>00041 <span class="comment"> * The first polyhedron in the list returned is the</span>
<a name="l00042"></a>00042 <span class="comment"> * updated context: a combination of D and C or an extended C.</span>
<a name="l00043"></a>00043 <span class="comment"> *</span>
<a name="l00044"></a>00044 <span class="comment"> * The order of the variables in the remaining polyhedra is</span>
<a name="l00045"></a>00045 <span class="comment"> * - first dim variables of P</span>
<a name="l00046"></a>00046 <span class="comment"> * - existential variables of P</span>
<a name="l00047"></a>00047 <span class="comment"> * - existential variables of D</span>
<a name="l00048"></a>00048 <span class="comment"> * - first dim variables of D</span>
<a name="l00049"></a>00049 <span class="comment"> * - the parameters</span>
<a name="l00050"></a>00050 <span class="comment"> */</span>
<a name="l00051"></a><a class="code" href="ranking_8h.html#a1bcb45db9576a3016be0eab5d32f4741">00051</a> <a class="code" href="structpolyhedron.html">Polyhedron</a> *<a class="code" href="ranking_8c.html#a1bcb45db9576a3016be0eab5d32f4741" 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="l00052"></a>00052 <a class="code" href="structpolyhedron.html">Polyhedron</a> *C, <span class="keywordtype">unsigned</span> <a class="code" href="verif__ehrhart_8c.html#a89fd83aa168651629c012d8655635588">MAXRAYS</a>)
<a name="l00053"></a>00053 {
<a name="l00054"></a>00054 <span class="keywordtype">unsigned</span> i, j, k, r;
<a name="l00055"></a>00055 <span class="keywordtype">unsigned</span> nb_parms = C-><a class="code" href="structpolyhedron.html#a2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a>;
<a name="l00056"></a>00056 <span class="keywordtype">unsigned</span> nb_vars = dim;
<a name="l00057"></a>00057 <span class="keywordtype">unsigned</span> P_extra = P-><a class="code" href="structpolyhedron.html#a2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a> - nb_vars - nb_parms;
<a name="l00058"></a>00058 <span class="keywordtype">unsigned</span> D_extra = D-><a class="code" href="structpolyhedron.html#a2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a> - nb_vars - nb_parms;
<a name="l00059"></a>00059 <span class="keywordtype">unsigned</span> nb_new_parms;
<a name="l00060"></a>00060 <span class="keywordtype">unsigned</span> ncons;
<a name="l00061"></a>00061 <a class="code" href="structmatrix.html">Matrix</a> * cur_element, * C_times_J, * Klon;
<a name="l00062"></a>00062 <a class="code" href="structpolyhedron.html">Polyhedron</a> * P1, *C1;
<a name="l00063"></a>00063 <a class="code" href="structpolyhedron.html">Polyhedron</a> * lexico_lesser_union = NULL;
<a name="l00064"></a>00064
<a name="l00065"></a>00065 <a class="code" href="polyhedron_8h.html#a54a764faf683e794f4db092c8d050104">POL_ENSURE_INEQUALITIES</a>(C);
<a name="l00066"></a>00066 <a class="code" href="polyhedron_8h.html#a54a764faf683e794f4db092c8d050104">POL_ENSURE_INEQUALITIES</a>(D);
<a name="l00067"></a>00067 <a class="code" href="polyhedron_8h.html#a54a764faf683e794f4db092c8d050104">POL_ENSURE_INEQUALITIES</a>(P);
<a name="l00068"></a>00068
<a name="l00069"></a>00069 <a class="code" href="assert_8h.html#a07d17d6d5d1074c0969bc5d3c3d1d84a">assert</a>(P-><a class="code" href="structpolyhedron.html#a2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a> >= C-><a class="code" href="structpolyhedron.html#a2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a> + dim);
<a name="l00070"></a>00070 <a class="code" href="assert_8h.html#a07d17d6d5d1074c0969bc5d3c3d1d84a">assert</a>(D-><a class="code" href="structpolyhedron.html#a2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a> >= C-><a class="code" href="structpolyhedron.html#a2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a> + dim);
<a name="l00071"></a>00071 nb_new_parms = nb_vars;
<a name="l00072"></a>00072
<a name="l00073"></a>00073 <span class="comment">/* the number of variables must be positive */</span>
<a name="l00074"></a>00074 <span class="keywordflow">if</span> (nb_vars<=0) {
<a name="l00075"></a>00075 printf(<span class="stringliteral">"\nRanking > No variables, returning NULL.\n"</span>);
<a name="l00076"></a>00076 <span class="keywordflow">return</span> NULL;
<a name="l00077"></a>00077 }
<a name="l00078"></a>00078 <span class="comment">/*</span>
<a name="l00079"></a>00079 <span class="comment"> * if D has extra variables, then we can't squeeze the contraints</span>
<a name="l00080"></a>00080 <span class="comment"> * of D in the new context, so we simply add them to each element.</span>
<a name="l00081"></a>00081 <span class="comment"> */</span>
<a name="l00082"></a>00082 <span class="keywordflow">if</span> (D_extra)
<a name="l00083"></a>00083 cur_element = <a class="code" href="matrix_8c.html#ac0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(P-><a class="code" href="structpolyhedron.html#a2db05293e731089b9198d45cf027bd1c">NbConstraints</a>+D-><a class="code" href="structpolyhedron.html#a2db05293e731089b9198d45cf027bd1c">NbConstraints</a>+nb_new_parms,
<a name="l00084"></a>00084 P-><a class="code" href="structpolyhedron.html#a2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a>+D_extra+nb_new_parms+2);
<a name="l00085"></a>00085 <span class="keywordflow">else</span>
<a name="l00086"></a>00086 cur_element = <a class="code" href="matrix_8c.html#ac0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(P-><a class="code" href="structpolyhedron.html#a2db05293e731089b9198d45cf027bd1c">NbConstraints</a>+nb_new_parms,
<a name="l00087"></a>00087 P-><a class="code" href="structpolyhedron.html#a2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a>+D_extra+nb_new_parms+2);
<a name="l00088"></a>00088
<a name="l00089"></a>00089
<a name="l00090"></a>00090 <span class="comment">/* 0- Put P in the first rows of cur_element */</span>
<a name="l00091"></a>00091 <span class="keywordflow">for</span> (i=0; i < P-><a class="code" href="structpolyhedron.html#a2db05293e731089b9198d45cf027bd1c">NbConstraints</a>; i++) {
<a name="l00092"></a>00092 <a class="code" href="vector_8c.html#ab6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(P-><a class="code" href="structpolyhedron.html#ab2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i], cur_element-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i], nb_vars+P_extra+1);
<a name="l00093"></a>00093 <a class="code" href="vector_8c.html#ab6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(P-><a class="code" href="structpolyhedron.html#ab2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i]+1+nb_vars+P_extra,
<a name="l00094"></a>00094 cur_element-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i]+1+nb_vars+P_extra+D_extra+nb_new_parms,
<a name="l00095"></a>00095 nb_parms+1);
<a name="l00096"></a>00096 }
<a name="l00097"></a>00097 ncons = P-><a class="code" href="structpolyhedron.html#a2db05293e731089b9198d45cf027bd1c">NbConstraints</a>;
<a name="l00098"></a>00098 <span class="keywordflow">if</span> (D_extra) {
<a name="l00099"></a>00099 <span class="keywordflow">for</span> (i=0; i < D-><a class="code" href="structpolyhedron.html#a2db05293e731089b9198d45cf027bd1c">NbConstraints</a>; i++) {
<a name="l00100"></a>00100 r = P-><a class="code" href="structpolyhedron.html#a2db05293e731089b9198d45cf027bd1c">NbConstraints</a> + i;
<a name="l00101"></a>00101 <a class="code" href="vector_8c.html#ab6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(D-><a class="code" href="structpolyhedron.html#ab2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i], cur_element-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r], 1);
<a name="l00102"></a>00102 <a class="code" href="vector_8c.html#ab6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(D-><a class="code" href="structpolyhedron.html#ab2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i]+1,
<a name="l00103"></a>00103 cur_element-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r]+1+nb_vars+P_extra+D_extra, nb_new_parms);
<a name="l00104"></a>00104 <a class="code" href="vector_8c.html#ab6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(D-><a class="code" href="structpolyhedron.html#ab2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i]+1+nb_new_parms,
<a name="l00105"></a>00105 cur_element-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r]+1+nb_vars+P_extra, D_extra);
<a name="l00106"></a>00106 <a class="code" href="vector_8c.html#ab6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(D-><a class="code" href="structpolyhedron.html#ab2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i]+1+nb_new_parms+D_extra,
<a name="l00107"></a>00107 cur_element-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r]+1+nb_vars+P_extra+D_extra+nb_new_parms,
<a name="l00108"></a>00108 nb_parms+1);
<a name="l00109"></a>00109 }
<a name="l00110"></a>00110 ncons += D-><a class="code" href="structpolyhedron.html#a2db05293e731089b9198d45cf027bd1c">NbConstraints</a>;
<a name="l00111"></a>00111 }
<a name="l00112"></a>00112
<a name="l00113"></a>00113 <span class="comment">/* 1- compute the Ehrhart polynomial of each disjoint polyhedron defining the</span>
<a name="l00114"></a>00114 <span class="comment"> lexicographic order */</span>
<a name="l00115"></a>00115 <span class="keywordflow">for</span> (k=0, r = ncons; k < nb_vars; k++, r++) {
<a name="l00116"></a>00116
<a name="l00117"></a>00117 <span class="comment">/* a- build the corresponding matrix</span>
<a name="l00118"></a>00118 <span class="comment"> * the nb of rows of cur_element is fake, so that we do not have to</span>
<a name="l00119"></a>00119 <span class="comment"> * re-allocate it. */</span>
<a name="l00120"></a>00120 cur_element-><a class="code" href="structmatrix.html#a16ad614d15c6e81c0041e877b623c72d">NbRows</a> = r+1;
<a name="l00121"></a>00121
<a name="l00122"></a>00122 <span class="comment">/* convert the previous (strict) inequality into an equality */</span>
<a name="l00123"></a>00123 <span class="keywordflow">if</span> (k>=1) {
<a name="l00124"></a>00124 <a class="code" href="source_2arith_2arithmetique_8h.html#a8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(cur_element-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r-1][0], 0);
<a name="l00125"></a>00125 <a class="code" href="source_2arith_2arithmetique_8h.html#a8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(cur_element-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r-1][cur_element-><a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-1], 0);
<a name="l00126"></a>00126 }
<a name="l00127"></a>00127 <span class="comment">/* build the k-th inequality from P */</span>
<a name="l00128"></a>00128 <a class="code" href="source_2arith_2arithmetique_8h.html#a8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(cur_element-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r][0], 1);
<a name="l00129"></a>00129 <a class="code" href="source_2arith_2arithmetique_8h.html#a8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(cur_element-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r][k+1], -1);
<a name="l00130"></a>00130 <a class="code" href="source_2arith_2arithmetique_8h.html#a8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(cur_element-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r][nb_vars+P_extra+D_extra+k+1], 1);
<a name="l00131"></a>00131 <span class="comment">/* we want a strict inequality */</span>
<a name="l00132"></a>00132 <a class="code" href="source_2arith_2arithmetique_8h.html#a8cc56567a4a29271559ac0fd5f6c5bfa">value_set_si</a>(cur_element-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[r][cur_element-><a class="code" href="structmatrix.html#a68858fd3b57684ef38bdfce13c65d182">NbColumns</a>-1], -1);
<a name="l00133"></a>00133 <span class="preprocessor">#ifdef ERDEBUG</span>
<a name="l00134"></a>00134 <span class="preprocessor"></span> <a class="code" href="matrix__addon_8h.html#a11468159c7fa7d75fadfa10e2e929fee" title="Polylib matrix addons Mainly, deals with polyhedra represented in implicit form (set...">show_matrix</a>(cur_element);
<a name="l00135"></a>00135 <span class="preprocessor">#endif</span>
<a name="l00136"></a>00136 <span class="preprocessor"></span>
<a name="l00137"></a>00137 <span class="comment">/* b- add it to the current union</span>
<a name="l00138"></a>00138 <span class="comment"> as Constraints2Polyhedron modifies its input, we must clone cur_element */</span>
<a name="l00139"></a>00139 Klon = <a class="code" href="Matop_8c.html#a9d027e9fc6b85e6fa37fc284bf1b5e06">Matrix_Copy</a>(cur_element);
<a name="l00140"></a>00140 P1 = <a class="code" href="polyhedron_8c.html#aefb77665a187d751bdd44f106b12465e" title="Given a matrix of constraints (&#39;Constraints&#39;), construct and return a polyhedron...">Constraints2Polyhedron</a>(Klon, MAXRAYS);
<a name="l00141"></a>00141 <a class="code" href="matrix_8c.html#afcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(Klon);
<a name="l00142"></a>00142 P1-><a class="code" href="structpolyhedron.html#aab97126cb9e56431d40eaf4e68b3953d">next</a> = lexico_lesser_union;
<a name="l00143"></a>00143 lexico_lesser_union = P1;
<a name="l00144"></a>00144 }
<a name="l00145"></a>00145
<a name="l00146"></a>00146 <span class="comment">/* 2- as we introduce n parameters, we must introduce them into the context</span>
<a name="l00147"></a>00147 <span class="comment"> * as well. </span>
<a name="l00148"></a>00148 <span class="comment"> * The added constraints are P.M.(J N 1 )^T >=0 */</span>
<a name="l00149"></a>00149 <span class="keywordflow">if</span> (D_extra)
<a name="l00150"></a>00150 C_times_J = <a class="code" href="matrix_8c.html#ac0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(C-><a class="code" href="structpolyhedron.html#a2db05293e731089b9198d45cf027bd1c">NbConstraints</a>, nb_new_parms+nb_parms+2);
<a name="l00151"></a>00151 <span class="keywordflow">else</span>
<a name="l00152"></a>00152 C_times_J = <a class="code" href="matrix_8c.html#ac0b29e1d99a2823ad00b5f2157879d80">Matrix_Alloc</a>(C-><a class="code" href="structpolyhedron.html#a2db05293e731089b9198d45cf027bd1c">NbConstraints</a> + D-><a class="code" href="structpolyhedron.html#a2db05293e731089b9198d45cf027bd1c">NbConstraints</a>, D-><a class="code" href="structpolyhedron.html#a2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a>+2);
<a name="l00153"></a>00153 <span class="comment">/* copy the initial context while adding the new parameters */</span>
<a name="l00154"></a>00154 <span class="keywordflow">for</span> (i = 0; i < C-><a class="code" href="structpolyhedron.html#a2db05293e731089b9198d45cf027bd1c">NbConstraints</a>; i++) {
<a name="l00155"></a>00155 <a class="code" href="source_2arith_2arithmetique_8h.html#a864613888dc46f15679aa4f63e468f89">value_assign</a>(C_times_J-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i][0], C-><a class="code" href="structpolyhedron.html#ab2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i][0]);
<a name="l00156"></a>00156 <a class="code" href="vector_8c.html#ab6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(C-><a class="code" href="structpolyhedron.html#ab2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i]+1, C_times_J-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[i]+1+nb_new_parms, nb_parms+1);
<a name="l00157"></a>00157 }
<a name="l00158"></a>00158
<a name="l00159"></a>00159 <span class="comment">/* copy constraints from evaluation domain */</span>
<a name="l00160"></a>00160 <span class="keywordflow">if</span> (!D_extra)
<a name="l00161"></a>00161 <span class="keywordflow">for</span> (i = 0; i < D-><a class="code" href="structpolyhedron.html#a2db05293e731089b9198d45cf027bd1c">NbConstraints</a>; i++)
<a name="l00162"></a>00162 <a class="code" href="vector_8c.html#ab6eca9ad03a2f4a60dd79182289e0e0b">Vector_Copy</a>(D-><a class="code" href="structpolyhedron.html#ab2691b8eb5d2dc43a509ac2094d2bc73">Constraint</a>[i], C_times_J-><a class="code" href="structmatrix.html#a2c6d840d8d911ae95c2ae4fc96f4b5ba">p</a>[C-><a class="code" href="structpolyhedron.html#a2db05293e731089b9198d45cf027bd1c">NbConstraints</a>+i],
<a name="l00163"></a>00163 D-><a class="code" href="structpolyhedron.html#a2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a>+2);
<a name="l00164"></a>00164
<a name="l00165"></a>00165 <span class="preprocessor">#ifdef ERDEBUG</span>
<a name="l00166"></a>00166 <span class="preprocessor"></span> <a class="code" href="matrix__addon_8h.html#a11468159c7fa7d75fadfa10e2e929fee" title="Polylib matrix addons Mainly, deals with polyhedra represented in implicit form (set...">show_matrix</a>(C_times_J);
<a name="l00167"></a>00167 <span class="preprocessor">#endif</span>
<a name="l00168"></a>00168 <span class="preprocessor"></span> C1 = <a class="code" href="polyhedron_8c.html#aefb77665a187d751bdd44f106b12465e" 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#a754586a0aee88f21ad4c98b1cddee1be">POL_NO_DUAL</a>);
<a name="l00169"></a>00169
<a name="l00170"></a>00170 <span class="comment">/* 4- clean up */</span>
<a name="l00171"></a>00171 <a class="code" href="matrix_8c.html#afcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(cur_element);
<a name="l00172"></a>00172 <a class="code" href="matrix_8c.html#afcb312b7c12a6997cd66964ecc34e1a6">Matrix_Free</a>(C_times_J);
<a name="l00173"></a>00173
<a name="l00174"></a>00174 C1-><a class="code" href="structpolyhedron.html#aab97126cb9e56431d40eaf4e68b3953d">next</a> = P1;
<a name="l00175"></a>00175
<a name="l00176"></a>00176 <span class="keywordflow">return</span> C1;
<a name="l00177"></a>00177 } <span class="comment">/* LexSmaller */</span>
<a name="l00178"></a>00178
<a name="l00179"></a>00179 <span class="comment"></span>
<a name="l00180"></a>00180 <span class="comment">/**</span>
<a name="l00181"></a>00181 <span class="comment"> * Returns the number of points in P that are lexicographically</span>
<a name="l00182"></a>00182 <span class="comment"> * smaller than a given point in D.</span>
<a name="l00183"></a>00183 <span class="comment"> * Only the first dim dimensions are taken into account</span>
<a name="l00184"></a>00184 <span class="comment"> * for computing the lexsmaller relation.</span>
<a name="l00185"></a>00185 <span class="comment"> * The remaining variables are assumed to be extra</span>
<a name="l00186"></a>00186 <span class="comment"> * existential/control variables.</span>
<a name="l00187"></a>00187 <span class="comment"> * When P == D, this is the conventional ranking function.</span>
<a name="l00188"></a>00188 <span class="comment"> * P and D are assumed to have the same parameter domain C.</span>
<a name="l00189"></a>00189 <span class="comment"> * The variables in the Enumeration correspond to the first dim variables</span>
<a name="l00190"></a>00190 <span class="comment"> * in D followed by the parameters of D (the variables of C).</span>
<a name="l00191"></a>00191 <span class="comment"> */</span>
<a name="l00192"></a><a class="code" href="ranking_8h.html#a89beba033ab097fc0bda2e685d292d0b">00192</a> <a class="code" href="struct__enumeration.html">Enumeration</a> *<a class="code" href="ranking_8c.html#a89beba033ab097fc0bda2e685d292d0b" 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="l00193"></a>00193 <span class="keywordtype">unsigned</span> dim,
<a name="l00194"></a>00194 <a class="code" href="structpolyhedron.html">Polyhedron</a> *C, <span class="keywordtype">unsigned</span> <a class="code" href="verif__ehrhart_8c.html#a89fd83aa168651629c012d8655635588">MAXRAYS</a>)
<a name="l00195"></a>00195 {
<a name="l00196"></a>00196 <a class="code" href="struct__enumeration.html">Enumeration</a> * ranking;
<a name="l00197"></a>00197 <a class="code" href="structpolyhedron.html">Polyhedron</a> *RC, *RD;
<a name="l00198"></a>00198
<a name="l00199"></a>00199 RC = <a class="code" href="ranking_8c.html#a1bcb45db9576a3016be0eab5d32f4741" 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="l00200"></a>00200 RD = RC-><a class="code" href="structpolyhedron.html#aab97126cb9e56431d40eaf4e68b3953d">next</a>;
<a name="l00201"></a>00201 RC-><a class="code" href="structpolyhedron.html#aab97126cb9e56431d40eaf4e68b3953d">next</a> = NULL;
<a name="l00202"></a>00202
<a name="l00203"></a>00203 <span class="comment">/* Compute the ranking, which is the sum of the Ehrhart polynomials of the n</span>
<a name="l00204"></a>00204 <span class="comment"> disjoint polyhedra we just put in P1. */</span>
<a name="l00205"></a>00205 <span class="comment">/* OPT : our polyhdera are (already) disjoint, so Domain_Enumerate does</span>
<a name="l00206"></a>00206 <span class="comment"> probably too much work uselessly */</span>
<a name="l00207"></a>00207 ranking = <a class="code" href="ext__ehrhart_8c.html#a1a7c95208634df638d39a6656d4abb76">Domain_Enumerate</a>(RD, RC, MAXRAYS, NULL);
<a name="l00208"></a>00208
<a name="l00209"></a>00209 <a class="code" href="polyhedron_8c.html#ae6d0a7daf8e801a777fc8e93d8cfe43a">Domain_Free</a>(RD);
<a name="l00210"></a>00210 <a class="code" href="polyhedron_8c.html#a4ae97b9794e3a616f1d38c68e6515cc3">Polyhedron_Free</a>(RC);
<a name="l00211"></a>00211
<a name="l00212"></a>00212 <span class="keywordflow">return</span> ranking;
<a name="l00213"></a>00213 }
<a name="l00214"></a>00214
<a name="l00215"></a>00215
<a name="l00216"></a>00216 <span class="comment">/*</span>
<a name="l00217"></a>00217 <span class="comment"> * Returns a function that assigns a unique number to each point in the</span>
<a name="l00218"></a>00218 <span class="comment"> * polytope P ranging from zero to (number of points in P)-1.</span>
<a name="l00219"></a>00219 <span class="comment"> * The order of the numbers corresponds to the lexicographical order.</span>
<a name="l00220"></a>00220 <span class="comment"> *</span>
<a name="l00221"></a>00221 <span class="comment"> * C is the parameter context of the polytope</span>
<a name="l00222"></a>00222 <span class="comment"> */</span>
<a name="l00223"></a><a class="code" href="ranking_8h.html#af8c8c703fc5a2eb9572decbce6a8f09b">00223</a> <a class="code" href="struct__enumeration.html">Enumeration</a> *<a class="code" href="ranking_8c.html#af8c8c703fc5a2eb9572decbce6a8f09b">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#a89fd83aa168651629c012d8655635588">MAXRAYS</a>)
<a name="l00224"></a>00224 {
<a name="l00225"></a>00225 <span class="keywordflow">return</span> <a class="code" href="ranking_8c.html#a89beba033ab097fc0bda2e685d292d0b" 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#a2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a>-C-><a class="code" href="structpolyhedron.html#a2a02cea8b7ba3dde415041b8b2373bc8">Dimension</a>,
<a name="l00226"></a>00226 C, MAXRAYS);
<a name="l00227"></a>00227 }
</pre></div></div>
<hr size="1"/><address style="text-align: right;"><small>Generated on Wed Nov 25 17:45:26 2009 for polylib by
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.6.1 </small></address>
</body>
</html>
|
