angel
mercurial changeset:
|
00001 // $Id: heuristics.cpp,v 1.11 2008/02/28 14:57:33 gottschling Exp $ 00002 /* 00003 ############################################################# 00004 # This file is part of angel released under the BSD license # 00005 # The full COPYRIGHT notice can be found in the top # 00006 # level directory of the angel distribution # 00007 ############################################################# 00008 */ 00009 00010 00011 #include <limits.h> 00012 #include <algorithm> 00013 00014 #include "angel/include/heuristics.hpp" 00015 #include "angel/include/angel_exceptions.hpp" 00016 #include "angel/include/angel_tools.hpp" 00017 #ifdef USEXAIFBOOSTER 00018 #include "angel/include/reroutings.hpp" 00019 using namespace xaifBoosterCrossCountryInterface; 00020 #endif 00021 00022 namespace angel { 00023 00024 using namespace std; 00025 using namespace boost; 00026 00027 // ===================================================== 00028 // for vertex elimination 00029 // ===================================================== 00030 00031 int forward_mode_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1, 00032 const c_graph_t& cg, 00033 vector<c_graph_t::vertex_t>& vv2) { 00034 vv2.resize (0); 00035 if (vv1.size() == 0) {set_empty_objective (); return 0; } 00036 vv2.push_back (vv1[0]); 00037 00038 for (size_t c= 1; c < vv1.size(); c++) 00039 if (vv1[c] < vv2[0]) vv2[0]= vv1[c]; 00040 set_objective (vv2[0]); 00041 return 1; 00042 } 00043 00044 forward_mode_vertex_t forward_mode_vertex; 00045 00046 // ------------------------------------------------------------------------- 00047 // reverse mode 00048 // ------------------------------------------------------------------------- 00049 00050 int reverse_mode_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1, 00051 const c_graph_t& cg, 00052 vector<c_graph_t::vertex_t>& vv2) { 00053 vv2.resize (0); 00054 if (vv1.size() == 0) {set_empty_objective (); return 0; } 00055 vv2.push_back (vv1[0]); 00056 00057 for (size_t c= 1; c < vv1.size(); c++) 00058 if (vv1[c] > vv2[0]) vv2[0]= vv1[c]; 00059 set_objective (vv2[0]); 00060 return 1; 00061 } 00062 00063 reverse_mode_vertex_t reverse_mode_vertex; 00064 00065 // ------------------------------------------------------------------------- 00066 // Lowest Markowitz 00067 // ------------------------------------------------------------------------- 00068 00069 // operator for lowest Markowitz on vertices 00070 struct lmv_op_t { 00071 int operator() (c_graph_t::vertex_t v, const c_graph_t& cg) { 00072 return in_degree (v, cg) * out_degree (v, cg); } 00073 }; 00074 00075 int lowest_markowitz_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1, 00076 const c_graph_t& cg, 00077 vector<c_graph_t::vertex_t>& vv2) { 00078 lmv_op_t lmv_op; 00079 return standard_heuristic_op (vv1, cg, vv2, lmv_op, *this); 00080 } 00081 00082 lowest_markowitz_vertex_t lowest_markowitz_vertex; 00083 00084 // ------------------------------------------------------------------------- 00085 // Lowest relative Markowitz 00086 // ------------------------------------------------------------------------- 00087 00088 // operator for lowest relative Markowitz on vertices and edges 00089 struct lrm_op_t { 00090 vector<int> indep, dep; 00091 lrm_op_t (const c_graph_t& cg) : indep (num_vertices (cg)), dep (num_vertices (cg)) { 00092 number_independent_vertices (cg, indep); number_dependent_vertices (cg, dep); } 00093 int operator() (bool front, c_graph_t::edge_t edge, const c_graph_t& cg) { 00094 return front ? out_degree (target (edge, cg), cg) - dep[target (edge, cg)] 00095 : in_degree (source (edge, cg), cg) - indep[source (edge, cg)]; } 00096 int operator() (edge_bool_t eb, const c_graph_t& cg) { 00097 return eb.second ? out_degree (target (eb.first, cg), cg) - dep[target (eb.first, cg)] 00098 : in_degree (source (eb.first, cg), cg) - indep[source (eb.first, cg)]; } 00099 int operator() (c_graph_t::vertex_t v, const c_graph_t& cg) { 00100 return in_degree (v, cg) * out_degree (v, cg) - indep[v] * dep[v]; } 00101 }; 00102 00103 int lowest_relative_markowitz_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1, 00104 const c_graph_t& cg, 00105 vector<c_graph_t::vertex_t>& vv2) { 00106 lrm_op_t lrm_op (cg); 00107 return standard_heuristic_op (vv1, cg, vv2, lrm_op, *this); 00108 } 00109 00110 lowest_relative_markowitz_vertex_t lowest_relative_markowitz_vertex; 00111 00112 // ------------------------------------------------------------------------- 00113 // subroutine of Lowest fill-in 00114 // ------------------------------------------------------------------------- 00115 00116 // how many new in_edges has j:target(e) by back-eliminating e 00117 int new_in_edges (c_graph_t::edge_t e, const c_graph_t& cg) { 00118 00119 typedef c_graph_t::vertex_t vertex_t; 00120 typedef c_graph_t::iei_t iei_t; 00121 00122 iei_t siei, sie_end, tiei, tie_end; 00123 tie (siei, sie_end)= in_edges (source (e, cg), cg); 00124 tie (tiei, tie_end)= in_edges (target (e, cg), cg); 00125 int new_edges= 0; 00126 00127 vector<vertex_t> nsl; // list of new sources to check double insertions 00128 00129 for (; siei != sie_end; ++siei) { 00130 vertex_t ss= source (*siei, cg); 00131 iei_t i= tiei; 00132 for (; i != tie_end; ++i) 00133 if (source (*i, cg) == ss) break; 00134 if (i == tie_end 00135 && find (nsl.begin(), nsl.end(), ss) == nsl.end()) { 00136 nsl.push_back (ss); new_edges++; } 00137 } 00138 00139 return new_edges; 00140 } 00141 00142 // how many new out_edges has j:=source(e) by front-eliminating e 00143 int new_out_edges (c_graph_t::edge_t e, const c_graph_t& cg) { 00144 00145 typedef c_graph_t::vertex_t vertex_t; 00146 typedef c_graph_t::oei_t oei_t; 00147 00148 oei_t soei, soe_end, toei, toe_end; 00149 tie (soei, soe_end)= out_edges (source (e, cg), cg); 00150 tie (toei, toe_end)= out_edges (target (e, cg), cg); 00151 int new_edges= 0; 00152 00153 vector<vertex_t> ntl; // list of new targets to check double insertions 00154 00155 for (; toei != toe_end; ++toei) { 00156 vertex_t tt= target (*toei, cg); 00157 oei_t i= soei; 00158 for (; i != soe_end; ++i) 00159 if (target (*i, cg) == tt) break; 00160 if (i == soe_end 00161 && find (ntl.begin(), ntl.end(), tt) == ntl.end()) { 00162 ntl.push_back (tt); new_edges++; } 00163 } 00164 00165 return new_edges; 00166 } 00167 00168 00169 // ------------------------------------------------------------------------- 00170 // Lowest fill-in 00171 // ------------------------------------------------------------------------- 00172 00173 00174 // operator for lowest fill-in on vertices 00175 struct fiv_op_t { 00176 int operator() (c_graph_t::vertex_t v, const c_graph_t& cg) { 00177 int fill_ins= 0; 00178 c_graph_t::iei_t iei, ie_end; 00179 for (tie (iei, ie_end)= in_edges (v, cg); iei != ie_end; ++iei) 00180 fill_ins+= new_out_edges (*iei, cg); 00181 return fill_ins; } 00182 }; 00183 00184 int lowest_fill_in_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1, 00185 const c_graph_t& cg, 00186 vector<c_graph_t::vertex_t>& vv2) { 00187 fiv_op_t fiv_op; 00188 return standard_heuristic_op (vv1, cg, vv2, fiv_op, *this); 00189 } 00190 00191 lowest_fill_in_vertex_t lowest_fill_in_vertex; 00192 00193 // ------------------------------------------------------------------------- 00194 // subroutines of LMMD MOMR 00195 // ------------------------------------------------------------------------- 00196 00197 // how much the markowitz degree of j:=source(e) is enlarged by front-eliminating e 00198 // this is in_degree(j) * #new out_edges(j) 00199 int markowitz_enlargement_front (c_graph_t::edge_t e, const c_graph_t& cg, 00200 bool eliminate_parallel_edges= false) { 00201 int ee= 0; // number of eliminated edges 00202 c_graph_t::vertex_t s= source (e, cg), t= target (e, cg); 00203 if (vertex_type (t, cg) == intermediate){ // if dependent edges are not eliminated 00204 if (eliminate_parallel_edges) { 00205 c_graph_t::oei_t soei, soe_end; 00206 for (tie (soei, soe_end)= out_edges (s, cg); soei != soe_end; soei++) 00207 ee+= target (*soei, cg) == t; 00208 } else ee= 1; 00209 } 00210 return in_degree (source (e, cg), cg) * (new_out_edges (e, cg) - ee); 00211 } 00212 00213 // how much is the markowitz degree of j:=target(e2) enlarged by front-eliminating e 00214 int markowitz_enlargement_front (c_graph_t::edge_t e, c_graph_t::edge_t e2, 00215 const c_graph_t& cg) { 00216 00217 THROW_DEBUG_EXCEPT_MACRO (target (e, cg) != source (e2, cg), consistency_exception, 00218 "e and e2 does not match"); 00219 00220 c_graph_t::vertex_t j= target (e2, cg), se= source (e, cg), te= target (e, cg); 00221 00222 // if e is last in_edge of te than e2 will be eliminated -> j has one in_edge less 00223 // int in_edge_change= in_degree (te, cg) == 1 ? -1 : 0; 00224 00225 // if e is last in_edge of te than e2 and its parallel edges will be eliminated 00226 // -> j has one or more in_edges less 00227 int in_edge_change= in_degree (te, cg) == 1 ? - count_parallel_edges (e2, cg) : 0; 00228 00229 // if source(e) is not source of an in_edge of j -> j has one in_edge more 00230 c_graph_t::iei_t iei, ie_end; 00231 for (tie (iei, ie_end)= in_edges (j, cg); iei != ie_end; ++iei) 00232 if (source (*iei, cg) == se) break; 00233 if (iei == ie_end) in_edge_change++; 00234 00235 return in_edge_change * out_degree (j, cg); 00236 } 00237 00238 // how much the markowitz degree of j:=target(e) is enlarged by back-eliminating e 00239 // this is out_degree(j) * #new in_edges(j) 00240 int markowitz_enlargement_back (c_graph_t::edge_t e, const c_graph_t& cg, 00241 bool eliminate_parallel_edges= false) { 00242 00243 int ee= 0; // number of eliminated edges 00244 if (eliminate_parallel_edges) { 00245 c_graph_t::vertex_t s= source (e, cg), t= target (e, cg); 00246 c_graph_t::iei_t tiei, tie_end; 00247 for (tie (tiei, tie_end)= in_edges (t, cg); tiei != tie_end; ++tiei) 00248 ee+= source (*tiei, cg) == s; 00249 } else ee= 1; 00250 00251 return out_degree (target (e, cg), cg) * (new_in_edges (e, cg) - ee); 00252 } 00253 00254 // how much is the markowitz degree of j:=source(e2) enlarged by back-eliminating e 00255 int markowitz_enlargement_back (c_graph_t::edge_t e, c_graph_t::edge_t e2, 00256 const c_graph_t& cg) { 00257 00258 // assert (source (e, cg) == target (e2, cg)); 00259 THROW_DEBUG_EXCEPT_MACRO (source (e, cg) != target (e2, cg), consistency_exception, 00260 "e and e2 does not match"); 00261 00262 c_graph_t::vertex_t j= source (e2, cg), se= source (e, cg), te= target (e, cg); 00263 00264 // if e is last out_edge of se than e2 will be eliminated -> j has one out_edge less 00265 int out_edge_change= out_degree (se, cg) == 1 ? -1 : 0; 00266 00267 // if target(e) is not target of an out_edge of j -> j has one out_edge more 00268 c_graph_t::oei_t oei, oe_end; 00269 for (tie (oei, oe_end)= out_edges (j, cg); oei != oe_end; ++oei) 00270 if (target (*oei, cg) == te) break; 00271 if (oei == oe_end) out_edge_change++; 00272 00273 return out_edge_change * in_degree (j, cg); 00274 } 00275 00276 // how much is the markowitz degree of all neighbors of v increased by its elimination 00277 // multiply occurred neighbors are counted only once 00278 int markowitz_enlargement_all_neighbors (c_graph_t::vertex_t v, const c_graph_t& cg) { 00279 00280 using namespace std; 00281 00282 typedef c_graph_t::vertex_t vertex_t; 00283 00284 int enl= 0; 00285 00286 // parallel edges does not cause multiple Markowitz changes 00287 vector<vertex_t> cv; // already checked vertices 00288 cv.reserve (10); // reduce mallocs 00289 00290 c_graph_t::iei_t iei, ie_end; 00291 tie (iei, ie_end)= in_edges (v, cg); 00292 for (; iei != ie_end; ++iei) { 00293 vertex_t v= source (*iei, cg); 00294 if (find (cv.begin(), cv.end(), v) == cv.end()) { 00295 enl+= markowitz_enlargement_front (*iei, cg, true); 00296 cv.push_back (v); } } 00297 00298 cv.resize (0); // reduce search space 00299 c_graph_t::oei_t oei, oe_end; 00300 tie (oei, oe_end)= out_edges (v, cg); 00301 for (; oei != oe_end; ++oei) { 00302 vertex_t v= target (*oei, cg); 00303 if (find (cv.begin(), cv.end(), v) == cv.end()) { 00304 enl+= markowitz_enlargement_back (*oei, cg, true); 00305 cv.push_back (v); } } 00306 return enl; 00307 } 00308 00309 struct markowitz_enlargement_front_t { 00310 c_graph_t::edge_t _e; // first edge is stored 00311 markowitz_enlargement_front_t (c_graph_t::edge_t e) : _e (e) {} 00312 int operator() (c_graph_t::edge_t e2, const c_graph_t& cg) const { 00313 return markowitz_enlargement_front (_e, e2, cg); } 00314 }; 00315 00316 struct markowitz_enlargement_back_t { 00317 c_graph_t::edge_t _e; // first edge is stored 00318 markowitz_enlargement_back_t (c_graph_t::edge_t e) : _e (e) {} 00319 int operator() (c_graph_t::edge_t e2, const c_graph_t& cg) const { 00320 return markowitz_enlargement_back (_e, e2, cg); } 00321 }; 00322 00323 00324 // ------------------------------------------------------------------------- 00325 // LMMD 00326 // ------------------------------------------------------------------------- 00327 00328 // operator that computes LMMD value for a single vertex 00329 struct lmmdv_op_t { 00330 double w; // weight 00331 lmmdv_op_t (double _w) : w (_w) {} 00332 int operator() (c_graph_t::vertex_t v, const c_graph_t& cg) { 00333 int markowitz= in_degree (v, cg) * out_degree (v, cg), 00334 damage= markowitz_enlargement_all_neighbors (v, cg); 00335 return int (double (markowitz) + w * double (damage)); } 00336 }; 00337 00338 int lmmd_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1, 00339 const c_graph_t& cg, 00340 vector<c_graph_t::vertex_t>& vv2) { 00341 lmmdv_op_t lmmdv_op (weight); 00342 return standard_heuristic_op (vv1, cg, vv2, lmmdv_op, *this); 00343 } 00344 00345 lmmd_vertex_t lmmd_vertex (1.0); 00346 00347 // ------------------------------------------------------------------------- 00348 // MOMR 00349 // ------------------------------------------------------------------------- 00350 00351 // operator that computes MOMR value for a single vertex 00352 struct momrv_op_t { 00353 int operator() (c_graph_t::vertex_t v, const c_graph_t& cg) { 00354 int momr= in_degree (v, cg) * out_degree (v, cg) 00355 - markowitz_enlargement_all_neighbors (v, cg); 00356 #ifndef NDEBUG 00357 c_graph_t gtmp (cg); vertex_elimination (v, gtmp); 00358 THROW_DEBUG_EXCEPT_MACRO (overall_markowitz_degree (cg) - overall_markowitz_degree (gtmp) != momr, 00359 consistency_exception, "momr not correct"); 00360 #endif 00361 return momr; } 00362 }; 00363 00364 int momr_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1, 00365 const c_graph_t& cg, 00366 vector<c_graph_t::vertex_t>& vv2) { 00367 momrv_op_t momrv_op; 00368 return standard_heuristic_op (vv1, cg, vv2, momrv_op, *this); 00369 } 00370 00371 momr_vertex_t momr_vertex; 00372 00373 // ------------------------------------------------------------------------- 00374 // subroutines of Maximal overall path length reduction 00375 // ------------------------------------------------------------------------- 00376 00377 // overall path length reduction of face (e1, e2) 00378 inline int oplr_face (c_graph_t::edge_t e1, c_graph_t::edge_t e2, 00379 const vector<int>& vni, const vector<int>& vli, 00380 const vector<int>& vno, const vector<int>& vlo, 00381 const c_graph_t& cg) { 00382 00383 // assert (target (e1, cg) == source (e2, cg)); 00384 THROW_DEBUG_EXCEPT_MACRO (target (e1, cg) != source (e2, cg), consistency_exception, 00385 "e1 and e2 does not match"); 00386 00387 c_graph_t::vertex_t p= source (e1, cg), s= target (e2, cg); 00388 00389 c_graph_t::edge_t e; 00390 bool found; 00391 boost::tie (e, found)= edge (p, s, cg); 00392 00393 return found ? vno[s] * (vni[p] + vli[p]) + vni[p] * (vno[s] + vlo[s]) 00394 : vni[p] * vno[s]; 00395 } 00396 00397 int oplr_edge_front (c_graph_t::edge_t e, 00398 const vector<int>& vni, const vector<int>& vli, 00399 const vector<int>& vno, const vector<int>& vlo, 00400 const c_graph_t& cg) { 00401 00402 int oplr= 0; 00403 graph_traits<c_graph_t>::out_edge_iterator oei, oe_end; 00404 tie (oei, oe_end)= out_edges (target (e, cg), cg); 00405 00406 for (; oei != oe_end; ++oei) 00407 oplr+= oplr_face (e, *oei, vni, vli, vno, vlo, cg); 00408 00409 return oplr; 00410 } 00411 00412 int oplr_edge_back (c_graph_t::edge_t e, 00413 const vector<int>& vni, const vector<int>& vli, 00414 const vector<int>& vno, const vector<int>& vlo, 00415 const c_graph_t& cg) { 00416 00417 int oplr= 0; 00418 graph_traits<c_graph_t>::in_edge_iterator iei, ie_end; 00419 tie (iei, ie_end)= in_edges (source (e, cg), cg); 00420 00421 for (; iei != ie_end; ++iei) 00422 oplr+= oplr_face (*iei, e, vni, vli, vno, vlo, cg); 00423 00424 return oplr; 00425 } 00426 00427 // ------------------------------------------------------------------------- 00428 // Maximal overall path length reduction 00429 // ------------------------------------------------------------------------- 00430 00431 // operator that computes path length reduction for a single vertex 00432 struct oplrv_op_t { 00433 vector<int> vni, vli, vno, vlo; 00434 oplrv_op_t (const c_graph_t& cg) { 00435 in_out_path_lengths (cg, vni, vli, vno, vlo); } 00436 int operator () (c_graph_t::vertex_t v, const c_graph_t& cg) { 00437 int oplr= 0; 00438 c_graph_t::iei_t iei, ie_end; 00439 for (tie (iei, ie_end)= in_edges (v, cg); iei != ie_end; ++iei) 00440 oplr+= oplr_edge_front (*iei, vni, vli, vno, vlo, cg); 00441 return oplr; } 00442 }; 00443 00444 int moplr_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1, 00445 const c_graph_t& cg, 00446 vector<c_graph_t::vertex_t>& vv2) { 00447 oplrv_op_t oplrv_op (cg); 00448 return standard_heuristic_op (vv1, cg, vv2, oplrv_op, *this); 00449 } 00450 00451 moplr_vertex_t moplr_vertex; 00452 00453 // ===================================================== 00454 // for edge elimination (in c-graph) 00455 // ===================================================== 00456 00457 int forward_mode_edge_f (const vector<c_graph_t::edge_t>& ev1, 00458 bool front, 00459 const c_graph_t& cg, 00460 vector<c_graph_t::edge_t>& ev2) { 00461 ev2.resize (0); 00462 00463 if (ev1.size() == 0) return 0; 00464 ev2.push_back (ev1[0]); 00465 00466 for (size_t c= 1; c < ev1.size(); c++) 00467 if (front ? inv_lex_less (ev1[c], ev2[0], cg) : lex_less (ev1[c], ev2[0], cg)) 00468 ev2[0]= ev1[c]; 00469 00470 return 1; 00471 } 00472 00473 // objective function for forward mode in edge elimination 00474 // works up to 47 million vertices in IEEE arithmetic 00475 inline double fme_obj (edge_bool_t eb, const c_graph_t& cg) { 00476 c_graph_t::edge_t edge= eb.first; 00477 // front is prefered -> add something if not front because we minimize 00478 int high, low, notfront; 00479 if (eb.second) high= target (edge, cg), low= source (edge, cg), notfront= 0; 00480 else high= source (edge, cg), low= target (edge, cg), notfront= 1; 00481 return (2 * high + notfront) * double (cg.x()) + low; 00482 } 00483 00484 int forward_mode_edge_t::operator() (const vector<edge_bool_t>& ev1, 00485 const c_graph_t& cg, 00486 vector<edge_bool_t>& ev2) { 00487 ev2.resize (0); 00488 if (ev1.size() == 0) {set_empty_objective (); return 0; } 00489 ev2.push_back (ev1[0]); 00490 00491 for (size_t c= 1; c < ev1.size(); c++) { 00492 // THROW_DEBUG_EXCEPT_MACRO (fme_obj (ev1[c], cg) < fme_obj (ev2[0], cg) != lex_less (ev1[c], ev2[0], cg), 00493 // consistency_exception, "objective function and comparator does not match"); 00494 if (lex_less (ev1[c], ev2[0], cg)) ev2[0]= ev1[c]; } 00495 set_objective (fme_obj (ev2[0], cg)); 00496 return 1; 00497 } 00498 00499 forward_mode_edge_t forward_mode_edge; 00500 00501 // remark fm: if all eliminatable edges are considered than only front elimination is used 00502 // this way one can force same sequences in vertex, edge and face elimination 00503 // when forward mode is used as sole criterion 00504 00505 // ------------------------------------------------------------------------- 00506 // reverse mode 00507 // ------------------------------------------------------------------------- 00508 00509 int reverse_mode_edge_f (const vector<c_graph_t::edge_t>& ev1, 00510 bool front, 00511 const c_graph_t& cg, 00512 vector<c_graph_t::edge_t>& ev2) { 00513 ev2.resize (0); 00514 00515 if (ev1.size() == 0) return 0; 00516 ev2.push_back (ev1[0]); 00517 00518 for (size_t c= 1; c < ev1.size(); c++) 00519 if (front ? inv_lex_greater (ev1[c], ev2[0], cg) : lex_greater (ev1[c], ev2[0], cg)) 00520 ev2[0]= ev1[c]; 00521 00522 return 1; 00523 } 00524 00525 // objective function for reverse mode in edge elimination 00526 // works up to 47 million vertices in IEEE arithmetic 00527 inline double rme_obj (edge_bool_t eb, const c_graph_t& cg) { 00528 c_graph_t::edge_t edge= eb.first; 00529 // front is prefered -> add something if front because we maximize 00530 int high, low, front; 00531 if (eb.second) high= target (edge, cg), low= source (edge, cg), front= 1; 00532 else high= source (edge, cg), low= target (edge, cg), front= 0; 00533 return (2 * high + front) * double (cg.x()) + low; 00534 } 00535 00536 int reverse_mode_edge_t::operator() (const vector<edge_bool_t>& ev1, 00537 const c_graph_t& cg, 00538 vector<edge_bool_t>& ev2) { 00539 ev2.resize (0); 00540 00541 if (ev1.size() == 0) {set_empty_objective (); return 0; } 00542 ev2.push_back (ev1[0]); 00543 00544 for (size_t c= 1; c < ev1.size(); c++) { 00545 // THROW_DEBUG_EXCEPT_MACRO ((rme_obj (ev1[c], cg) > rme_obj (ev2[0], cg)) != lex_greater (ev1[c], ev2[0], cg), 00546 // consistency_exception, "objective function and comparator does not match"); 00547 if (lex_greater (ev1[c], ev2[0], cg)) ev2[0]= ev1[c]; } 00548 set_objective (rme_obj (ev2[0], cg)); 00549 return 1; 00550 } 00551 00552 reverse_mode_edge_t reverse_mode_edge; 00553 00554 // remark rm: if all eliminatable edges are considered than only front elimination is used 00555 // this way one can force same sequences in vertex, edge and face elimination 00556 // when reverse mode is used as sole criterion 00557 00558 // ------------------------------------------------------------------------- 00559 // Lowest Markowitz 00560 // ------------------------------------------------------------------------- 00561 00562 int lowest_markowitz_edge_f (const vector<c_graph_t::edge_t>& ev1, 00563 bool front, 00564 const c_graph_t& cg, 00565 vector<c_graph_t::edge_t>& ev2) { 00566 ev2.resize (0); 00567 00568 if (ev1.size() == 0) return 0; 00569 int min_degree= front ? out_degree (target (ev1[0], cg), cg) 00570 : in_degree (source (ev1[0], cg), cg); 00571 ev2.push_back (ev1[0]); 00572 00573 for (size_t c= 1; c < ev1.size(); c++) { 00574 c_graph_t::edge_t e= ev1[c]; 00575 int degree= front ? out_degree (target (e, cg), cg) 00576 : in_degree (source (e, cg), cg); 00577 if (degree < min_degree) ev2.resize (0); 00578 if (degree <= min_degree) { 00579 ev2.push_back (e); min_degree= degree;} 00580 } 00581 return ev2.size(); 00582 } 00583 00584 // operator that computes the Markowitz degree for a single edge elimination 00585 struct lme_op_t { 00586 int operator() (edge_bool_t eb, const c_graph_t& cg) { 00587 return eb.second ? out_degree (target (eb.first, cg), cg) 00588 : in_degree (source (eb.first, cg), cg); } 00589 }; 00590 00591 int lowest_markowitz_edge_t::operator() (const vector<edge_bool_t>& ev1, 00592 const c_graph_t& cg, 00593 vector<edge_bool_t>& ev2) { 00594 lme_op_t lme_op; 00595 return standard_heuristic_op (ev1, cg, ev2, lme_op, *this); 00596 } 00597 00598 lowest_markowitz_edge_t lowest_markowitz_edge; 00599 00600 // ------------------------------------------------------------------------- 00601 // Lowest relative Markowitz 00602 // ------------------------------------------------------------------------- 00603 00604 int lowest_relative_markowitz_edge_f (const vector<c_graph_t::edge_t>& ev1, 00605 bool front, 00606 const c_graph_t& cg, 00607 vector<c_graph_t::edge_t>& ev2) { 00608 ev2.resize (0); 00609 if (ev1.size() == 0) return 0; 00610 lrm_op_t lrm_op (cg); 00611 int min_degree= lrm_op (front, ev1[0], cg); 00612 ev2.push_back (ev1[0]); 00613 00614 for (size_t c= 1; c < ev1.size(); c++) { 00615 int degree= lrm_op (front, ev1[c], cg); 00616 if (degree < min_degree) ev2.resize (0); 00617 if (degree <= min_degree) { 00618 ev2.push_back (ev1[c]); min_degree= degree;} } 00619 return ev2.size(); 00620 } 00621 00622 int lowest_relative_markowitz_edge_t::operator() (const vector<edge_bool_t>& ev1, 00623 const c_graph_t& cg, 00624 vector<edge_bool_t>& ev2) { 00625 lrm_op_t lrm_op (cg); 00626 return standard_heuristic_op (ev1, cg, ev2, lrm_op, *this); 00627 } 00628 00629 lowest_relative_markowitz_edge_t lowest_relative_markowitz_edge; 00630 00631 // ------------------------------------------------------------------------- 00632 // Lowest fill-in 00633 // ------------------------------------------------------------------------- 00634 00635 inline int fill_in_front (c_graph_t::edge_t e, const c_graph_t& cg) { 00636 return new_out_edges (e, cg); 00637 } 00638 00639 inline int fill_in_back (c_graph_t::edge_t e, const c_graph_t& cg) { 00640 return new_in_edges (e, cg); 00641 } 00642 00643 00644 int lowest_fill_in_edge_f (const vector<c_graph_t::edge_t>& ev1, 00645 bool front, 00646 const c_graph_t& cg, 00647 vector<c_graph_t::edge_t>& ev2) { 00648 ev2.resize (0); 00649 00650 if (ev1.size() == 0) return 0; 00651 int min_degree= front ? fill_in_front (ev1[0], cg) 00652 : fill_in_back (ev1[0], cg); 00653 ev2.push_back (ev1[0]); 00654 00655 for (size_t c= 1; c < ev1.size(); c++) { 00656 c_graph_t::edge_t e= ev1[c]; 00657 int degree= front ? fill_in_front (e, cg) 00658 : fill_in_back (e, cg); 00659 if (degree < min_degree) ev2.resize (0); 00660 if (degree <= min_degree) { 00661 ev2.push_back (e); min_degree= degree;} 00662 } 00663 00664 return ev2.size(); 00665 } 00666 00667 00668 // ------------------------------------------------------------------------- 00669 // LMMD 00670 // ------------------------------------------------------------------------- 00671 00672 lmmd_edge_t lmmd_edge (1.0); 00673 00674 inline int lmmd_edge_front (c_graph_t::edge_t e, double w, const c_graph_t& cg) { 00675 int markowitz= out_degree (target (e, cg), cg); 00676 markowitz_enlargement_front_t me (e); 00677 int damage= markowitz_enlargement_front (e, cg) 00678 + sum_over_all_out_edges (target (e, cg), cg, me); 00679 return int (double (markowitz) + w * double (damage)); 00680 } 00681 00682 inline int lmmd_edge_back (c_graph_t::edge_t e, double w, const c_graph_t& cg) { 00683 int markowitz= in_degree (source (e, cg), cg); 00684 markowitz_enlargement_back_t me (e); 00685 int damage= markowitz_enlargement_back (e, cg) 00686 + sum_over_all_in_edges (source (e, cg), cg, me); 00687 return int (double (markowitz) + w * double (damage)); 00688 } 00689 00690 struct lmmde_op_t { 00691 double w; // weight 00692 lmmde_op_t (double _w) : w (_w) {} 00693 int operator() (edge_bool_t eb, const c_graph_t& cg) { 00694 return eb.second ? lmmd_edge_front (eb.first, w, cg) 00695 : lmmd_edge_back (eb.first, w, cg); } 00696 }; 00697 00698 int lmmd_edge_t::operator() (const vector<edge_bool_t>& ev1, 00699 const c_graph_t& cg, 00700 vector<edge_bool_t>& ev2) { 00701 lmmde_op_t lmmde_op (weight); 00702 return standard_heuristic_op (ev1, cg, ev2, lmmde_op, *this); 00703 } 00704 00705 00706 // ------------------------------------------------------------------------- 00707 // MOMR 00708 // ------------------------------------------------------------------------- 00709 00710 inline int momr_edge_front (c_graph_t::edge_t e, const c_graph_t& cg) { 00711 00712 markowitz_enlargement_front_t me (e); 00713 int momr= out_degree (target (e, cg), cg) - markowitz_enlargement_front (e, cg) 00714 - sum_over_all_out_edges (target (e, cg), cg, me); 00715 00716 #ifndef NDEBUG 00717 c_graph_t gtmp (cg); 00718 00719 // eliminating e in gtmp does not work -> edge_descriptor from gtmp needed 00720 c_graph_t::edge_t etmp; 00721 c_graph_t::ei_t ei, e_end; 00722 c_graph_t::vertex_t s= source (e, cg), t= target (e, cg); 00723 for (boost::tie (ei, e_end)= edges (gtmp); ei != e_end; ++ei) 00724 if (source (*ei, gtmp) == s && target (*ei, gtmp) == t) { 00725 etmp= *ei; break; } 00726 // assert (ei != e_end); // otherwise edge not found 00727 THROW_DEBUG_EXCEPT_MACRO (ei == e_end, consistency_exception, "No matching edge found"); 00728 00729 front_edge_elimination (etmp, gtmp); 00730 // assert (overall_markowitz_degree (cg) - overall_markowitz_degree (gtmp) == momr); 00731 THROW_DEBUG_EXCEPT_MACRO (overall_markowitz_degree (cg) - overall_markowitz_degree (gtmp) != momr, 00732 consistency_exception, "momr not correct"); 00733 #endif 00734 return momr; 00735 } 00736 00737 inline int momr_edge_back (c_graph_t::edge_t e, const c_graph_t& cg) { 00738 // reduction of markowitz degree in vertex source (e) 00739 int momr= in_degree (source (e, cg), cg); 00740 // target (e) can get a larger markowitz degree due to new in_edges 00741 momr-= markowitz_enlargement_back (e, cg); 00742 00743 // the predecessors of source (e) can get a larger markowitz degree 00744 // due to a new out_edge to target (e) 00745 c_graph_t::iei_t iei, ie_end; 00746 tie (iei, ie_end)= in_edges (source (e, cg), cg); 00747 for (; iei != ie_end; ++iei) 00748 momr-= markowitz_enlargement_back (e, *iei, cg); 00749 #ifndef NDEBUG 00750 markowitz_enlargement_back_t me (e); 00751 int momr2= in_degree (source (e, cg), cg) - markowitz_enlargement_back (e, cg) 00752 - sum_over_all_in_edges (source (e, cg), cg, me); 00753 // assert (momr == momr2); 00754 THROW_DEBUG_EXCEPT_MACRO (momr2 != momr, consistency_exception, "momr not correct"); 00755 00756 c_graph_t gtmp (cg); 00757 c_graph_t::vi_t vi, v_end; 00758 int old_overall_markowitz= 0, new_overall_markowitz= 0; 00759 for (boost::tie (vi, v_end)= vertices (gtmp); vi != v_end; ++vi) 00760 old_overall_markowitz+= in_degree (*vi, gtmp) * out_degree (*vi, gtmp); 00761 00762 // eliminating e in gtmp does not work -> edge_descriptor from gtmp needed 00763 c_graph_t::edge_t etmp; 00764 c_graph_t::ei_t ei, e_end; 00765 c_graph_t::vertex_t s= source (e, cg), t= target (e, cg); 00766 for (boost::tie (ei, e_end)= edges (gtmp); ei != e_end; ++ei) 00767 if (source (*ei, gtmp) == s && target (*ei, gtmp) == t) { 00768 etmp= *ei; break; } 00769 // assert (ei != e_end); // otherwise edge not found 00770 THROW_DEBUG_EXCEPT_MACRO (ei == e_end, consistency_exception, "No matching edge found"); 00771 00772 back_edge_elimination (etmp, gtmp); 00773 for (boost::tie (vi, v_end)= vertices (gtmp); vi != v_end; ++vi) 00774 new_overall_markowitz+= in_degree (*vi, gtmp) * out_degree (*vi, gtmp); 00775 // assert (old_overall_markowitz-new_overall_markowitz == momr); 00776 THROW_DEBUG_EXCEPT_MACRO (old_overall_markowitz-new_overall_markowitz != momr, 00777 consistency_exception, "momr not correct"); 00778 #endif 00779 return momr; 00780 } 00781 00782 // operator for MOMR on edges 00783 struct momre_op_t { 00784 int operator() (bool front, c_graph_t::edge_t edge, const c_graph_t& cg) { 00785 return front ? momr_edge_front (edge, cg) : momr_edge_back (edge, cg); } 00786 int operator() (edge_bool_t eb, const c_graph_t& cg) { 00787 return eb.second ? momr_edge_front (eb.first, cg) : momr_edge_back (eb.first, cg); } 00788 }; 00789 00790 int momr_edge_f (const vector<c_graph_t::edge_t>& ev1, 00791 bool front, 00792 const c_graph_t& cg, 00793 vector<c_graph_t::edge_t>& ev2) { 00794 ev2.resize (0); 00795 if (ev1.size() == 0) return 0; 00796 momre_op_t momre_op; 00797 int max_momr= momre_op (front, ev1[0], cg); 00798 ev2.push_back (ev1[0]); 00799 00800 for (size_t c= 1; c < ev1.size(); c++) { 00801 int momr= momre_op (front, ev1[c], cg); 00802 if (momr > max_momr) ev2.resize (0); 00803 if (momr >= max_momr) { 00804 ev2.push_back (ev1[c]); max_momr= momr;} 00805 } 00806 return ev2.size(); 00807 } 00808 00809 int momr_edge_t::operator() (const vector<edge_bool_t>& ev1, const c_graph_t& cg, 00810 vector<edge_bool_t>& ev2) { 00811 momre_op_t momre_op; 00812 return standard_heuristic_op (ev1, cg, ev2, momre_op, *this); 00813 } 00814 00815 momr_edge_t momr_edge; 00816 00817 // ------------------------------------------------------------------------- 00818 // Minimal distance 00819 // ------------------------------------------------------------------------- 00820 00821 // operator for minimal distances on faces 00822 struct diste_op_t { 00823 int operator() (edge_bool_t eb, const c_graph_t& cg) { 00824 c_graph_t::vertex_t i= source (eb.first, cg), j= target (eb.first, cg), dist= 0; 00825 vector<c_graph_t::vertex_t> nb; 00826 if (eb.second) { 00827 successor_set (j, cg, nb); 00828 for (size_t c= 0; c < nb.size(); c++) 00829 if (nb[c] - i > dist) dist= nb[c] - i; 00830 } else { 00831 predecessor_set (j, cg, nb); 00832 for (size_t c= 0; c < nb.size(); c++) 00833 if (j - nb[c] > dist) dist= j - nb[c]; } 00834 THROW_DEBUG_EXCEPT_MACRO (dist <= 0, consistency_exception, "Wrong distance in edge elimination"); 00835 return dist; } 00836 }; 00837 00838 int minimal_distance_edge_t::operator() (const vector<edge_bool_t>& ev1, const c_graph_t& cg, 00839 vector<edge_bool_t>& ev2) { 00840 return standard_heuristic_op (ev1, cg, ev2, diste_op_t(), *this); 00841 } 00842 00843 minimal_distance_edge_t minimal_distance_edge; 00844 00845 // ------------------------------------------------------------------------- 00846 // Maximal overall path length reduction 00847 // ------------------------------------------------------------------------- 00848 00849 int moplr_edge (const vector<c_graph_t::edge_t>& ev1, 00850 bool front, 00851 const c_graph_t& cg, 00852 vector<c_graph_t::edge_t>& ev2) { 00853 ev2.resize (0); 00854 if (ev1.size() == 0) return 0; 00855 00856 vector<int> vni, vli, vno, vlo; 00857 in_out_path_lengths (cg, vni, vli, vno, vlo); 00858 00859 int max_oplr= front ? oplr_edge_front (ev1[0], vni, vli, vno, vlo, cg) 00860 : oplr_edge_back (ev1[0], vni, vli, vno, vlo, cg); 00861 ev2.push_back (ev1[0]); 00862 00863 for (size_t c= 1; c < ev1.size(); c++) { 00864 c_graph_t::edge_t e= ev1[c]; 00865 int oplr= front ? oplr_edge_front (e, vni, vli, vno, vlo, cg) 00866 : oplr_edge_back (e, vni, vli, vno, vlo, cg); 00867 if (oplr > max_oplr) ev2.resize (0); 00868 if (oplr >= max_oplr) { 00869 ev2.push_back (e); max_oplr= oplr;} 00870 } 00871 00872 return ev2.size(); 00873 } 00874 00875 00876 00877 // ===================================================== 00878 // for face elimination 00879 // ===================================================== 00880 00881 // objective function for forward and reverse mode in face elimination 00882 // works up to 165 thousands vertices in IEEE arithmetic 00883 inline double fmf_obj (line_graph_t::face_t f, const line_graph_t& lg) { 00884 int i, j, k, x= lg.x(); 00885 face_vertex_name (f, lg, i, j, k); 00886 return ((double (j) * double (x)) + double (i)) * double (x) + double (k); 00887 } 00888 00889 int forward_mode_face_t::operator() (const vector<line_graph_t::face_t>& fv1, 00890 const line_graph_t& lg, 00891 vector<line_graph_t::face_t>& fv2) { 00892 fv2.resize (0); 00893 if (fv1.size() == 0) {set_empty_objective (); return 0; } 00894 fv2.push_back (fv1[0]); 00895 00896 for (size_t c= 1; c < fv1.size(); c++) { 00897 // THROW_DEBUG_EXCEPT_MACRO (fmf_obj (fv1[c], lg) < fmf_obj (fv2[0], lg) != lex_less_face (fv1[c], fv2[0], lg), 00898 // consistency_exception, "objective function and comparator does not match"); 00899 if (lex_less_face (fv1[c], fv2[0], lg)) fv2[0]= fv1[c]; } 00900 set_objective (fmf_obj (fv2[0], lg)); 00901 return 1; 00902 } 00903 00904 forward_mode_face_t forward_mode_face; 00905 00906 // ------------------------------------------------------------------------- 00907 // reverse mode 00908 // ------------------------------------------------------------------------- 00909 00910 int reverse_mode_face_t::operator() (const vector<line_graph_t::face_t>& fv1, 00911 const line_graph_t& lg, 00912 vector<line_graph_t::face_t>& fv2) { 00913 fv2.resize (0); 00914 if (fv1.size() == 0) {set_empty_objective (); return 0; } 00915 fv2.push_back (fv1[0]); 00916 00917 for (size_t c= 1; c < fv1.size(); c++) { 00918 // THROW_DEBUG_EXCEPT_MACRO (fmf_obj (fv1[c], lg) < fmf_obj (fv2[0], lg) != lex_less_face (fv1[c], fv2[0], lg), 00919 // consistency_exception, "objective function and comparator does not match"); 00920 if (!lex_less_face (fv1[c], fv2[0], lg)) fv2[0]= fv1[c]; } 00921 set_objective (fmf_obj (fv2[0], lg)); 00922 return 1; 00923 } 00924 00925 reverse_mode_face_t reverse_mode_face; 00926 00927 int reverse_mode_face_whole_vertex_t::operator() (const vector<line_graph_t::face_t>& fv1, 00928 const line_graph_t& lg, 00929 vector<line_graph_t::face_t>& fv2) { 00930 fv2.resize (0); 00931 if (fv1.size() == 0) return 0; 00932 fv2.push_back (fv1[0]); 00933 line_graph_t::const_evn_t evn= get(boost::vertex_name, lg); 00934 00935 int maxv= evn[source(fv1[0], lg)].second; 00936 00937 for (size_t c= 1; c < fv1.size(); c++) { 00938 line_graph_t::face_t f= fv1[c]; 00939 int v= evn[source(f, lg)].second; 00940 if (v > maxv) {fv2.resize (0); maxv= v;} 00941 if (v == maxv) fv2.push_back (f); } 00942 00943 return fv2.size(); 00944 } 00945 00946 reverse_mode_face_whole_vertex_t reverse_mode_face_whole_vertex; 00947 00948 // ------------------------------------------------------------------------- 00949 // subroutine of Lowest Markowitz on line graph 00950 // ------------------------------------------------------------------------- 00951 00952 void markowitz_on_line_graph (const line_graph_t& lg, 00953 vector<int>& mdegree) { 00954 00955 line_graph_t::const_evn_t evn= get(vertex_name, lg); 00956 int max_vertex_cg= 0; 00957 line_graph_t::ei_t ei, e_end; 00958 for (boost::tie (ei, e_end)= vertices (lg); ei != e_end; ++ei) 00959 if (max_vertex_cg < evn[*ei].second) max_vertex_cg= evn[*ei].second; 00960 00961 // number of faces in which vertex j occurs in the center 00962 // filter out independent and dependent vertices (i,i,k) or (i,k,k) 00963 mdegree.resize (0); mdegree.resize (max_vertex_cg+1); 00964 line_graph_t::fi_t fi, f_end; 00965 for (boost::tie (fi, f_end)= edges (lg); fi != f_end; ++fi) { 00966 line_graph_t::edge_t s= source (*fi, lg), t= target (*fi, lg); 00967 if (evn[s].first != evn[s].second && evn[t].first != evn[t].second) 00968 mdegree[evn[s].second]++; } 00969 } 00970 00971 00972 00973 // ------------------------------------------------------------------------- 00974 // Lowest Markowitz 00975 // ------------------------------------------------------------------------- 00976 00977 // operator for lowest Markowitz on faces 00978 struct lmf_op_t { 00979 vector<int> mdegree; 00980 lmf_op_t (const line_graph_t& lg) { 00981 markowitz_on_line_graph (lg, mdegree); } 00982 int operator() (line_graph_t::face_t f, const line_graph_t& lg) { 00983 int i, j, k; face_vertex_name (f, lg, i, j, k); 00984 THROW_DEBUG_EXCEPT_MACRO (mdegree[j] == 0, consistency_exception, "Un-eliminatable face in fv1"); 00985 return mdegree[j]; } 00986 }; 00987 00988 int lowest_markowitz_face_t::operator() (const vector<line_graph_t::face_t>& fv1, 00989 const line_graph_t& lg, 00990 vector<line_graph_t::face_t>& fv2) { 00991 lmf_op_t lmf_op (lg); 00992 return standard_heuristic_op (fv1, lg, fv2, lmf_op, *this); 00993 } 00994 00995 00996 // ------------------------------------------------------------------------- 00997 // MOMR 00998 // ------------------------------------------------------------------------- 00999 01000 // will a face (p,i,k) from (i,j)'s predecessor (p,i) to (i,k) be inserted ? 01001 // or does it already exist 01002 class new_pik_t { 01003 int i, k; 01004 public: 01005 new_pik_t (int _i, int _k) : i (_i), k (_k) {} 01006 int operator() (line_graph_t::face_t pij, const line_graph_t& lg) const { 01007 line_graph_t::edge_t pi= source (pij, lg); 01008 // for independent edges, new faces doesn't affect Mark. -> stop 01009 if (vertex_type (pi, lg) == independent) return 0; 01010 line_graph_t::ofi_t ofi, of_end; 01011 for (tie (ofi, of_end)= out_edges (pi, lg); ofi != of_end; ++ofi) { 01012 int v1, v2; 01013 edge_vertex_name (target (*ofi, lg), lg, v1, v2); 01014 // assert (v1 == i); 01015 THROW_DEBUG_EXCEPT_MACRO (v1 != i, consistency_exception, "Adjacency corrupted in line graph"); 01016 if (v2 == k) return 0; } // (p,i,k) found 01017 return 1; 01018 } 01019 }; 01020 01021 struct source_not_independent_t { 01022 int operator() (line_graph_t::face_t f, const line_graph_t& lg) const { 01023 return (vertex_type (source (f, lg), lg) != independent); } 01024 }; 01025 01026 // will a face (i,k,s) to (j,k)'s successor (k,s) from (i,k) be inserted ? 01027 // or does it already exist 01028 class new_iks_t { 01029 int i, k; 01030 public: 01031 new_iks_t (int _i, int _k) : i (_i), k (_k) {} 01032 int operator() (line_graph_t::face_t jks, const line_graph_t& lg) const { 01033 line_graph_t::edge_t ks= target (jks, lg); 01034 // for dependent edges, new faces doesn't affect Mark. -> stop 01035 if (vertex_type (ks, lg) == dependent) return 0; 01036 line_graph_t::ifi_t ifi, if_end; 01037 for (tie (ifi, if_end)= in_edges (ks, lg); ifi != if_end; ++ifi) { 01038 int v1, v2; 01039 edge_vertex_name (source (*ifi, lg), lg, v1, v2); 01040 // assert (v2 == k); 01041 THROW_DEBUG_EXCEPT_MACRO (v2 != k, consistency_exception, "Adjacency corrupted in line graph"); 01042 if (v1 == i) return 0; } // (i,k,s) found 01043 return 1; 01044 } 01045 }; 01046 01047 struct target_not_dependent_t { 01048 int operator() (line_graph_t::face_t f, const line_graph_t& lg) const { 01049 return (vertex_type (target (f, lg), lg) != dependent); } 01050 }; 01051 01052 // operator for MOMR on faces 01053 struct momrf_op_t { 01054 int operator() (line_graph_t::face_t f, const line_graph_t& lg) { 01055 int momr= 1; // the face itself 01056 int i, j, k; // f's vertices w.r.t. c-graph 01057 face_vertex_name (f, lg, i, j, k); 01058 line_graph_t::edge_t ij= source (f, lg), jk= target (f, lg); 01059 01060 new_pik_t new_pik (i, k); 01061 momr-= sum_over_all_in_edges (ij, lg, new_pik); 01062 if (out_degree (ij, lg) == 1) 01063 momr+= sum_over_all_in_edges (ij, lg, source_not_independent_t()); 01064 01065 new_iks_t new_iks (i, k); 01066 momr-= sum_over_all_out_edges (jk, lg, new_iks); 01067 if (in_degree (jk, lg) == 1) 01068 momr+= sum_over_all_out_edges (jk, lg, target_not_dependent_t()); 01069 #ifndef NDEBUG 01070 line_graph_t gtmp (lg); 01071 01072 // eliminating f in gtmp does not work -> edge_descriptor from gtmp needed 01073 line_graph_t::face_t ftmp; 01074 ftmp= *same_edge (f, lg, gtmp); 01075 face_elimination (ftmp, gtmp); 01076 01077 int old_overall_markowitz= overall_markowitz_degree (lg); 01078 int new_overall_markowitz= overall_markowitz_degree (gtmp); 01079 if (old_overall_markowitz - new_overall_markowitz != momr) { 01080 write_graph ("AD edge before elimination", lg); 01081 line_graph_t::const_evn_t evn= get(vertex_name, lg); 01082 write_vertex_property (cout, "vertices of this edge graph", evn, lg); 01083 cout << "overall_markowitz_degree is " << old_overall_markowitz << "\n"; 01084 cout << "elimination of face: "; 01085 write_face_op_t wf (gtmp); wf (cout, ftmp); 01086 cout << endl; 01087 write_graph ("AD edge after elimination", gtmp); 01088 line_graph_t::evn_t evntmp= get(vertex_name, gtmp); 01089 write_vertex_property (cout, "vertices of this edge graph", evntmp, lg); 01090 cout << "overall_markowitz_degree is " << new_overall_markowitz 01091 << " momr is " << momr << "\n"; 01092 line_graph_t gtmp2 (lg); 01093 ftmp= *same_edge (f, lg, gtmp2); 01094 face_elimination (ftmp, gtmp2); 01095 } 01096 // assert (overall_markowitz_degree (lg) - overall_markowitz_degree (gtmp) == momr); 01097 THROW_DEBUG_EXCEPT_MACRO (overall_markowitz_degree (lg) - overall_markowitz_degree (gtmp) != momr, 01098 consistency_exception, "momr not correct"); 01099 #endif 01100 return momr; } 01101 }; 01102 01103 int momr_face_t::operator() (const vector<line_graph_t::face_t>& fv1, 01104 const line_graph_t& lg, 01105 vector<line_graph_t::face_t>& fv2) { 01106 momrf_op_t momrf_op; 01107 return standard_heuristic_op (fv1, lg, fv2, momrf_op, *this); 01108 } 01109 01110 momr_face_t momr_face; 01111 01112 // ------------------------------------------------------------------------- 01113 // Minimal distance 01114 // ------------------------------------------------------------------------- 01115 01116 // operator for minimal distances on faces 01117 struct distf_op_t { 01118 int operator() (line_graph_t::face_t f, const line_graph_t& lg) { 01119 int i, j, k; face_vertex_name (f, lg, i, j, k); 01120 return k - i; } 01121 }; 01122 01123 int minimal_distance_face_t::operator() (const vector<line_graph_t::face_t>& fv1, 01124 const line_graph_t& lg, vector<line_graph_t::face_t>& fv2) { 01125 return standard_heuristic_op (fv1, lg, fv2, distf_op_t(), *this); 01126 } 01127 01128 #ifdef USEXAIFBOOSTER 01129 01130 // ------------------------------------------------------------------------- 01131 // Scarcity preserving edge eliminations 01132 // ------------------------------------------------------------------------- 01133 int edge_elim_effect (const edge_bool_t be, 01134 const c_graph_t& angelLCG, 01135 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) { 01136 01137 boost::property_map<c_graph_t, EdgeType>::const_type eType = get(EdgeType(), angelLCG); 01138 c_graph_t::oei_t oei, oe_end; 01139 c_graph_t::iei_t iei, ie_end; 01140 c_graph_t::edge_t absorb_e; 01141 bool found_absorb; 01142 01143 c_graph_t::edge_t e = be.first; 01144 bool isFront = be.second; 01145 int nontrivialEdgeChange = 0; 01146 01147 // No awareness: removal of e decreases edge count 01148 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange--; 01149 // unit awareness: e must be nonunit for its removal to decrease nontrivial edges 01150 else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[e] != UNIT_EDGE) nontrivialEdgeChange--; 01151 // constant awareness: e must be variable for its removal to decrease nontrivial edges 01152 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[e] == VARIABLE_EDGE) nontrivialEdgeChange--; 01153 01154 if (isFront) { // front-elimination 01155 // if tgt(e) is isolated by the elimination 01156 if (in_degree (target (e, angelLCG), angelLCG) == 1) { 01157 for (tie (oei, oe_end) = out_edges (target (e, angelLCG), angelLCG); oei != oe_end; ++oei) { 01158 // all the outedges of tgt(e) will go away. we need to see how this affects nontrivial edge count 01159 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange--; 01160 else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*oei] != UNIT_EDGE) nontrivialEdgeChange--; 01161 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*oei] == VARIABLE_EDGE) nontrivialEdgeChange--; 01162 } // end all outedges of tgt(e) 01163 } 01164 01165 // determine effect of absorption/fill-in 01166 for (tie (oei, oe_end) = out_edges (target (e, angelLCG), angelLCG); oei != oe_end; ++oei) { 01167 tie (absorb_e, found_absorb) = edge (source (e, angelLCG), target (*oei, angelLCG), angelLCG); 01168 if (found_absorb) { // absorption 01169 //no awareness: no increase in edge count 01170 //unit awareness: absorb_e will be nonunit afterwards. increase only if absorb_e was previously unit 01171 if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange++; 01172 // constant awareness: increase if absorb edge is nonvariable and either e or *oei is variable 01173 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE) 01174 if (eType[e] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE) nontrivialEdgeChange++; 01175 } 01176 else { // fill-in 01177 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange++; 01178 // unit awareness: if either is nonunit, the fill-in is nonunit 01179 else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[e] != UNIT_EDGE || eType[*oei] != UNIT_EDGE)) nontrivialEdgeChange++; 01180 // constant awareness: if either is variable, the fill-in is variable 01181 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[e] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE)) nontrivialEdgeChange++; 01182 } 01183 } // end all successors of tgt(e) 01184 01185 } // end front-elimination 01186 else { // back-elimination 01187 01188 // consider in-edges lost due to isolating src(e) (requires src(e) is not dependent) 01189 if (out_degree (source (e, angelLCG), angelLCG) == 1 && vertex_type (source (e, angelLCG), angelLCG) != dependent) { 01190 for (tie (iei, ie_end) = in_edges (source (e, angelLCG), angelLCG); iei != ie_end; ++iei) { 01191 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange--; 01192 else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*iei] != UNIT_EDGE) nontrivialEdgeChange--; 01193 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*iei] == VARIABLE_EDGE) nontrivialEdgeChange--; 01194 } // end all inedges of src(e) 01195 } 01196 01197 // determine effect of absorption/fill-in 01198 for (tie (iei, ie_end) = in_edges (source (e, angelLCG), angelLCG); iei != ie_end; ++iei) { 01199 tie (absorb_e, found_absorb) = edge (source (*iei, angelLCG), target (e, angelLCG), angelLCG); 01200 if (found_absorb) { // absorption 01201 //no awareness: no increase in edge count 01202 //unit awareness: absorb_e will be nonunit afterwards. increase only if absorb_e was previously unit 01203 if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange++; 01204 // constant awareness: increase if absorb edge is nonvariable and either e or *oei is variable 01205 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE) 01206 if (eType[e] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE) nontrivialEdgeChange++; 01207 } 01208 else { // fill-in 01209 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange++; 01210 // unit awareness: if either is nonunit, the fill-in is nonunit 01211 else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[e] != UNIT_EDGE || eType[*iei] != UNIT_EDGE)) nontrivialEdgeChange++; 01212 // constant awareness: if either is variable, the fill-in is variable 01213 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[e] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)) nontrivialEdgeChange++; 01214 } 01215 } // end all predecessors of src(e) 01216 } // end back-elimination 01217 01218 return nontrivialEdgeChange; 01219 } 01220 01221 int edge_elim_effect(const EdgeElim ee, 01222 const c_graph_t& angelLCG, 01223 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) { 01224 return edge_elim_effect(make_pair(ee.getE(angelLCG), ee.isFront()), angelLCG, ourAwarenessLevel); 01225 } // end edge_elim_effect() 01226 01227 bool maintaining_edge_eliminations(const vector<EdgeElim>& bev1, 01228 const c_graph_t& angelLCG, 01229 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 01230 vector<EdgeElim>& bev2) { 01231 bev2.clear(); 01232 if (bev1.empty()) return 0; 01233 01234 for (size_t c = 0; c < bev1.size(); c++) 01235 if (edge_elim_effect (bev1[c], angelLCG, ourAwarenessLevel) <= 0) 01236 bev2.push_back (bev1[c]); 01237 01238 #ifndef NDEBUG 01239 cout << " Of " << bev1.size() << " edge eliminations passed to maintaining_edge_eliminations(), " << bev2.size() << " maintain the nontrivial edge count" << endl; 01240 #endif 01241 01242 if (bev2.empty()) { 01243 bev2 = bev1; 01244 return false; 01245 } 01246 else return true; 01247 } // end count_maintain_edge_eliminations() 01248 01249 bool reducing_edge_eliminations(const vector<EdgeElim>& bev1, 01250 const c_graph_t& angelLCG, 01251 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 01252 vector<EdgeElim>& bev2) { 01253 bev2.clear(); 01254 if (bev1.empty()) return 0; 01255 01256 for (size_t c = 0; c < bev1.size(); c++) 01257 if (edge_elim_effect (bev1[c], angelLCG, ourAwarenessLevel) < 0) 01258 bev2.push_back (bev1[c]); 01259 01260 #ifndef NDEBUG 01261 cout << " Of " << bev1.size() << " edge eliminations passed to reducing_edge_eliminations()" 01262 << ", " << bev2.size() << " reduce the nontrivial edge count" << endl; 01263 #endif 01264 01265 if(bev2.empty()) { 01266 bev2 = bev1; 01267 return false; 01268 } 01269 else return true; 01270 } // end count_maintain_edge_eliminations() 01271 01272 bool refill_avoiding_edge_eliminations(const vector<EdgeElim>& bev1, 01273 c_graph_t& angelLCG, 01274 const refillDependenceMap_t refillDependences, 01275 vector<EdgeElim>& bev2) { 01276 bev2.clear(); 01277 if (bev1.empty()) 01278 return 0; 01279 01280 c_graph_t::iei_t iei, ie_end; 01281 c_graph_t::oei_t oei, oe_end; 01282 refillDependenceMap_t::const_iterator depMap_i; 01283 vertex_set_t::const_iterator vDepSet_i; 01284 property_map<pure_c_graph_t, VertexVisited>::type visited = get(VertexVisited(), angelLCG); 01285 c_graph_t::vi_t cleari, clear_end; 01286 01287 for (size_t c = 0; c < bev1.size(); c++) { 01288 c_graph_t::edge_t e = bev1[c].getE(angelLCG); // the direction of elimination (front/back) doesn't matter 01289 01290 depMap_i = refillDependences.find(make_pair(source (e, angelLCG), target(e, angelLCG))); 01291 if (depMap_i != refillDependences.end()) { // we have refill dependences to consider for e 01292 #ifndef NDEBUG 01293 cout << "edge " << e << " has some refill dependences. Checking them..." << endl; 01294 #endif 01295 vertex_set_t vDepSet = depMap_i->second; // extract the vertex dependence set for e 01296 01297 // check all vertices that this edge depends on 01298 // the dependence vertex can't be both below tgt(e) and above src(e) 01299 for (vDepSet_i = vDepSet.begin(); vDepSet_i != vDepSet.end(); vDepSet_i++) { 01300 // clear visited property for all vertices 01301 for (tie(cleari, clear_end) = vertices(angelLCG); cleari != clear_end; ++cleari) visited[*cleari] = false; 01302 if (reachable (source (e, angelLCG), *vDepSet_i, angelLCG)) { 01303 // clear visited property for all vertices (again) 01304 for (tie(cleari, clear_end) = vertices(angelLCG); cleari != clear_end; ++cleari) visited[*cleari] = false; 01305 if (reachable (*vDepSet_i, target (e, angelLCG), angelLCG)) { 01306 #ifndef NDEBUG 01307 cout << "edge " << e << " has an unmet refill dependence on vertex " << *vDepSet_i << endl; 01308 #endif 01309 break; 01310 } // end if vertex dependency is not met 01311 } 01312 } // end all vertex dependences 01313 01314 // all vertex dependences for this edge have been met 01315 if (vDepSet_i == vDepSet.end()) 01316 bev2.push_back(bev1[c]); 01317 } // end if vertex dependences exist 01318 else bev2.push_back(bev1[c]); 01319 01320 } // end iterate over bev1 01321 01322 #ifndef NDEBUG 01323 cout << " Of " << bev1.size() << " edge eliminations passed to refill_avoiding_edge_eliminations(), " << bev2.size() << " don't violate refill dependences" << endl; 01324 #endif 01325 01326 if (bev2.empty()) { 01327 bev2 = bev1; 01328 return false; 01329 } 01330 else return true; 01331 } // end refill_avoiding_edge_eliminations() 01332 01333 bool rerouting_considerate_edge_eliminations(const vector<EdgeElim>& bev, 01334 const c_graph_t& angelLCG, 01335 const std::vector<Transformation>& transformationsPerformedV, 01336 vector<EdgeElim>& reroutingConsiderateEdgeElimsV) { 01337 reroutingConsiderateEdgeElimsV.clear(); 01338 if (bev.empty()) 01339 return false; 01340 01341 // Check every for every possible edge elimination 01342 for (size_t i = 0; i < bev.size(); i++) { 01343 size_t j; 01344 01345 if (bev[i].isFront()) { // front-elimination 01346 // check all previously performed reroutings to see if the edge elim undoes it 01347 for (j = 0; j < transformationsPerformedV.size(); j++) { 01348 if (transformationsPerformedV[j].isRerouting() 01349 && transformationsPerformedV[j].getRerouting().isPre() 01350 && source(transformationsPerformedV[j].getRerouting().getE(angelLCG), angelLCG) == bev[i].getSource() 01351 && source(transformationsPerformedV[j].getRerouting().getPivotE(angelLCG), angelLCG) == bev[i].getTarget()) 01352 break; 01353 } 01354 } // end front-elimination 01355 01356 else { // back-elimination 01357 for (j = 0; j < transformationsPerformedV.size(); j++) { 01358 if (transformationsPerformedV[j].isRerouting() 01359 && !transformationsPerformedV[j].getRerouting().isPre() 01360 && target(transformationsPerformedV[j].getRerouting().getE(angelLCG), angelLCG) == bev[i].getTarget() 01361 && target(transformationsPerformedV[j].getRerouting().getPivotE(angelLCG), angelLCG) == bev[i].getSource()) 01362 break; 01363 } // end all transformations 01364 } // end back-elimination 01365 01366 if (j == transformationsPerformedV.size()) 01367 reroutingConsiderateEdgeElimsV.push_back(bev[i]); 01368 } // end iterate over bev 01369 01370 #ifndef NDEBUG 01371 cout << " Of " << bev.size() << " edge eliminations passed to rerouting_considerate_edge_eliminations(), " << reroutingConsiderateEdgeElimsV.size() << " don't undo a rerouting" << endl; 01372 #endif 01373 01374 if (reroutingConsiderateEdgeElimsV.empty()) { 01375 reroutingConsiderateEdgeElimsV = bev; 01376 return false; 01377 } 01378 else return true; 01379 } // end rerouting_considerate_edge_eliminations() 01380 01381 unsigned int lowestMarkowitzEdgeElim(const vector<EdgeElim>& inEEV, 01382 const c_graph_t& angelLCG, 01383 vector<EdgeElim>& outEEV) { 01384 outEEV.clear(); 01385 if (inEEV.empty()) 01386 return 0; 01387 01388 vector<edge_bool_t> inBEV, outBEV; 01389 01390 for (size_t i = 0; i < inEEV.size(); i++) 01391 inBEV.push_back(inEEV[i].getBool(angelLCG)); 01392 01393 lowest_markowitz_edge(inBEV, angelLCG, outBEV); 01394 01395 for (size_t i = 0; i < outBEV.size(); i++) 01396 outEEV.push_back(EdgeElim (outBEV[i], angelLCG)); 01397 01398 return outEEV.size(); 01399 } // end lowestMarkowitzEdgeElim() 01400 01401 bool reverseModeEdgeElim(const vector<EdgeElim>& inEEV, 01402 const c_graph_t& angelLCG, 01403 vector<EdgeElim>& outEEV) { 01404 outEEV.clear(); 01405 if (inEEV.empty()) 01406 return false; 01407 01408 vector<edge_bool_t> inBEV, outBEV; 01409 01410 for (size_t i = 0; i < inEEV.size(); i++) 01411 inBEV.push_back(inEEV[i].getBool(angelLCG)); 01412 01413 reverse_mode_edge(inBEV, angelLCG, outBEV); 01414 01415 for (size_t i = 0; i < outBEV.size(); i++) 01416 outEEV.push_back(EdgeElim (outBEV[i], angelLCG)); 01417 01418 return true; 01419 } // end reverseModeEdgeElim() 01420 01421 // ============================================================================== 01422 // | FILTERS FOR REROUTINGS | 01423 // ============================================================================== 01424 01425 size_t noncyclicReroutings (const vector<Rerouting>& erv, 01426 const std::vector<Transformation>& transformationsPerformedV, 01427 const c_graph_t& angelLCG, 01428 vector<Rerouting>& noncyclicReroutingsV) { 01429 noncyclicReroutingsV.clear(); 01430 if (erv.empty()) 01431 return 0; 01432 size_t j; 01433 // check each rerouting in erv to see whether it has already been performed 01434 for (size_t i = 0; i < erv.size(); i++) { 01435 // go through the history 01436 for (j = 0; j < transformationsPerformedV.size(); j++) 01437 if (transformationsPerformedV[j].isRerouting() 01438 && transformationsPerformedV[j].getRerouting() == erv[i]); 01439 break; 01440 if (j == transformationsPerformedV.size()) // if it made it all the way through, the rerouting hasn't already been performed 01441 noncyclicReroutingsV.push_back(erv[i]); 01442 } // end iterate over erv 01443 return noncyclicReroutingsV.size(); 01444 } // end noncyclicReroutings() 01445 01446 /* 01447 bool maintaining_reroutings (const vector<edge_reroute_t>& erv, 01448 const c_graph_t& angelLCG, 01449 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 01450 vector<edge_reroute_t>& maintainingReroutingsV) { 01451 maintainingReroutingsV.clear(); 01452 if (erv.empty()) return 0; 01453 01454 bool dummyBool; 01455 01456 for (size_t i = 0; i < erv.size(); i++) { 01457 cout << "reroute_effect = " << reroute_effect(erv[i], angelLCG, ourAwarenessLevel, dummyBool) << endl; 01458 if (reroute_effect(erv[i], angelLCG, ourAwarenessLevel, dummyBool) <= 0) 01459 maintainingReroutingsV.push_back(erv[i]); 01460 } 01461 cout << "Of " << erv.size() << " reroutings passed to maintaining_reroutings(), " << maintainingReroutingsV.size() << " maintain the nontrivial edge count" << endl; 01462 01463 if (maintainingReroutingsV.empty()) { 01464 maintainingReroutingsV = erv; 01465 return false; 01466 } 01467 else return true; 01468 } // end maintaining_reroutings() 01469 */ 01470 01471 /* 01472 bool reducing_reroutings (const vector<edge_reroute_t>& erv, 01473 const c_graph_t& angelLCG, 01474 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 01475 vector<edge_reroute_t>& reducingReroutingsV) { 01476 reducingReroutingsV.clear(); 01477 if (erv.empty()) return 0; 01478 size_t i; 01479 01480 vector<edge_reroute_t> reducingReroutingstypes12V, reducingReroutingstype3V; 01481 01482 if (edge_reducing_rerouteElims_types12 (erv, angelLCG, ourAwarenessLevel, false, reducingReroutingstypes12V)) 01483 for (i = 0; i < reducingReroutingstypes12V.size(); i++) 01484 reducingReroutingsV.push_back(reducingReroutingstypes12V[i]); 01485 01486 if (edge_reducing_rerouteElims_type3 (erv, angelLCG, ourAwarenessLevel, false, reducingReroutingstype3V)) 01487 for (i = 0; i < reducingReroutingstype3V.size(); i++) 01488 reducingReroutingsV.push_back(reducingReroutingstype3V[i]); 01489 #ifndef NDEBUG 01490 cout << " Of " << erv.size() << " reroutings passed to reducing_reroutings(), " << reducingReroutingsV.size() << " reduce the nontrivial edge count when followed by elimination" << endl; 01491 #endif 01492 if (reducingReroutingsV.empty()) { 01493 //reducingReroutingsV = erv; 01494 return false; 01495 } 01496 else return true; 01497 } // end reducing_reroutings() 01498 */ 01499 01500 bool reducing_reroutings (const vector<Rerouting>& erv, 01501 const c_graph_t& angelLCG, 01502 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 01503 vector<Rerouting>& reducingReroutingsV) { 01504 reducingReroutingsV.clear(); 01505 if (erv.empty()) 01506 return 0; 01507 01508 boost::property_map<c_graph_t, EdgeType>::const_type eType = get(EdgeType(), angelLCG); 01509 c_graph_t::iei_t iei, ie_end; 01510 c_graph_t::oei_t oei, oe_end; 01511 c_graph_t::edge_t absorb_e, increment_absorb_e, decrement_absorb_e; 01512 bool found_absorb_e; 01513 01514 for (size_t i = 0; i < erv.size(); i++) { 01515 edge_reroute_t er = erv[i].getER(angelLCG); 01516 // first record effect of the rerouting itself 01517 bool incrementIsTrivial; 01518 int nontrivialEdgeChange_rerouting = reroute_effect (er, angelLCG, ourAwarenessLevel, incrementIsTrivial); 01519 01520 c_graph_t::edge_t e = er.e; 01521 c_graph_t::edge_t pe = er.pivot_e; 01522 er.pivot_eliminatable = false; 01523 er.increment_eliminatable = false; 01524 er.type3EdgeElimVector.clear(); 01525 01526 int nontrivialEdgeChange_elimIncrement = 0; 01527 int nontrivialEdgeChange_elimPivot = 0; 01528 01529 if (er.isPre) { // pre-routing 01530 //--------------------------------------------------------------------------------------------------------------------------- 01531 // determine effect of back-eliminating the increment edge on the nontrivial edge count (nontrivialEdgeChange_elimIncrement) 01532 //--------------------------------------------------------------------------------------------------------------------------- 01533 01534 // cannot back-eliminate the increment edge if src(e) is an independent 01535 if (in_degree (source (e, angelLCG), angelLCG) > 0) { 01536 // determine effect of removing the increment edge 01537 if (!incrementIsTrivial) nontrivialEdgeChange_elimIncrement--; 01538 01539 // examine effect of back-eliminating increment edge 01540 for (tie(iei, ie_end) = in_edges(source(e, angelLCG), angelLCG); iei != ie_end; ++iei) { 01541 tie(absorb_e, found_absorb_e) = edge(source(*iei, angelLCG), source(pe, angelLCG), angelLCG); 01542 if (found_absorb_e) { // absorption: count when the absorb_e goes from trivial to nontrivial 01543 if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange_elimIncrement++; 01544 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE) 01545 if (eType[*iei] == VARIABLE_EDGE || !incrementIsTrivial) nontrivialEdgeChange_elimIncrement++; 01546 } // end absorption 01547 else { // fill-in: is the fill-in trivial or not? 01548 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimIncrement++; 01549 else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[*iei] != UNIT_EDGE || !incrementIsTrivial)) nontrivialEdgeChange_elimIncrement++; 01550 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[*iei] == VARIABLE_EDGE || !incrementIsTrivial)) nontrivialEdgeChange_elimIncrement++; 01551 } // end fill-in 01552 } // end all preds of src(e) 01553 if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_elimIncrement < 0) er.increment_eliminatable = true; 01554 } // end if increment edge can be back-eliminated 01555 01556 //------------------------------------------------------------------------------------------------------------------------------------------------ 01557 // determine effect of front-eliminating the pivot edge on the nontrivial edge count (nontrivialEdgeChange_elimPivot) 01558 //------------------------------------------------------------------------------------------------------------------------------------------------ 01559 01560 // front-elimination of pivot edge MUST isolate the target 01561 if (in_degree(target(pe, angelLCG), angelLCG) == 2 && vertex_type(target(pe, angelLCG), angelLCG) != dependent) { 01562 01563 // determine effect of eliminating the pivot edge 01564 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimPivot--; 01565 else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[pe] != UNIT_EDGE) nontrivialEdgeChange_elimPivot--; 01566 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[pe] == VARIABLE_EDGE) nontrivialEdgeChange_elimPivot--; 01567 01568 // iterate over successors of tgt(pe); the fill/absorb edges will have the same source as the pivot edge 01569 for (tie (oei, oe_end) = out_edges(target(pe, angelLCG), angelLCG); oei != oe_end; ++oei) { 01570 // determine effect of removing *oei 01571 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimPivot--; 01572 else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*oei] != UNIT_EDGE) nontrivialEdgeChange_elimPivot--; 01573 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*oei] == VARIABLE_EDGE) nontrivialEdgeChange_elimPivot--; 01574 01575 tie (absorb_e, found_absorb_e) = edge (source(pe, angelLCG), target(*oei, angelLCG), angelLCG); 01576 if (found_absorb_e) { // absorption: we need to detect of it goes from trivial to nontrivial 01577 if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange_elimPivot++; 01578 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE) 01579 if (eType[pe] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE) nontrivialEdgeChange_elimPivot++; 01580 } // end absorption case 01581 else { // fill-in 01582 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimPivot++; 01583 else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[pe] != UNIT_EDGE || eType[*oei] != UNIT_EDGE)) nontrivialEdgeChange_elimPivot++; 01584 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[pe] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE)) nontrivialEdgeChange_elimPivot++; 01585 } // end fill-in case 01586 01587 } // end all successors of tgt(e)=tgt(pe) 01588 if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_elimPivot < 0) er.pivot_eliminatable = true; 01589 } // end determine nontrivialEdgeChange_elimPivot 01590 01591 //------------------------------------------------------------------------------------------------------------------------------------------------ 01592 // determine effect of back-eliminating (type 3) 01593 //------------------------------------------------------------------------------------------------------------------------------------------------ 01594 01595 // iterate over outedges of tgt(e), consider back-elimination of *oei 01596 for (tie(oei, oe_end) = out_edges(target(e, angelLCG), angelLCG); oei != oe_end; ++oei) { 01597 int nontrivialEdgeChange_backElimination = 0; 01598 01599 // consider loss of *oei 01600 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS 01601 || (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*oei] != UNIT_EDGE) 01602 || (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*oei] == VARIABLE_EDGE)) nontrivialEdgeChange_backElimination--; 01603 01604 // consider fill/absorb effect of back-eliminating *oei 01605 for (tie(iei, ie_end) = in_edges(target(e, angelLCG), angelLCG); iei != ie_end; ++iei) { 01606 if (*iei == e) continue; // skip the rerouted edge 01607 tie(absorb_e, found_absorb_e) = edge(source(*iei, angelLCG), target(*oei, angelLCG), angelLCG); 01608 if (found_absorb_e) { // absorption: only counts if it goes from trivial to nontrivial 01609 if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange_backElimination++; 01610 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE) 01611 if (eType[*oei] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE) nontrivialEdgeChange_backElimination++; 01612 } 01613 else { // fill-in 01614 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_backElimination++; 01615 else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[*oei] != UNIT_EDGE || eType[*iei] != UNIT_EDGE)) nontrivialEdgeChange_backElimination++; 01616 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[*oei] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)) nontrivialEdgeChange_backElimination++; 01617 } 01618 } // end all inedges of tgt(e) 01619 if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_backElimination < 0) er.type3EdgeElimVector.push_back(target(*oei, angelLCG)); 01620 } // end all outedges of tgt(e) (end type 3) 01621 01622 } // end pre-routing 01623 else { // post-routing 01624 01625 //------------------------------------------------------------------------------------------------------------------------------------------------ 01626 // determine effect of front-eliminating the increment edge on the nontrivial edge count 01627 //------------------------------------------------------------------------------------------------------------------------------------------------ 01628 01629 // cannot front-eliminate the increment edge if tgt(e) is a dependent 01630 if (vertex_type(target(e, angelLCG), angelLCG) != dependent) { 01631 // determine effect of removing the increment edge 01632 if (!incrementIsTrivial) nontrivialEdgeChange_elimIncrement--; 01633 01634 // examine effect of front-eliminating increment edge 01635 for (tie (oei, oe_end) = out_edges(target(e, angelLCG), angelLCG); oei != oe_end; ++oei) { 01636 tie (absorb_e, found_absorb_e) = edge(target(pe, angelLCG), target(*oei, angelLCG), angelLCG); 01637 if (found_absorb_e) { // absorption: count when the absorb_e goes from trivial to nontrivial 01638 if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange_elimIncrement++; 01639 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE) 01640 if (eType[*oei] == VARIABLE_EDGE || !incrementIsTrivial) nontrivialEdgeChange_elimIncrement++; 01641 } // end absorption 01642 else { // fill-in: is the fill-in trivial or not? 01643 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimIncrement++; 01644 else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[*oei] != UNIT_EDGE || !incrementIsTrivial)) nontrivialEdgeChange_elimIncrement++; 01645 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[*oei] == VARIABLE_EDGE || !incrementIsTrivial)) nontrivialEdgeChange_elimIncrement++; 01646 } // end fill-in 01647 } // end all preds of src(e) 01648 if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_elimIncrement < 0) er.increment_eliminatable = true; 01649 } // end if increment edge can be front-eliminated 01650 01651 //------------------------------------------------------------------------------------------------------------------------------------------------ 01652 // determine effect of back-eliminating the pivot edge on the nontrivial edge count 01653 //------------------------------------------------------------------------------------------------------------------------------------------------ 01654 01655 // front-elimination of pivot edge MUST isolate the target 01656 if (out_degree (source(pe, angelLCG), angelLCG) == 2 && in_degree (source(pe, angelLCG), angelLCG) > 0) { 01657 01658 // determine effect of eliminating the pivot edge 01659 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimPivot--; 01660 else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[pe] != UNIT_EDGE) nontrivialEdgeChange_elimPivot--; 01661 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[pe] == VARIABLE_EDGE) nontrivialEdgeChange_elimPivot--; 01662 01663 // iterate over predecessors of src(pe) 01664 // the fill/absorb edges will have the same target as the pivot edge 01665 for (tie (iei, ie_end) = in_edges(source(pe, angelLCG), angelLCG); iei != ie_end; ++iei) { 01666 // determine effect of removing the outedge 01667 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimPivot--; 01668 else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*iei] != UNIT_EDGE) nontrivialEdgeChange_elimPivot--; 01669 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*iei] == VARIABLE_EDGE) nontrivialEdgeChange_elimPivot--; 01670 01671 tie (absorb_e, found_absorb_e) = edge (source(*iei, angelLCG), target(pe, angelLCG), angelLCG); 01672 if (found_absorb_e) { // absorption: we need to detect of it goes from trivial to nontrivial 01673 if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange_elimPivot++; 01674 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE) 01675 if (eType[pe] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE) nontrivialEdgeChange_elimPivot++; 01676 } // end absorption case 01677 else { // fill-in 01678 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_elimPivot++; 01679 else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[pe] != UNIT_EDGE || eType[*iei] != UNIT_EDGE)) nontrivialEdgeChange_elimPivot++; 01680 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[pe] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)) nontrivialEdgeChange_elimPivot++; 01681 } // end fill-in case 01682 01683 } // end all successors of tgt(e)=tgt(pe) 01684 if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_elimPivot < 0) er.pivot_eliminatable = true; 01685 } // end determine nontrivialEdgeChange_elimPivot 01686 01687 //------------------------------------------------------------------------------------------------------------------------------------------------ 01688 // determine effect of front-eliminating (type 3) 01689 //------------------------------------------------------------------------------------------------------------------------------------------------ 01690 01691 // iterate over inedges of src(e), consider front-elimination of *iei 01692 if (vertex_type(source(e, angelLCG), angelLCG) != dependent) { 01693 for (tie(iei, ie_end) = in_edges(source(e, angelLCG), angelLCG); iei != ie_end; ++iei) { 01694 int nontrivialEdgeChange_frontElimination = 0; 01695 01696 // consider loss of *iei 01697 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS 01698 || (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*iei] != UNIT_EDGE) 01699 || (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*iei] == VARIABLE_EDGE)) nontrivialEdgeChange_frontElimination--; 01700 01701 // consider fill/absorb effect of front-eliminating *iei 01702 for (tie(oei, oe_end) = out_edges(source(e, angelLCG), angelLCG); oei != oe_end; ++oei) { 01703 if (*oei == e) continue; // skip the rerouted edge 01704 tie(absorb_e, found_absorb_e) = edge(source(*iei, angelLCG), target(*oei, angelLCG), angelLCG); 01705 if (found_absorb_e) { // absorption: only counts if it goes from trivial to nontrivial 01706 if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange_frontElimination++; 01707 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE) 01708 if (eType[*oei] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE) nontrivialEdgeChange_frontElimination++; 01709 } 01710 else { // fill-in 01711 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange_frontElimination++; 01712 else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[*oei] != UNIT_EDGE || eType[*iei] != UNIT_EDGE)) nontrivialEdgeChange_frontElimination++; 01713 else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[*oei] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)) nontrivialEdgeChange_frontElimination++; 01714 } // end fill-in 01715 } // end all outedges of src(e) 01716 if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_frontElimination < 0) er.type3EdgeElimVector.push_back(source(*iei, angelLCG)); 01717 } // end all inedges of src(e) 01718 } // end type 3 01719 } // end post-routing 01720 01721 if (er.pivot_eliminatable || er.increment_eliminatable || !er.type3EdgeElimVector.empty()) 01722 reducingReroutingsV.push_back(Rerouting (er, angelLCG)); 01723 01724 } // end iterate through erv 01725 01726 #ifndef NDEBUG 01727 cout << " Of " << erv.size() << " reroutings passed to reducing_reroutings(), " << reducingReroutingsV.size() << " reduce the nontrivial edge count when followed by elimination" << endl; 01728 #endif 01729 01730 return !reducingReroutingsV.empty(); 01731 } // end reducing_reroutings() 01732 01733 // ============================================================================== 01734 // | FILTERS FOR ELIMINATIONS AND REROUTINGS (TRANSFORMATIONS) | 01735 // ============================================================================== 01736 01737 int transformation_effect(const Transformation t, 01738 const c_graph_t& angelLCG, 01739 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) { 01740 int effect; 01741 if (t.isRerouting()) { 01742 bool dummy_incrementIsTrivial; 01743 effect = reroute_effect(t.getRerouting().getER(angelLCG), angelLCG, ourAwarenessLevel, dummy_incrementIsTrivial); 01744 } 01745 else 01746 effect = edge_elim_effect(t.getEdgeElim(), angelLCG, ourAwarenessLevel); 01747 return effect; 01748 } // end transformation_effect() 01749 01750 bool all_viable_transformations (c_graph_t& angelLCG, 01751 const std::vector<Transformation>& transformationsPerformedV, 01752 vector<Transformation>& allViableTransformationsV) { 01753 allViableTransformationsV.clear(); 01754 // find all eliminatable edges 01755 vector<EdgeElim> allEdgeElimsV; 01756 eliminatable_edges(angelLCG, allEdgeElimsV); 01757 for (size_t i = 0; i < allEdgeElimsV.size(); i++) 01758 allViableTransformationsV.push_back(Transformation (allEdgeElimsV[i])); 01759 // find viable reroutings 01760 vector<Rerouting> allReroutingsV, noncyclicReroutingsV; 01761 reroutable_edges (angelLCG, allReroutingsV); 01762 noncyclicReroutings (allReroutingsV, transformationsPerformedV, angelLCG, noncyclicReroutingsV); 01763 for (size_t i = 0; i < noncyclicReroutingsV.size(); i++) 01764 allViableTransformationsV.push_back(Transformation (noncyclicReroutingsV[i])); 01765 #ifndef NDEBUG 01766 cout << "\tThere are " << allEdgeElimsV.size() << " viable Edge eliminations in G" << endl; 01767 cout << "\tOf " << allReroutingsV.size() << " possible reroutings, " << noncyclicReroutingsV.size() << " are noncyclic" << endl; 01768 cout << "\t\tThere are " << allViableTransformationsV.size() << " viable transformations in G" << endl; 01769 #endif 01770 return !allViableTransformationsV.empty(); 01771 } // end all_viable_transformations() 01772 01773 bool maintaining_transformations(const vector<Transformation>& tv, 01774 const c_graph_t& angelLCG, 01775 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 01776 vector<Transformation>& maintainingTransformationsV) { 01777 maintainingTransformationsV.clear(); 01778 if (tv.empty()) 01779 return false; 01780 01781 vector<Rerouting> tempReroutingsV; 01782 vector<EdgeElim> tempEdgeElimsV, tempMaintainingEdgeElimsV; 01783 01784 // create temporary lists 01785 for (size_t i = 0; i < tv.size(); i++) 01786 tv[i].isRerouting() ? tempReroutingsV.push_back(tv[i].getRerouting()) 01787 : tempEdgeElimsV.push_back(tv[i].getEdgeElim()); 01788 01789 // if there are edge elims, push them to the transformation vector 01790 if (maintaining_edge_eliminations(tempEdgeElimsV, angelLCG, ourAwarenessLevel, tempMaintainingEdgeElimsV)) 01791 for (size_t i = 0; i < tempMaintainingEdgeElimsV.size(); i++) 01792 maintainingTransformationsV.push_back(Transformation (tempMaintainingEdgeElimsV[i])); 01793 01794 // push all reroutings to the transformation vector 01795 for (size_t i = 0; i < tempReroutingsV.size(); i++) 01796 maintainingTransformationsV.push_back(Transformation (tempReroutingsV[i])); 01797 01798 #ifndef NDEBUG 01799 cout << "Of " << tv.size() << " transformations passed to maintaining_transformations()" 01800 << ", " << maintainingTransformationsV.size() << " maintain the nontrivial edge count" << endl; 01801 #endif 01802 01803 // if there are neither edge elims nor reroutings, return the transformation vector we were passed 01804 if (maintainingTransformationsV.empty()) { 01805 maintainingTransformationsV = tv; 01806 return false; 01807 } 01808 else return true; 01809 } // end count_maintaining_transformations() 01810 01811 bool reducing_transformations(const vector<Transformation>& tv, 01812 const c_graph_t& angelLCG, 01813 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 01814 vector<Transformation>& reducingTransformationsV) { 01815 reducingTransformationsV.clear(); 01816 if (tv.empty()) 01817 return 0; 01818 01819 vector<Rerouting> tempReroutingsV, tempReducingReroutingsV; 01820 vector<EdgeElim> tempEdgeElimsV, tempReducingEdgeElimsV; 01821 01822 // split tv into separate temporary lists 01823 for (size_t i = 0; i < tv.size(); i++) 01824 tv[i].isRerouting() ? tempReroutingsV.push_back(tv[i].getRerouting()) 01825 : tempEdgeElimsV.push_back(tv[i].getEdgeElim()); 01826 01827 // if there are edge elims, push them to the transformation vector 01828 if (reducing_edge_eliminations(tempEdgeElimsV, angelLCG, ourAwarenessLevel, tempReducingEdgeElimsV)) 01829 for (size_t i = 0; i < tempReducingEdgeElimsV.size(); i++) 01830 reducingTransformationsV.push_back(Transformation (tempReducingEdgeElimsV[i])); 01831 01832 // if there are reroutings, push them to the transformation vector 01833 if (reducing_reroutings(tempReroutingsV, angelLCG, ourAwarenessLevel, tempReducingReroutingsV)) 01834 for (size_t i = 0; i < tempReducingReroutingsV.size(); i++) 01835 reducingTransformationsV.push_back(Transformation (tempReducingReroutingsV[i])); 01836 01837 #ifndef NDEBUG 01838 cout << "Of " << tv.size() << " transformations passed to reducing_transformations(), " << reducingTransformationsV.size() << " reduce the nontrivial edge count" << endl; 01839 #endif 01840 01841 // if there are neither edge elims nor reroutings, return only the edge elims 01842 if (reducingTransformationsV.empty()) { 01843 for (size_t i = 0; i < tempEdgeElimsV.size(); i++) // push back all the edge elims 01844 reducingTransformationsV.push_back(Transformation (tempEdgeElimsV[i])); 01845 // if there are no edge elims that maintain or reduce, and no reroutings that reduce: push back all edge elims 01846 if (reducingTransformationsV.empty()) { 01847 vector<EdgeElim> allEdgeElimsV; 01848 eliminatable_edges(angelLCG, allEdgeElimsV); 01849 for (size_t j = 0; j < allEdgeElimsV.size(); j++) 01850 reducingTransformationsV.push_back(Transformation (allEdgeElimsV[j])); 01851 } 01852 return false; 01853 } 01854 /* 01855 // if there are neither edge elims nor reroutings, return the transformation vector we were passed 01856 if (reducingTransformationsV.empty()) { 01857 reducingTransformationsV = tv; 01858 return false; 01859 } */ 01860 else return true; 01861 01862 } // end count_reducing_transformations() 01863 01864 bool refill_avoiding_transformations(const vector<Transformation>& tv, 01865 c_graph_t& angelLCG, 01866 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 01867 const refillDependenceMap_t& refillDependences, 01868 vector<Transformation>& refillAvoidingTransformationsV) { 01869 refillAvoidingTransformationsV.clear(); 01870 if (tv.empty()) 01871 return false; 01872 01873 vector<Rerouting> tempReroutingsV; 01874 vector<EdgeElim> tempEdgeElimsV, tempRefillAvoidingEdgeElimsV; 01875 01876 // create temporary edge elim and rerouting vectors 01877 for (size_t i = 0; i < tv.size(); i++) 01878 tv[i].isRerouting() ? tempReroutingsV.push_back(tv[i].getRerouting()) 01879 : tempEdgeElimsV.push_back(tv[i].getEdgeElim()); 01880 01881 // run edge elims through the refill filter 01882 if (refill_avoiding_edge_eliminations(tempEdgeElimsV, angelLCG, refillDependences, tempRefillAvoidingEdgeElimsV)) { 01883 // push refill avoiding edge elims to the transformation vector 01884 for (size_t i = 0; i < tempRefillAvoidingEdgeElimsV.size(); i++) 01885 refillAvoidingTransformationsV.push_back(Transformation (tempRefillAvoidingEdgeElimsV[i])); 01886 // push all reroutings to the transformation vector 01887 for (size_t i = 0; i < tempReroutingsV.size(); i++) 01888 refillAvoidingTransformationsV.push_back(Transformation (tempReroutingsV[i])); 01889 return true; 01890 } // end if refill avoiders were found 01891 01892 else { // none of the edge elims avoid refill 01893 refillAvoidingTransformationsV = tv; 01894 return false; 01895 } 01896 } // end refill_avoiding_transformations() 01897 01898 bool rerouting_considerate_transformations(const vector<Transformation>& tv, 01899 const c_graph_t& angelLCG, 01900 const std::vector<Transformation>& transformationsPerformedV, 01901 vector<Transformation>& reroutingConsiderateTransformationsV) { 01902 reroutingConsiderateTransformationsV.clear(); 01903 if (tv.empty()) 01904 return false; 01905 01906 vector<Transformation> tempReroutingsV; 01907 vector<EdgeElim> tempEdgeElimsV, tempReroutingConsiderateEdgeElimsV; 01908 01909 // create temporary edge elim and rerouting vectors 01910 for (size_t i = 0; i < tv.size(); i++) 01911 tv[i].isRerouting() ? tempReroutingsV.push_back(tv[i].getRerouting()) 01912 : tempEdgeElimsV.push_back(tv[i].getEdgeElim()); 01913 01914 // pass all edge elims through the edge elim filter 01915 if (rerouting_considerate_edge_eliminations(tempEdgeElimsV, angelLCG, transformationsPerformedV, tempReroutingConsiderateEdgeElimsV)) { 01916 // add preferred edge elims to the transformations vector to be returned 01917 for (size_t i = 0; i < tempReroutingConsiderateEdgeElimsV.size(); i++) 01918 reroutingConsiderateTransformationsV.push_back(Transformation (tempReroutingConsiderateEdgeElimsV[i])); 01919 // push all reroutings to the transformation vector 01920 for (size_t i = 0; i < tempReroutingsV.size(); i++) 01921 reroutingConsiderateTransformationsV.push_back(Transformation (tempReroutingsV[i])); 01922 return true; 01923 } // end if rerouting considerate edge elims were found 01924 01925 else { // none of the edge elims are rerouting considerate 01926 reroutingConsiderateTransformationsV = tv; 01927 return false; 01928 } 01929 } // end rerouting_considerate_transformations () 01930 01931 bool lowest_markowitz_transformations(const vector<Transformation>& tv, 01932 const c_graph_t& angelLCG, 01933 vector<Transformation>& lowestMarkowitzTransformationsV) { 01934 lowestMarkowitzTransformationsV.clear(); 01935 if (tv.empty()) 01936 return false; 01937 // create temporary edge elim vector 01938 vector<EdgeElim> tempEdgeElimsV, tempLowestMarkowitzEdgeElimsV; 01939 for (size_t i = 0; i < tv.size(); i++) 01940 if (!tv[i].isRerouting()) 01941 tempEdgeElimsV.push_back(tv[i].getEdgeElim()); 01942 // if no edge elims, return exactly what we got 01943 if (tempEdgeElimsV.empty()) { 01944 lowestMarkowitzTransformationsV = tv; 01945 return false; 01946 } 01947 lowestMarkowitzEdgeElim(tempEdgeElimsV, angelLCG, tempLowestMarkowitzEdgeElimsV); 01948 // add preferred edge elims to the transformations vector to be returned 01949 for (size_t i = 0; i < tempLowestMarkowitzEdgeElimsV.size(); i++) 01950 lowestMarkowitzTransformationsV.push_back(Transformation (tempLowestMarkowitzEdgeElimsV[i])); 01951 return true; 01952 } // end lowest_markowitz_transformations() 01953 01954 bool reverse_mode_transformations(const vector<Transformation>& tv, 01955 const c_graph_t& angelLCG, 01956 vector<Transformation>& reverseModeTransformationsV) { 01957 reverseModeTransformationsV.clear(); 01958 if (tv.empty()) 01959 return false; 01960 // create temporary edge elim vector 01961 vector<EdgeElim> tempEdgeElimsV, tempReverseModeEdgeElimsV; 01962 for (size_t i = 0; i < tv.size(); i++) 01963 if (!tv[i].isRerouting()) 01964 tempEdgeElimsV.push_back(tv[i].getEdgeElim()); 01965 // if no edge elims, return exactly what we got 01966 if (tempEdgeElimsV.empty()) { 01967 reverseModeTransformationsV = tv; 01968 return false; 01969 } 01970 reverseModeEdgeElim(tempEdgeElimsV, angelLCG, tempReverseModeEdgeElimsV); 01971 // add preferred edge elims to the transformations vector to be returned 01972 for (size_t i = 0; i < tempReverseModeEdgeElimsV.size(); i++) 01973 reverseModeTransformationsV.push_back(Transformation (tempReverseModeEdgeElimsV[i])); 01974 return true; 01975 } // end reverse_mode_transformations() 01976 01977 #endif // USEXAIFBOOSTER 01978 01979 } // namespace angel 01980 01981 // to do: some names are confusing, e.g. ev for a face vector