angel
mercurial changeset:
|
00001 // $Id: eliminations.cpp,v 1.13 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 #include "angel/include/eliminations.hpp" 00011 #include "angel/include/angel_tools.hpp" 00012 #include "angel/include/angel_io.hpp" 00013 00014 namespace angel { 00015 00016 using namespace std; 00017 using namespace boost; 00018 00019 // ========================================================================= 00020 // eliminations in c-graph 00021 // ========================================================================= 00022 00023 // ------------------------------------------------------------------------- 00024 // elimination of a single vertex in compute graph 00025 // ------------------------------------------------------------------------- 00026 00027 int vertex_elimination (c_graph_t::vertex_t v, c_graph_t& cg) { 00028 // vector used since eliminations invalidate iterators 00029 vector<c_graph_t::edge_t> ev; 00030 c_graph_t::oei_t oei, oe_end; 00031 for (tie (oei, oe_end)= out_edges (v, cg); oei != oe_end; ++oei) 00032 ev.push_back (*oei); 00033 00034 int costs= 0; 00035 for (size_t n= 0; n < ev.size(); n++) 00036 costs+= back_edge_elimination (ev[n], cg); 00037 // UN: print graph after elimination 00038 // graphviz_display(cg); 00039 return costs; 00040 } 00041 00042 // ------------------------------------------------------------------------- 00043 // elimination of a single egde in compute graph 00044 // ------------------------------------------------------------------------- 00045 00046 int front_edge_elimination (c_graph_t::edge_t edge_ij, c_graph_t& cg) { 00047 using boost::tie; 00048 00049 typedef c_graph_t::vertex_t vertex_t; 00050 typedef c_graph_t::edge_t edge_t; 00051 typedef c_graph_t::oei_t oei_t; 00052 c_graph_t::ew_t ew= get(edge_weight, cg); 00053 boost::property_map<c_graph_t, EdgeType>::type eType = get(EdgeType(), cg); 00054 // write_edge_property (std::cout, "edge weights ", ew, cg); 00055 00056 vertex_t i= source (edge_ij, cg), j= target (edge_ij, cg); 00057 00058 if (cg.vertex_type (j) == dependent) return 0; 00059 00060 int c_ji= ew[edge_ij]; 00061 // safe edges in vector because iterators will be invalidated 00062 oei_t oei, oe_end; 00063 std::vector<edge_t> ev; 00064 for (tie (oei, oe_end)= out_edges (j, cg); oei != oe_end; ++oei) 00065 ev.push_back (*oei); 00066 00067 for (size_t n= 0; n < ev.size(); n++) { 00068 edge_t edge_jk= ev[n]; 00069 vertex_t k= target (edge_jk, cg); 00070 int d= c_ji * ew[edge_jk]; 00071 00072 bool found_ik; 00073 edge_t edge_ik; 00074 tie (edge_ik, found_ik)= edge (i, k, cg); 00075 if (found_ik) { // absorption 00076 ew[edge_ik]+= d; 00077 if (eType[edge_ij] == VARIABLE_EDGE || eType[edge_jk] == VARIABLE_EDGE) eType[edge_ik] = VARIABLE_EDGE; 00078 else if (eType[edge_ik] != VARIABLE_EDGE) eType[edge_ik] = CONSTANT_EDGE; 00079 } 00080 else { // fill-in 00081 tie (edge_ik, found_ik)= add_edge (i, k, cg.next_edge_number++, cg); 00082 ew[edge_ik]= d; 00083 if (eType[edge_ij] == VARIABLE_EDGE || eType[edge_jk] == VARIABLE_EDGE) eType[edge_ik] = VARIABLE_EDGE; 00084 else if (eType[edge_ij] == UNIT_EDGE && eType[edge_jk] == UNIT_EDGE) eType[edge_ik] = UNIT_EDGE; 00085 else eType[edge_ik] = CONSTANT_EDGE; 00086 } 00087 } 00088 remove_edge (edge_ij, cg); 00089 00090 // if ij was the last in_edge of j then all out-edges (stored in ev) become unreachable 00091 // targets of out-edges shall be reachable by the set of edge_ik's 00092 if (in_degree (j, cg) == 0) 00093 for (size_t n= 0; n < ev.size(); n++) 00094 remove_edge (ev[n], cg); 00095 // is overkill: remove_unreachable_edges (j, cg); 00096 00097 return ev.size(); 00098 } 00099 00100 int back_edge_elimination (c_graph_t::edge_t edge_ij, c_graph_t& cg) { 00101 using namespace boost; 00102 using boost::tie; 00103 00104 typedef c_graph_t::vertex_t vertex_t; 00105 typedef c_graph_t::edge_t edge_t; 00106 typedef c_graph_t::iei_t iei_t; 00107 c_graph_t::ew_t ew= get(edge_weight, cg); 00108 boost::property_map<c_graph_t, EdgeType>::type eType = get(EdgeType(), cg); 00109 00110 vertex_t i= source (edge_ij, cg), j= target (edge_ij, cg); 00111 00112 if (cg.vertex_type (i) == independent) return 0; 00113 00114 int c_ji= ew[edge_ij]; 00115 // safe edges in vector because iterators will be invalidated 00116 iei_t iei, ie_end; 00117 std::vector<edge_t> ev; 00118 for (tie (iei, ie_end)= in_edges (i, cg); iei != ie_end; ++iei) 00119 ev.push_back (*iei); 00120 00121 for (size_t n= 0; n < ev.size(); n++) { 00122 edge_t edge_ki= ev[n]; 00123 vertex_t k= source (edge_ki, cg); 00124 int d= c_ji * ew[edge_ki]; 00125 00126 bool found_kj; 00127 edge_t edge_kj; 00128 tie (edge_kj, found_kj)= edge (k, j, cg); 00129 if (found_kj) { // absorption 00130 ew[edge_kj]+= d; 00131 if (eType[edge_ij] == VARIABLE_EDGE || eType[edge_ki] == VARIABLE_EDGE) eType[edge_kj] = VARIABLE_EDGE; 00132 else if (eType[edge_kj] != VARIABLE_EDGE) eType[edge_kj] = CONSTANT_EDGE; 00133 } 00134 else { // fill-in 00135 tie (edge_kj, found_kj)= add_edge (k, j, cg.next_edge_number++, cg); 00136 ew[edge_kj]= d; 00137 if (eType[edge_ij] == VARIABLE_EDGE || eType[edge_ki] == VARIABLE_EDGE) eType[edge_kj] = VARIABLE_EDGE; 00138 else if (eType[edge_ij] == UNIT_EDGE && eType[edge_ki] == UNIT_EDGE) eType[edge_kj] = UNIT_EDGE; 00139 else eType[edge_kj] = CONSTANT_EDGE; 00140 } 00141 } 00142 remove_edge (edge_ij, cg); 00143 00144 // if ij was the last out_edge of i then all in-edges (stored in ev) become irrelevant 00145 // except if i is a dependent vertex 00146 // sources of in-edges shall be relevant due to the set of edge_ik's 00147 if (out_degree (i, cg) == 0 && vertex_type (i, cg) != dependent) 00148 for (size_t n= 0; n < ev.size(); n++) 00149 remove_edge (ev[n], cg); 00150 // is overkill: remove_irrelevant_edges (i, cg); 00151 00152 return ev.size(); 00153 } 00154 00155 00156 00157 00158 00159 // ========================================================================= 00160 // eliminations in line graph 00161 // ========================================================================= 00162 00163 // ------------------------------------------------------------------------- 00164 // elimination of a single vertex in line graph 00165 // ------------------------------------------------------------------------- 00166 00167 int vertex_elimination (int j, line_graph_t& lg) { 00168 vector<line_graph_t::face_t> fv; 00169 line_graph_t::evn_t evn= get(vertex_name, lg); 00170 line_graph_t::ei_t ei, eend; 00171 for (tie (ei, eend)= vertices (lg); ei != eend; ++ei) 00172 if (evn[*ei].second == j) { 00173 line_graph_t::ofi_t ofi, of_end; 00174 for (tie (ofi, of_end)= out_edges (*ei, lg); ofi != of_end; ++ofi) 00175 fv.push_back (*ofi); 00176 } 00177 int costs= 0; 00178 for (size_t c= 0; c < fv.size(); c++) 00179 costs+= face_elimination (fv[c], lg); 00180 return costs; 00181 } 00182 00183 // ------------------------------------------------------------------------- 00184 // elimination of a single egde in line graph 00185 // ------------------------------------------------------------------------- 00186 00187 int front_edge_elimination (int i, int j, line_graph_t& lg) { 00188 vector<line_graph_t::edge_t> ev; 00189 find_edge (i, j, lg, ev); 00190 int costs= 0; 00191 for (size_t c= 0; c < ev.size(); c++) 00192 costs+= front_edge_elimination (ev[c], lg); 00193 00194 return costs; 00195 } 00196 00197 int front_edge_elimination (line_graph_t::edge_t vij, line_graph_t& lg) { 00198 std::vector<line_graph_t::face_t> fv; 00199 line_graph_t::ofi_t oi, oend; 00200 for (boost::tie (oi, oend)= out_edges (vij, lg); oi != oend; ++oi) 00201 fv.push_back (*oi); 00202 00203 int costs= 0; 00204 for (size_t n= 0; n < fv.size(); n++) 00205 costs+= face_elimination (fv[n], lg); 00206 00207 return costs; 00208 } 00209 00210 00211 int back_edge_elimination (int i, int j, line_graph_t& lg) { 00212 vector<line_graph_t::edge_t> ev; 00213 find_edge (i, j, lg, ev); 00214 int costs= 0; 00215 for (size_t c= 0; c < ev.size(); c++) 00216 costs+= back_edge_elimination (ev[c], lg); 00217 return costs; 00218 } 00219 00220 int back_edge_elimination (line_graph_t::edge_t vij, 00221 line_graph_t& lg) { 00222 std::vector<line_graph_t::face_t> fv; 00223 line_graph_t::ifi_t ii, iend; 00224 for (boost::tie (ii, iend)= in_edges (vij, lg); ii != iend; ++ii) 00225 fv.push_back (*ii); 00226 00227 int costs= 0; 00228 for (size_t n= 0; n < fv.size(); n++) 00229 costs+= face_elimination (fv[n], lg); 00230 00231 return costs; 00232 } 00233 00234 // ------------------------------------------------------------------------- 00235 // elimination of a single face in line graph 00236 // ------------------------------------------------------------------------- 00237 00238 int face_elimination (line_graph_t::face_t f, int kr, line_graph_t& lg, accu_graph_t& ac) { 00239 00240 typedef line_graph_t::edge_t edge_t; 00241 edge_t i= source (f, lg), j= target (f, lg); 00242 vector<edge_t> pi, sj, same_p, same_s, same; 00243 00244 if ((int) i >= lg.v() || (int) j >= lg.v()) { 00245 return -1;} 00246 00247 same_predecessors (i, lg, same_p); // same pred. as i 00248 same_successors (j, lg, same_s); 00249 same.resize (max (same_p.size(), same_s.size())); 00250 vector<edge_t>::iterator se= set_intersection (same_p.begin(), same_p.end(), same_s.begin(), 00251 same_s.end(), same.begin()); 00252 THROW_DEBUG_EXCEPT_MACRO (se-same.begin() >= 2, consistency_exception, 00253 "More than one mergeable vertex in face elimination"); 00254 00255 if (kr != -1) { 00256 if (se != same.begin()) { // if matching vertex found, it must be kr (k requested) 00257 if (same[0] != edge_t (kr)) return -1; 00258 } else { 00259 if (kr < lg.v()) { 00260 edge_t e= vertex (kr, lg); 00261 if (out_degree (e, lg) > 0 || in_degree (e, lg) > 0) { 00262 return -1; } } 00263 // insert enough empty vertices 00264 for (; kr > lg.v();) {add_vertex (lg); ac.exp_nr.push_back (-1); } 00265 } } 00266 00267 line_graph_t::ed_t el= get(vertex_degree, lg); // edge label 00268 int d= el[i] * el[j]; 00269 00270 THROW_DEBUG_EXCEPT_MACRO ((int) ac.exp_nr.size() != lg.v(), consistency_exception, 00271 "Array exp_nr has wrong size"); 00272 edge_t k; 00273 if (se != same.begin()) { // absorption 00274 k= same[0]; el[k]+= d; 00275 ac.accu_exp.resize (ac.accu_exp.size() + 1); 00276 ac.accu_exp[ac.accu_exp.size()-1].set_graph (k, i, j, ac.exp_nr); 00277 ac.exp_nr[k]= ac.accu_exp.size()-1; 00278 } else { // new or empty edge 00279 if (kr == -1 || kr == lg.v()) { 00280 k= add_vertex (lg); ac.exp_nr.push_back(-1); } 00281 else k= vertex (kr, lg); // this is an empty edge 00282 00283 ac.accu_exp.resize (ac.accu_exp.size() + 1); 00284 ac.accu_exp[ac.accu_exp.size()-1].set_graph(accu_exp_t::mult, i, j, ac.exp_nr); 00285 ac.exp_nr[k]= ac.accu_exp.size()-1; 00286 line_graph_t::evn_t evn= get(vertex_name, lg); 00287 // assert (evn[i].second == evn[j].first); // adjacent edges ? 00288 THROW_DEBUG_EXCEPT_MACRO (evn[i].second != evn[j].first, consistency_exception, 00289 "Adjacency corrupted in line graph"); 00290 evn[k]= make_pair (evn[i].first, evn[j].second); 00291 00292 sorted_predecessor_set (i, lg, pi); sorted_successor_set (j, lg, sj); 00293 for (size_t c= 0; c < pi.size(); c++) 00294 add_edge (pi[c], k, lg); 00295 for (size_t c= 0; c < sj.size(); c++) 00296 add_edge (k, sj[c], lg); 00297 el[k]= d; 00298 lg.cons_ok= false; 00299 } 00300 THROW_DEBUG_EXCEPT_MACRO (kr != -1 && edge_t (kr) != k, consistency_exception, 00301 "Inserted Vertex has wrong number"); 00302 00303 remove_edge (f, lg); 00304 00305 if (remove_irrelevant_edges (i, lg, true) > 0) // i is isolated 00306 lg.cons_ok= false; 00307 else { 00308 THROW_DEBUG_EXCEPT_MACRO (in_degree (i, lg) == 0 || out_degree (i, lg) == 0, consistency_exception, 00309 "Undetected isolated vertex"); 00310 vector<edge_t> same; 00311 same_neighbors (i, lg, same); 00312 THROW_DEBUG_EXCEPT_MACRO (same.size() >= 2, consistency_exception, 00313 "More than one mergeable vertex in face elimination"); 00314 if (same.size() > 0) { // mergeable vertex (edge in c-graph) 00315 edge_t i2= same[0]; 00316 el[i]+= el[i2]; 00317 clear_vertex (i2, lg); 00318 ac.accu_exp.resize (ac.accu_exp.size() + 1); 00319 ac.accu_exp[ac.accu_exp.size()-1].set_graph (accu_exp_t::add, i, i2, ac.exp_nr); 00320 ac.exp_nr[i]= ac.accu_exp.size()-1; 00321 lg.cons_ok= false;} 00322 } 00323 00324 if (remove_unreachable_edges (j, lg, true) > 0) // j is isolated 00325 lg.cons_ok= false; 00326 else { 00327 THROW_DEBUG_EXCEPT_MACRO (in_degree (j, lg) == 0 || out_degree (j, lg) == 0, consistency_exception, 00328 "Undetected isolated vertex"); 00329 vector<edge_t> same; 00330 same_neighbors (j, lg, same); 00331 THROW_DEBUG_EXCEPT_MACRO (same.size() >= 2, consistency_exception, 00332 "More than one mergeable vertex in face elimination"); 00333 if (same.size() > 0) { // mergeable vertex (edge) 00334 edge_t j2= same[0]; 00335 el[j]+= el[j2]; 00336 clear_vertex (j2, lg); 00337 ac.accu_exp.resize (ac.accu_exp.size() + 1); 00338 ac.accu_exp[ac.accu_exp.size()-1].set_graph (accu_exp_t::add, j, j2, ac.exp_nr); 00339 ac.exp_nr[j]= ac.accu_exp.size()-1; 00340 lg.cons_ok= false; } 00341 } 00342 00343 return k; 00344 } 00345 00346 // ========================================================================= 00347 // which vertices, edges or faces can be eliminated 00348 // ========================================================================= 00349 00350 int eliminatable_vertices (const c_graph_t& cg, vector<c_graph_t::vertex_t>& vv) { 00351 vv.resize (0); 00352 c_graph_t::vi_t vi, v_end; 00353 for (tie(vi, v_end)= vertices(cg); vi != v_end; ++vi) 00354 if (cg.vertex_type (*vi) == intermediate) // only intermediate vertices can be eliminated 00355 vv.push_back (*vi); 00356 return vv.size(); 00357 } 00358 00359 int semi_eliminatable_vertices (const c_graph_t& cg, vector<c_graph_t::vertex_t>& vv) { 00360 vv.resize (0); 00361 c_graph_t::vi_t vi, v_end; 00362 for (tie(vi, v_end)= vertices(cg); vi != v_end; ++vi) 00363 // either intermediate or dependent with outgoing edges 00364 if (cg.vertex_type (*vi) == intermediate 00365 || 00366 (cg.vertex_type (*vi) == dependent && out_degree (*vi, cg) > 0)) 00367 vv.push_back (*vi); 00368 return vv.size(); 00369 } 00370 00371 int eliminatable_edges (const c_graph_t& cg, 00372 std::vector<c_graph_t::edge_t>& ev) { 00373 // in fact it only copies the edges into a vector for better treatment 00374 ev.resize(0); 00375 c_graph_t::ei_t ei, e_end; 00376 for (tie (ei, e_end)= edges (cg); ei != e_end; ++ei) 00377 ev.push_back (*ei); 00378 return ev.size(); 00379 } 00380 00381 int front_eliminatable_edges (const c_graph_t& cg, 00382 std::vector<c_graph_t::edge_t>& ev) { 00383 // in fact it only copies the edges into a vector for better treatment 00384 ev.resize(0); 00385 c_graph_t::ei_t ei, e_end; 00386 for (tie (ei, e_end)= edges (cg); ei != e_end; ++ei) 00387 if (vertex_type (target (*ei, cg), cg) != dependent) 00388 ev.push_back (*ei); 00389 return ev.size(); 00390 } 00391 00392 int back_eliminatable_edges (const c_graph_t& cg, 00393 std::vector<c_graph_t::edge_t>& ev) { 00394 // in fact it only copies the edges into a vector for better treatment 00395 ev.resize(0); 00396 c_graph_t::ei_t ei, e_end; 00397 for (tie (ei, e_end)= edges (cg); ei != e_end; ++ei) 00398 if (vertex_type (source (*ei, cg), cg) != independent) 00399 ev.push_back (*ei); 00400 return ev.size(); 00401 } 00402 00403 int eliminatable_edges (const c_graph_t& cg, 00404 std::vector<edge_bool_t>& ev) { 00405 ev.resize(0); 00406 c_graph_t::ei_t ei, e_end; 00407 for (tie (ei, e_end)= edges (cg); ei != e_end; ++ei) { 00408 // can edge be back-eliminated ? 00409 if (vertex_type (source (*ei, cg), cg) != independent) 00410 ev.push_back (std::pair<c_graph_t::edge_t,bool> (*ei, false)); 00411 // can edge be front-eliminated ? 00412 if (vertex_type (target (*ei, cg), cg) != dependent) 00413 ev.push_back (std::pair<c_graph_t::edge_t,bool> (*ei, true)); 00414 } 00415 return ev.size(); 00416 } 00417 00418 int eliminatable_edges (const c_graph_t& cg, 00419 std::vector<edge_ij_elim_t>& ev) { 00420 ev.resize(0); 00421 c_graph_t::ei_t ei, e_end; 00422 for (tie (ei, e_end)= edges (cg); ei != e_end; ++ei) { 00423 edge_ij_elim_t ee (source (*ei, cg), target (*ei, cg), false); 00424 // can edge be back-eliminated ? 00425 if (vertex_type (source (*ei, cg), cg) != independent) 00426 ev.push_back (ee); 00427 // can edge be front-eliminated ? 00428 if (vertex_type (target (*ei, cg), cg) != dependent) { 00429 ee.front= true; ev.push_back (ee); } 00430 } 00431 return ev.size(); 00432 } 00433 00434 unsigned int eliminatable_edges(const c_graph_t& cg, 00435 std::vector<EdgeElim>& ev) { 00436 ev.clear(); 00437 c_graph_t::ei_t ei, e_end; 00438 for (tie(ei, e_end) = edges(cg); ei != e_end; ++ei) { 00439 // can edge be back-eliminated ? 00440 if (vertex_type(source(*ei, cg), cg) != independent) 00441 ev.push_back(EdgeElim (*ei, false, cg)); 00442 // can edge be front-eliminated ? 00443 if (vertex_type(target(*ei, cg), cg) != dependent) 00444 ev.push_back(EdgeElim (*ei, true, cg)); 00445 } // end iterate over all edges 00446 return ev.size(); 00447 } // end eliminatable_edges() 00448 00449 int eliminatable_faces (const line_graph_t& lg, 00450 std::vector<line_graph_t::face_t>& fv) { 00451 // in fact it only copies the edges into a vector for better treatment 00452 fv.resize(0); 00453 graph_traits<line_graph_t>::edge_iterator ei, e_end; 00454 for (tie (ei, e_end)= edges (lg); ei != e_end; ++ei) { 00455 line_graph_t::vertex_descriptor s= source (*ei, lg), t= target (*ei, lg); 00456 if (vertex_type (s, lg) != independent && vertex_type (t, lg) != dependent) 00457 fv.push_back (*ei); 00458 } 00459 return fv.size(); 00460 } 00461 00462 bool convert_elimination_sequence (const vector<c_graph_t::vertex_t>& vv, 00463 const c_graph_t& cg, 00464 vector<edge_ij_elim_t>& ev) { 00465 c_graph_t cgc (cg); 00466 ev.resize (0); 00467 for (size_t c= 0; c < vv.size(); c++) { 00468 c_graph_t::iei_t iei, ie_end; 00469 // cout << "conv_elim_seq: eliminate vertex " << vv[c]; 00470 // write_graph ("from graph", cgc); 00471 for (tie (iei, ie_end)= in_edges (vv[c], cgc); iei != ie_end; ++iei) { 00472 edge_ij_elim_t ee (source (*iei, cgc), target (*iei, cgc), true); 00473 // cout << "new edge " << ee; 00474 ev.push_back (ee); } 00475 // cout << endl; 00476 vertex_elimination (vv[c], cgc); } 00477 return true; 00478 } 00479 00480 bool convert_elimination_sequence (const vector<edge_ij_elim_t>& ev, 00481 const line_graph_t& lg, 00482 vector<triplet_t>& tv) { 00483 line_graph_t lgc (lg); 00484 tv.resize (0); 00485 for (size_t c= 0; c < ev.size(); c++) { 00486 edge_ij_elim_t ee = ev[c]; 00487 vector<line_graph_t::edge_t> lev; 00488 // cout << "conv_elim_seq: eliminate edge " << ee; 00489 // write_graph ("from graph", lgc); 00490 // line_graph_t::evn_t evn= get(vertex_name, lgc); 00491 // write_vertex_property (cout, "vertices of this edge graph", evn, lgc); 00492 // std::cout << "dealing with edge elim: " << ee.i << " to " << ee.j << std::endl; 00493 line_graph_t::edge_t ledge; 00494 00495 #ifndef NDEBUG 00496 cout << endl; 00497 cout << "convert_elimination_sequence: eliminate edge " << ee; 00498 write_graph ("from line graph: ", lgc); 00499 line_graph_t::evn_t evn = get(vertex_name, lgc); 00500 write_vertex_property (cout, "Labels of vertices in this line graph: ", evn, lgc); 00501 #endif 00502 00503 bool found = find_edge (ee.i, ee.j, lgc, lev); 00504 THROW_EXCEPT_MACRO (!found || lev.empty(), consistency_exception, "LCG edge has no corresponding line graph node"); 00505 00506 if (lev.size() == 1) { ledge = lev[0]; } 00507 else { // if lev.size() != 1 00508 cout << lev.size() << " line graph nodes correspond to LCG edge (" << ee.i << ", " << ee.j << ")." 00509 << " Determining the correct one..."; 00510 vector<line_graph_t::edge_t> candidates; 00511 // iterate through corresponding line graph vertices to ensure only one of them isn't isolated 00512 for (size_t l = 0; l < lev.size(); l++) { 00513 if (in_degree(lev[l], lgc) > 0 || out_degree(lev[l], lgc) > 0) candidates.push_back(lev[l]); 00514 } 00515 THROW_EXCEPT_MACRO (candidates.empty(), consistency_exception, "all corresponding line graph nodes are isolated"); 00516 THROW_EXCEPT_MACRO (candidates.size() > 1, consistency_exception, "multiple non-isolated corresponding line graph nodes"); 00517 00518 cout << " Unique correlation found!\n"; 00519 ledge = candidates[0]; 00520 } // end lev.size() != 1 00521 00522 if (ee.front) { 00523 line_graph_t::ofi_t oi, oend; 00524 for (boost::tie (oi, oend) = out_edges (ledge, lgc); oi != oend; ++oi) { 00525 triplet_t t (ledge, target (*oi, lgc), -1); tv.push_back (t); 00526 #ifndef NDEBUG 00527 cout << "new face " << t << endl; 00528 #endif 00529 } 00530 front_edge_elimination (ee.i, ee.j, lgc); 00531 } else { 00532 line_graph_t::ifi_t ii, iend; 00533 for (boost::tie (ii, iend) = in_edges (ledge, lgc); ii != iend; ++ii) { 00534 triplet_t t (source (*ii, lgc), ledge, -1); tv.push_back (t); 00535 #ifndef NDEBUG 00536 cout << "new face " << t << endl; 00537 #endif 00538 } 00539 back_edge_elimination (ee.i, ee.j, lgc); } 00540 } // end all edge eliminations 00541 return true; 00542 } // end convert_elimination_sequence() 00543 00544 #ifdef USEXAIFBOOSTER 00545 //############################################################################################################ 00546 // DIRECT ELIMINATIONS 00547 00548 EdgeRefType_E getRefType (const c_graph_t::edge_t e, const c_graph_t& angelLCG, const list<EdgeRef_t>& edge_ref_list) { 00549 c_graph_t::const_eind_t eind = get(edge_index, angelLCG); 00550 for (list<EdgeRef_t>::const_iterator ref_it = edge_ref_list.begin(); ref_it != edge_ref_list.end(); ref_it++) 00551 if (source (e, angelLCG) == source (ref_it->my_angelLCGedge, angelLCG) && 00552 target (e, angelLCG) == target (ref_it->my_angelLCGedge, angelLCG)) { 00553 THROW_EXCEPT_MACRO (ref_it->my_type == UNDEFINED, consistency_exception, "requested edge reference type is UNDEFINED"); 00554 return ref_it->my_type; 00555 } 00556 THROW_EXCEPT_MACRO (true, consistency_exception, "can't return reference type - no reference entry could be found for edge"); 00557 } // end getRef_type () 00558 00559 const xaifBoosterCrossCountryInterface::LinearizedComputationalGraphEdge* getLCG_p (const c_graph_t::edge_t e, 00560 const c_graph_t& angelLCG, 00561 const list<EdgeRef_t>& edge_ref_list) { 00562 c_graph_t::const_eind_t eind = get(edge_index, angelLCG); 00563 for (list<EdgeRef_t>::const_iterator ref_it = edge_ref_list.begin(); ref_it != edge_ref_list.end(); ref_it++) 00564 if (source (e, angelLCG) == source (ref_it->my_angelLCGedge, angelLCG) && 00565 target (e, angelLCG) == target (ref_it->my_angelLCGedge, angelLCG)) { 00566 THROW_EXCEPT_MACRO (ref_it->my_LCG_edge_p == NULL, consistency_exception, "requested LCG edge pointer is NULL"); 00567 return ref_it->my_LCG_edge_p; 00568 } 00569 THROW_EXCEPT_MACRO (true, consistency_exception, "can't return LCG_p - no reference entry could be found for edge"); 00570 } // end getLCG_p () 00571 00572 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex* getJAE_p (const c_graph_t::edge_t e, 00573 const c_graph_t& angelLCG, 00574 const list<EdgeRef_t>& edge_ref_list) { 00575 c_graph_t::const_eind_t eind = get(edge_index, angelLCG); 00576 for (list<EdgeRef_t>::const_iterator ref_it = edge_ref_list.begin(); ref_it != edge_ref_list.end(); ref_it++) 00577 if (source (e, angelLCG) == source (ref_it->my_angelLCGedge, angelLCG) && 00578 target (e, angelLCG) == target (ref_it->my_angelLCGedge, angelLCG)) { 00579 THROW_EXCEPT_MACRO (ref_it->my_JAE_vertex_p == NULL, consistency_exception, "requested JAE vertex pointer is NULL"); 00580 return ref_it->my_JAE_vertex_p; 00581 } 00582 THROW_EXCEPT_MACRO (true, consistency_exception, "can't return JAE_p - no reference entry could be found for edge"); 00583 } // end getJAE_p () 00584 00585 void setJaevRef (const c_graph_t::edge_t e, 00586 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex& jaev, 00587 const c_graph_t& angelLCG, 00588 const list<EdgeRef_t>& edge_ref_list) { 00589 EdgeRefType_E e_ref_type = getRefType (e, angelLCG, edge_ref_list); 00590 if (e_ref_type == LCG_EDGE) { 00591 const xaifBoosterCrossCountryInterface::LinearizedComputationalGraphEdge* LCG_p = getLCG_p (e, angelLCG, edge_ref_list); 00592 jaev.setExternalReference (*LCG_p); 00593 } 00594 else if (e_ref_type == JAE_VERT) { 00595 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex* JAE_p = getJAE_p (e, angelLCG, edge_ref_list); 00596 jaev.setInternalReference (*JAE_p); 00597 } 00598 else THROW_EXCEPT_MACRO (true, consistency_exception, "cannot set JAE vertex ref because edge reference type is UNDEFINED"); 00599 } // end setJaevRef () 00600 00601 void removeRef (const c_graph_t::edge_t e, 00602 const c_graph_t& angelLCG, 00603 list<EdgeRef_t>& edge_ref_list) { 00604 for (list<EdgeRef_t>::iterator ref_it = edge_ref_list.begin(); ref_it != edge_ref_list.end(); ref_it++) 00605 if (source (e, angelLCG) == source (ref_it->my_angelLCGedge, angelLCG) && 00606 target (e, angelLCG) == target (ref_it->my_angelLCGedge, angelLCG)) { 00607 edge_ref_list.erase(ref_it); 00608 return; 00609 } 00610 THROW_EXCEPT_MACRO (true, consistency_exception, "couldn't find edge reference in order to remove it"); 00611 } // end removeRef() 00612 00613 // Creates a new JAE corresponding to multiplying edges e1 and e2 00614 // where e1 comes before e2 00615 unsigned int multiply_edge_pair_directly (const c_graph_t::edge_t e1, 00616 const c_graph_t::edge_t e2, 00617 c_graph_t& angelLCG, 00618 list<EdgeRef_t>& edge_ref_list, 00619 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionList& jae_list) { 00620 00621 // Create JAE with vertices for multiply and for the two edges being multiplied 00622 xaifBoosterCrossCountryInterface::JacobianAccumulationExpression& new_jae = jae_list.addExpression(); 00623 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex& jaev_mult = new_jae.addVertex(); 00624 jaev_mult.setOperation (xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex::MULT_OP); 00625 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex& jaev_e1 = new_jae.addVertex(); 00626 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex& jaev_e2 = new_jae.addVertex(); 00627 setJaevRef (e1, jaev_e1, angelLCG, edge_ref_list); 00628 setJaevRef (e2, jaev_e2, angelLCG, edge_ref_list); 00629 new_jae.addEdge(jaev_e1, jaev_mult); 00630 new_jae.addEdge(jaev_e2, jaev_mult); 00631 00632 boost::property_map<c_graph_t, EdgeType>::type eType = get (EdgeType(), angelLCG); 00633 00634 //test for absorption 00635 c_graph_t::edge_t fill_or_absorb_e; 00636 bool found_absorb_e; 00637 tie (fill_or_absorb_e, found_absorb_e) = edge (source (e1, angelLCG), target (e2, angelLCG), angelLCG); 00638 if (found_absorb_e) { // absorption 00639 //create add vertex and absorb vertex, connect them up 00640 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex& jaev_add = new_jae.addVertex(); 00641 jaev_add.setOperation (xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex::ADD_OP); 00642 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex& jaev_absorb_e = new_jae.addVertex(); 00643 setJaevRef (fill_or_absorb_e, jaev_absorb_e, angelLCG, edge_ref_list); 00644 new_jae.addEdge(jaev_absorb_e, jaev_add); 00645 new_jae.addEdge(jaev_mult, jaev_add); 00646 00647 // reset reference for the absorb edge 00648 removeRef (fill_or_absorb_e, angelLCG, edge_ref_list); 00649 EdgeRef_t absorb_e_ref (fill_or_absorb_e, &jaev_add); 00650 edge_ref_list.push_back(absorb_e_ref); 00651 00652 // set edge type for absorption edge 00653 if (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE) eType[fill_or_absorb_e] = VARIABLE_EDGE; 00654 else if (eType[fill_or_absorb_e] != VARIABLE_EDGE) eType[fill_or_absorb_e] = CONSTANT_EDGE; 00655 } 00656 else { // fill-in 00657 tie (fill_or_absorb_e, found_absorb_e) = add_edge (source (e1, angelLCG), target (e2, angelLCG), angelLCG.next_edge_number++, angelLCG); 00658 EdgeRef_t fill_e_ref (fill_or_absorb_e, &jaev_mult); 00659 edge_ref_list.push_back(fill_e_ref); //point the fill-in edge at the top of the new JAE 00660 00661 // set edge type for new fill-in edge 00662 if (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE) eType[fill_or_absorb_e] = VARIABLE_EDGE; 00663 else if (eType[e1] == UNIT_EDGE && eType[e2] == UNIT_EDGE) eType[fill_or_absorb_e] = UNIT_EDGE; 00664 else eType[fill_or_absorb_e] = CONSTANT_EDGE; 00665 } 00666 00667 if (eType[e1] == UNIT_EDGE || eType[e2] == UNIT_EDGE) 00668 return 0; 00669 else 00670 return 1; 00671 } // end multiply_edge_pair_directly 00672 00673 unsigned int front_eliminate_edge_directly (c_graph_t::edge_t e, 00674 c_graph_t& angelLCG, 00675 list<EdgeRef_t>& edge_ref_list, 00676 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionList& jae_list) { 00677 #ifndef NDEBUG 00678 cout << "front eliminating edge " << e << endl; 00679 #endif 00680 00681 unsigned int cost = 0; 00682 c_graph_t::vertex_t tgt = target (e, angelLCG); 00683 vector<c_graph_t::edge_t> tgtOutEdges; 00684 c_graph_t::oei_t oei, oe_end; 00685 00686 // save out-edges of tgt in a vector, as pointers become invalidated 00687 for (tie (oei, oe_end) = out_edges (tgt, angelLCG); oei != oe_end; ++oei) 00688 tgtOutEdges.push_back(*oei); 00689 00690 // multiply all edge pairs 00691 for (size_t i = 0; i < tgtOutEdges.size(); i++) 00692 cost += multiply_edge_pair_directly (e, tgtOutEdges[i], angelLCG, edge_ref_list, jae_list); 00693 00694 // remove tgt of e and incident edges if it becomes isolated 00695 if (in_degree (tgt, angelLCG) == 1) 00696 for (size_t i = 0; i < tgtOutEdges.size(); i++) { 00697 removeRef (tgtOutEdges[i], angelLCG, edge_ref_list); 00698 remove_edge (tgtOutEdges[i], angelLCG); 00699 } 00700 00701 removeRef (e, angelLCG, edge_ref_list); 00702 remove_edge (e, angelLCG); 00703 return cost; 00704 } // end front_eliminate_edge_directly() 00705 00706 unsigned int back_eliminate_edge_directly (c_graph_t::edge_t e, 00707 c_graph_t& angelLCG, 00708 list<EdgeRef_t>& edge_ref_list, 00709 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionList& jae_list) { 00710 #ifndef NDEBUG 00711 cout << "back eliminating edge " << e << endl; 00712 #endif 00713 00714 unsigned int cost = 0; 00715 c_graph_t::vertex_t src = source (e, angelLCG); 00716 vector<c_graph_t::edge_t> srcInEdges; 00717 c_graph_t::iei_t iei, ie_end; 00718 00719 // save in-edges of src in a vector, as pointers become invalidated 00720 for (tie (iei, ie_end) = in_edges (src, angelLCG); iei != ie_end; ++iei) 00721 srcInEdges.push_back(*iei); 00722 00723 // multiply all edge pairs 00724 for (size_t i = 0; i < srcInEdges.size(); i++) 00725 cost += multiply_edge_pair_directly (srcInEdges[i], e, angelLCG, edge_ref_list, jae_list); 00726 00727 // remove src of e and incident edges if it becomes isolated and isn't a dependent 00728 if (out_degree (src, angelLCG) == 1 && vertex_type (src, angelLCG) != dependent) 00729 for (size_t i = 0; i < srcInEdges.size(); i++) { 00730 removeRef (srcInEdges[i], angelLCG, edge_ref_list); 00731 remove_edge (srcInEdges[i], angelLCG); 00732 } 00733 00734 removeRef (e, angelLCG, edge_ref_list); 00735 remove_edge (e, angelLCG); 00736 return cost; 00737 } // end back_eliminate_edge_directly() 00738 00739 unsigned int pair_elim (c_graph_t::edge_t e1, 00740 c_graph_t::edge_t e2, 00741 c_graph_t& angelLCG, 00742 const elimSeq_cost_t& currentElimSeq, 00743 refillDependenceMap_t& refillDependences) { 00744 boost::property_map<c_graph_t, EdgeType>::type eType = get (EdgeType(), angelLCG); 00745 c_graph_t::edge_t fill_or_absorb_e; 00746 bool found_absorb_e; 00747 00748 // determine whether absorption edge is present 00749 tie (fill_or_absorb_e, found_absorb_e) = edge (source (e1, angelLCG), target (e2, angelLCG), angelLCG); 00750 if (found_absorb_e) { // absorption - all we have to do is set the edge type for the absorption edge 00751 if (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE) eType[fill_or_absorb_e] = VARIABLE_EDGE; 00752 else if (eType[fill_or_absorb_e] != VARIABLE_EDGE) eType[fill_or_absorb_e] = CONSTANT_EDGE; 00753 } 00754 else { // fill-in 00755 00756 // check for refill. If found, add tgt to dependence vertex set for respective edge (from src to succ of tgt) 00757 for (size_t c = 0; c < currentElimSeq.edgeElimVector.size(); c++) { 00758 unsigned int i = currentElimSeq.edgeElimVector[c].getSource(); 00759 unsigned int j = currentElimSeq.edgeElimVector[c].getTarget(); 00760 if (source (e1, angelLCG) == i && target (e2, angelLCG) == j) { 00761 #ifndef NDEBUG 00762 cout << endl << "refilledge (" << i << "," << j << "), adding this information to the refillDependences map..." << endl << endl; 00763 #endif 00764 // add vertex to the refill dependence set for the refilled edge 00765 refillDependenceMap_t::iterator depMap_i = refillDependences.find(make_pair(i, j)); 00766 if (depMap_i == refillDependences.end()) { 00767 #ifndef NDEBUG 00768 cout << "the edge was not found as a map key. Creating new map key and empty set..." << endl; 00769 #endif 00770 // add the edge to the map if it isnt there 00771 depMap_i = refillDependences.insert( std::make_pair(make_pair(i, j), vertex_set_t()) ).first; 00772 currentElimSeq.revealedNewDependence = true; 00773 } 00774 bool wasntPresent = (depMap_i->second).insert(target (e1, angelLCG)).second; // add the vertex to the depSet for the current edge 00775 if (wasntPresent) currentElimSeq.revealedNewDependence = true; 00776 // refill has already been found for this edge, so break 00777 break; 00778 } // end if fill edge is found to have been previously eliminated (refill) 00779 } // end all previous elims in current sequence 00780 00781 // create the fill-in edge and set it's edge type 00782 tie (fill_or_absorb_e, found_absorb_e) = add_edge (source (e1, angelLCG), target (e2, angelLCG), angelLCG.next_edge_number++, angelLCG); 00783 if (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE) eType[fill_or_absorb_e] = VARIABLE_EDGE; 00784 else if (eType[e1] == UNIT_EDGE && eType[e2] == UNIT_EDGE) eType[fill_or_absorb_e] = UNIT_EDGE; 00785 else eType[fill_or_absorb_e] = CONSTANT_EDGE; 00786 } // end fill-in 00787 00788 if (eType[e1] == UNIT_EDGE || eType[e2] == UNIT_EDGE) 00789 return 0; 00790 else 00791 return 1; 00792 } // end pair_elim() 00793 00794 unsigned int front_elim (c_graph_t::edge_t e, 00795 c_graph_t& angelLCG, 00796 const elimSeq_cost_t& currentElimSeq, 00797 refillDependenceMap_t& refillDependences) { 00798 #ifndef NDEBUG 00799 cout << "front eliminating edge " << e << endl; 00800 #endif 00801 00802 unsigned int cost = 0; 00803 c_graph_t::oei_t oei, oe_end; 00804 vector<c_graph_t::edge_t> tgtOutEdges; 00805 00806 // save out-edges of tgt in a vector, as pointers become invalidated 00807 for (tie (oei, oe_end) = out_edges (target (e, angelLCG), angelLCG); oei != oe_end; ++oei) 00808 tgtOutEdges.push_back(*oei); 00809 00810 for (size_t i = 0; i < tgtOutEdges.size(); i++) 00811 cost += pair_elim (e, tgtOutEdges[i], angelLCG, currentElimSeq, refillDependences); 00812 00813 // if elimination isolates the target, remove vertex and incident edges 00814 if (in_degree (target (e, angelLCG), angelLCG) == 1) 00815 for (size_t i = 0; i < tgtOutEdges.size(); i++) 00816 remove_edge (tgtOutEdges[i], angelLCG); 00817 00818 remove_edge (e, angelLCG); 00819 return cost; 00820 } // end front_elim() 00821 00822 unsigned int back_elim (c_graph_t::edge_t e, 00823 c_graph_t& angelLCG, 00824 const elimSeq_cost_t& currentElimSeq, 00825 refillDependenceMap_t& refillDependences) { 00826 #ifndef NDEBUG 00827 cout << "back eliminating edge " << e << endl; 00828 #endif 00829 00830 unsigned int cost = 0; 00831 c_graph_t::iei_t iei, ie_end; 00832 vector<c_graph_t::edge_t> srcInEdges; 00833 00834 // save in-edges of src in a vector, as pointers become invalidated 00835 for (tie (iei, ie_end) = in_edges (source (e, angelLCG), angelLCG); iei != ie_end; ++iei) 00836 srcInEdges.push_back(*iei); 00837 00838 for (size_t i = 0; i < srcInEdges.size(); i++) 00839 cost += pair_elim (srcInEdges[i], e, angelLCG, currentElimSeq, refillDependences); 00840 00841 // remove src of e and incident edges if it becomes isolated and isn't a dependent 00842 if (out_degree (source (e, angelLCG), angelLCG) == 1 && vertex_type (source (e, angelLCG), angelLCG) != dependent) 00843 for (size_t i = 0; i < srcInEdges.size(); i++) 00844 remove_edge (srcInEdges[i], angelLCG); 00845 00846 remove_edge (e, angelLCG); 00847 return cost; 00848 } // end back_elim() 00849 00850 unsigned int pairElim_noJAE (c_graph_t::edge_t e1, 00851 c_graph_t::edge_t e2, 00852 c_graph_t& angelLCG, 00853 const transformationSeq_cost_t* currentTransformationSequence, 00854 refillDependenceMap_t& refillDependences) { 00855 boost::property_map<c_graph_t, EdgeType>::type eType = get (EdgeType(), angelLCG); 00856 c_graph_t::edge_t fill_or_absorb_e; 00857 bool found_absorb_e; 00858 00859 // check for refill. If found, add tgt to dependence vertex set for respective edge (from src to succ of tgt) 00860 for (size_t c = 0; c < currentTransformationSequence->transformationVector.size(); c++) { 00861 if (currentTransformationSequence->transformationVector[c].isRerouting()) 00862 continue; // ignore reroutings 00863 00864 unsigned int i = currentTransformationSequence->transformationVector[c].getEdgeElim().getSource(); 00865 unsigned int j = currentTransformationSequence->transformationVector[c].getEdgeElim().getTarget(); 00866 00867 // the fill/absorb edge was previously eliminated 00868 if (source (e1, angelLCG) == i && target (e2, angelLCG) == j) { 00869 #ifndef NDEBUG 00870 cout << endl << "refilledge (" << i << "," << j << "), adding this information to the refillDependences map..." << endl << endl; 00871 #endif 00872 // add vertex to the refill dependence set for the refilled edge 00873 refillDependenceMap_t::iterator depMap_i = refillDependences.find(make_pair(i, j)); 00874 if (depMap_i == refillDependences.end()) { // map doesn't contain a key for the refilled edge 00875 #ifndef NDEBUG 00876 cout << "the edge was not found as a map key. Creating new map key with empty vertex set..." << endl; 00877 #endif 00878 // add the edge to the map if it isnt there 00879 depMap_i = refillDependences.insert( std::make_pair(make_pair(i, j), vertex_set_t()) ).first; 00880 currentTransformationSequence->revealedNewDependence = true; // edge newly added as map key 00881 } 00882 00883 // add the vertex to the depSet for the current edge 00884 if ((depMap_i->second).insert(target (e1, angelLCG)).second) 00885 currentTransformationSequence->revealedNewDependence = true; // vertex newly added to dependence set for edge 00886 00887 break; // refill has already been found for this edge, so break 00888 } // end if fill/absorb edge is found to have been previously eliminated (refill) 00889 } // end all previous elims in current sequence 00890 00891 // determine whether absorption edge is present 00892 tie (fill_or_absorb_e, found_absorb_e) = edge (source (e1, angelLCG), target (e2, angelLCG), angelLCG); 00893 if (found_absorb_e) { // absorption: all we have to do is set the edge type for the absorption edge 00894 if (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE) eType[fill_or_absorb_e] = VARIABLE_EDGE; 00895 else if (eType[fill_or_absorb_e] != VARIABLE_EDGE) eType[fill_or_absorb_e] = CONSTANT_EDGE; 00896 } // end absorption 00897 else { // fill-in: create new edge and set it's edge type 00898 tie (fill_or_absorb_e, found_absorb_e) = add_edge (source (e1, angelLCG), target (e2, angelLCG), angelLCG.next_edge_number++, angelLCG); 00899 if (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE) eType[fill_or_absorb_e] = VARIABLE_EDGE; 00900 else if (eType[e1] == UNIT_EDGE && eType[e2] == UNIT_EDGE) eType[fill_or_absorb_e] = UNIT_EDGE; 00901 else eType[fill_or_absorb_e] = CONSTANT_EDGE; 00902 } // end fill-in 00903 00904 if (eType[e1] == UNIT_EDGE || eType[e2] == UNIT_EDGE) 00905 return 0; 00906 else return 1; 00907 } // end pairElim_noJAE() 00908 00909 unsigned int frontEdgeElimination_noJAE (c_graph_t::edge_t e, 00910 c_graph_t& angelLCG, 00911 const transformationSeq_cost_t* currentTransformationSequence, 00912 refillDependenceMap_t& refillDependences) { 00913 #ifndef NDEBUG 00914 cout << "front eliminating edge " << e << "\t(without creating any JAEs)" << endl; 00915 #endif 00916 00917 unsigned int cost = 0; 00918 c_graph_t::oei_t oei, oe_end; 00919 vector<c_graph_t::edge_t> tgtOutEdges; 00920 00921 // save out-edges of tgt in a vector, as pointers become invalidated 00922 for (tie (oei, oe_end) = out_edges (target (e, angelLCG), angelLCG); oei != oe_end; ++oei) 00923 tgtOutEdges.push_back(*oei); 00924 00925 for (size_t i = 0; i < tgtOutEdges.size(); i++) 00926 cost += pairElim_noJAE (e, tgtOutEdges[i], angelLCG, currentTransformationSequence, refillDependences); 00927 00928 // if elimination isolates the target, remove vertex and incident edges 00929 if (in_degree (target (e, angelLCG), angelLCG) == 1) 00930 for (size_t i = 0; i < tgtOutEdges.size(); i++) 00931 remove_edge (tgtOutEdges[i], angelLCG); 00932 00933 remove_edge (e, angelLCG); 00934 return cost; 00935 } // end frontEdgeElimination_noJAE() 00936 00937 unsigned int backEdgeElimination_noJAE (c_graph_t::edge_t e, 00938 c_graph_t& angelLCG, 00939 const transformationSeq_cost_t* currentTransformationSequence, 00940 refillDependenceMap_t& refillDependences) { 00941 #ifndef NDEBUG 00942 cout << "back eliminating edge " << e << "\t(without creating any JAEs)" << endl; 00943 #endif 00944 00945 unsigned int cost = 0; 00946 c_graph_t::iei_t iei, ie_end; 00947 vector<c_graph_t::edge_t> srcInEdges; 00948 00949 // save in-edges of src in a vector, as pointers become invalidated 00950 for (tie (iei, ie_end) = in_edges (source (e, angelLCG), angelLCG); iei != ie_end; ++iei) 00951 srcInEdges.push_back(*iei); 00952 00953 for (size_t i = 0; i < srcInEdges.size(); i++) 00954 cost += pairElim_noJAE (srcInEdges[i], e, angelLCG, currentTransformationSequence, refillDependences); 00955 00956 // remove src of e and incident edges if it becomes isolated and isn't a dependent 00957 if (out_degree (source (e, angelLCG), angelLCG) == 1 && vertex_type (source (e, angelLCG), angelLCG) != dependent) 00958 for (size_t i = 0; i < srcInEdges.size(); i++) 00959 remove_edge (srcInEdges[i], angelLCG); 00960 00961 remove_edge (e, angelLCG); 00962 return cost; 00963 } // end backEdgeElimination_noJAE() 00964 00965 #endif // USEXAIFBOOSTER 00966 00967 } // namespace angel 00968