00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023 #ifndef PPL_Polyhedron_templates_hh
00024 #define PPL_Polyhedron_templates_hh 1
00025
00026 #include "Generator.defs.hh"
00027 #include "MIP_Problem.defs.hh"
00028 #include <algorithm>
00029 #include <deque>
00030
00031 namespace Parma_Polyhedra_Library {
00032
00033 template <typename Interval>
00034 Polyhedron::Polyhedron(Topology topol,
00035 const Box<Interval>& box,
00036 Complexity_Class)
00037 : con_sys(topol),
00038 gen_sys(topol),
00039 sat_c(),
00040 sat_g() {
00041
00042 space_dim = box.space_dimension();
00043
00044
00045 if (box.is_empty()) {
00046 set_empty();
00047 return;
00048 }
00049
00050
00051 if (space_dim == 0) {
00052 set_zero_dim_univ();
00053 return;
00054 }
00055
00056
00057
00058
00059 con_sys.insert(Variable(space_dim - 1) >= 0);
00060
00061 TEMP_INTEGER(l_n);
00062 TEMP_INTEGER(l_d);
00063 TEMP_INTEGER(u_n);
00064 TEMP_INTEGER(u_d);
00065
00066 if (topol == NECESSARILY_CLOSED) {
00067 for (dimension_type k = space_dim; k-- > 0; ) {
00068
00069 bool l_closed = false;
00070 bool l_bounded = box.get_lower_bound(k, l_closed, l_n, l_d);
00071
00072 bool u_closed = false;
00073 bool u_bounded = box.get_upper_bound(k, u_closed, u_n, u_d);
00074
00075
00076 if (l_bounded && u_bounded
00077 && l_closed && u_closed
00078 && l_n == u_n && l_d == u_d) {
00079
00080 con_sys.insert(l_d * Variable(k) == l_n);
00081 }
00082 else {
00083 if (l_bounded)
00084
00085 con_sys.insert(l_d * Variable(k) >= l_n);
00086 if (u_bounded)
00087
00088 con_sys.insert(u_d * Variable(k) <= u_n);
00089 }
00090 }
00091 }
00092 else {
00093
00094 for (dimension_type k = space_dim; k-- > 0; ) {
00095
00096 bool l_closed = false;
00097 bool l_bounded = box.get_lower_bound(k, l_closed, l_n, l_d);
00098
00099 bool u_closed = false;
00100 bool u_bounded = box.get_upper_bound(k, u_closed, u_n, u_d);
00101
00102
00103 if (l_bounded && u_bounded
00104 && l_closed && u_closed
00105 && l_n == u_n && l_d == u_d) {
00106
00107 con_sys.insert(l_d * Variable(k) == l_n);
00108 }
00109 else {
00110
00111 if (l_bounded) {
00112 if (l_closed)
00113
00114 con_sys.insert(l_d * Variable(k) >= l_n);
00115 else
00116
00117 con_sys.insert(l_d * Variable(k) > l_n);
00118 }
00119
00120 if (u_bounded) {
00121 if (u_closed)
00122
00123 con_sys.insert(u_d * Variable(k) <= u_n);
00124 else
00125
00126 con_sys.insert(u_d * Variable(k) < u_n);
00127 }
00128 }
00129 }
00130 }
00131
00132
00133 con_sys.add_low_level_constraints();
00134
00135 dimension_type n_rows = con_sys.num_rows() - 1;
00136 con_sys[0].swap(con_sys[n_rows]);
00137 con_sys.set_sorted(false);
00138
00139 con_sys.set_index_first_pending_row(n_rows);
00140 con_sys.erase_to_end(n_rows);
00141
00142
00143 set_constraints_up_to_date();
00144 assert(OK());
00145 }
00146
00147 template <typename Partial_Function>
00148 void
00149 Polyhedron::map_space_dimensions(const Partial_Function& pfunc) {
00150 if (space_dim == 0)
00151 return;
00152
00153 if (pfunc.has_empty_codomain()) {
00154
00155 if (marked_empty()
00156 || (has_pending_constraints()
00157 && !remove_pending_to_obtain_generators())
00158 || (!generators_are_up_to_date() && !update_generators())) {
00159
00160 space_dim = 0;
00161 con_sys.clear();
00162 }
00163 else
00164
00165 set_zero_dim_univ();
00166
00167 assert(OK());
00168 return;
00169 }
00170
00171 const dimension_type new_space_dimension = pfunc.max_in_codomain() + 1;
00172
00173 if (new_space_dimension == space_dim) {
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188
00189 std::vector<dimension_type> cycles;
00190 cycles.reserve(space_dim + space_dim/2);
00191
00192
00193 std::deque<bool> visited(space_dim);
00194
00195 for (dimension_type i = space_dim; i-- > 0; ) {
00196 if (!visited[i]) {
00197 dimension_type j = i;
00198 do {
00199 visited[j] = true;
00200
00201 dimension_type k = 0;
00202 if (!pfunc.maps(j, k))
00203 throw_invalid_argument("map_space_dimensions(pfunc)",
00204 " pfunc is inconsistent");
00205 if (k == j)
00206
00207 goto skip;
00208
00209 cycles.push_back(j+1);
00210
00211 j = k;
00212 } while (!visited[j]);
00213
00214 cycles.push_back(0);
00215 skip:
00216 ;
00217 }
00218 }
00219
00220
00221 if (cycles.empty())
00222 return;
00223
00224
00225
00226
00227 if (constraints_are_up_to_date())
00228 con_sys.permute_columns(cycles);
00229
00230 if (generators_are_up_to_date())
00231 gen_sys.permute_columns(cycles);
00232
00233 assert(OK());
00234 return;
00235 }
00236
00237
00238
00239
00240
00241 const Generator_System& old_gensys = generators();
00242
00243 if (old_gensys.has_no_rows()) {
00244
00245 Polyhedron new_polyhedron(topology(), new_space_dimension, EMPTY);
00246 std::swap(*this, new_polyhedron);
00247 assert(OK());
00248 return;
00249 }
00250
00251
00252 std::vector<dimension_type> pfunc_maps(space_dim, not_a_dimension());
00253 for (dimension_type j = space_dim; j-- > 0; ) {
00254 dimension_type pfunc_j;
00255 if (pfunc.maps(j, pfunc_j))
00256 pfunc_maps[j] = pfunc_j;
00257 }
00258
00259 Generator_System new_gensys;
00260 for (Generator_System::const_iterator i = old_gensys.begin(),
00261 old_gensys_end = old_gensys.end(); i != old_gensys_end; ++i) {
00262 const Generator& old_g = *i;
00263 Linear_Expression e(0 * Variable(new_space_dimension-1));
00264 bool all_zeroes = true;
00265 for (dimension_type j = space_dim; j-- > 0; ) {
00266 if (old_g.coefficient(Variable(j)) != 0
00267 && pfunc_maps[j] != not_a_dimension()) {
00268 e += Variable(pfunc_maps[j]) * old_g.coefficient(Variable(j));
00269 all_zeroes = false;
00270 }
00271 }
00272 switch (old_g.type()) {
00273 case Generator::LINE:
00274 if (!all_zeroes)
00275 new_gensys.insert(line(e));
00276 break;
00277 case Generator::RAY:
00278 if (!all_zeroes)
00279 new_gensys.insert(ray(e));
00280 break;
00281 case Generator::POINT:
00282
00283 new_gensys.insert(point(e, old_g.divisor()));
00284 break;
00285 case Generator::CLOSURE_POINT:
00286
00287 new_gensys.insert(closure_point(e, old_g.divisor()));
00288 break;
00289 }
00290 }
00291 Polyhedron new_polyhedron(topology(), new_gensys);
00292 std::swap(*this, new_polyhedron);
00293 assert(OK(true));
00294 }
00295
00296 }
00297
00298 #endif // !defined(PPL_Polyhedron_templates_hh)