angel
mercurial changeset:
|
00001 /* 00002 ############################################################# 00003 # This file is part of angel released under the BSD license # 00004 # The full COPYRIGHT notice can be found in the top # 00005 # level directory of the angel distribution # 00006 ############################################################# 00007 */ 00008 00009 #ifndef _eliminations_include_ 00010 #define _eliminations_include_ 00011 00012 #include "angel_types.hpp" 00013 #include "angel_io.hpp" 00014 00015 #ifdef USEXAIFBOOSTER 00016 #include "xaifBooster/algorithms/CrossCountryInterface/inc/AwarenessLevel.hpp" 00017 using std::list; 00018 #endif 00019 00020 namespace angel { 00021 00022 using std::vector; 00023 using std::cout; 00024 using boost::tie; 00025 00026 // ========================================================================= 00027 // eliminations in c-graph 00028 // ========================================================================= 00029 00030 // ------------------------------------------------------------------------- 00031 // elimination of a single vertex in compute graph 00032 // ------------------------------------------------------------------------- 00033 00038 int vertex_elimination (c_graph_t::vertex_t v, c_graph_t& cg); 00039 00044 inline int vertex_elimination (int j, c_graph_t& cg) { 00045 return vertex_elimination (vertex (j, cg), cg); } 00046 00047 // ------------------------------------------------------------------------- 00048 // elimination of a single edge in compute graph 00049 // ------------------------------------------------------------------------- 00050 00055 int front_edge_elimination (c_graph_t::edge_t e, 00056 c_graph_t& cg); 00057 00062 inline int front_edge_elimination (c_graph_t::vertex_t i, 00063 c_graph_t::vertex_t j, 00064 c_graph_t& cg) { 00065 bool found_ij; 00066 c_graph_t::edge_t edge_ij; 00067 tie (edge_ij, found_ij)= edge (i, j, cg); 00068 return found_ij ? front_edge_elimination (edge_ij, cg) : 0; 00069 } 00070 00076 inline int front_edge_elimination (int i, int j, c_graph_t& cg) { 00077 return front_edge_elimination (vertex (i, cg), vertex (j, cg), cg); } 00078 00079 00084 int back_edge_elimination (c_graph_t::edge_t e, 00085 c_graph_t& cg); 00086 00090 inline int back_edge_elimination (c_graph_t::vertex_t i, 00091 c_graph_t::vertex_t j, 00092 c_graph_t& cg) { 00093 bool found_ij; 00094 c_graph_t::edge_t edge_ij; 00095 tie (edge_ij, found_ij)= edge (i, j, cg); 00096 return found_ij ? back_edge_elimination (edge_ij, cg) : 0; 00097 } 00098 00103 inline int back_edge_elimination (int i, int j, c_graph_t& cg) { 00104 return back_edge_elimination (vertex (i, cg), vertex (j, cg), cg); } 00105 00109 inline int edge_elimination (c_graph_t::edge_t e, bool front, 00110 c_graph_t& cg) { 00111 return front ? front_edge_elimination (e, cg) 00112 : back_edge_elimination (e, cg); 00113 } 00114 00118 inline int edge_elimination (edge_bool_t e, c_graph_t& cg) { 00119 return e.second ? front_edge_elimination (e.first, cg) 00120 : back_edge_elimination (e.first, cg); 00121 } 00122 00127 inline int edge_elimination (c_graph_t::vertex_t i, 00128 c_graph_t::vertex_t j, 00129 bool front, c_graph_t& cg) { 00130 return front ? front_edge_elimination (i, j, cg) 00131 : back_edge_elimination (i, j, cg); 00132 } 00133 00138 inline int edge_elimination (int i, int j, bool front, c_graph_t& cg) { 00139 return front ? front_edge_elimination (i, j, cg) 00140 : back_edge_elimination (i, j, cg); 00141 } 00142 00144 inline int edge_elimination (edge_ij_elim_t ee, c_graph_t& cg) { 00145 return edge_elimination (ee.i, ee.j, ee.front, cg); } 00146 00147 // ------------------------------------------------------------------------- 00148 // elimination sequences of vertices in compute graph 00149 // ------------------------------------------------------------------------- 00150 00155 int vertex_elimination (const vector<int>& seq, c_graph_t& cg); 00156 00157 00161 inline int edge_elimination (const edge_elim_seq_t& seq, c_graph_t& cg) { 00162 int costs= 0; 00163 for (size_t i= 0; i < seq.size(); i++) 00164 costs+= edge_elimination (seq[i].edge, seq[i].front, cg); 00165 return costs; 00166 } 00167 00171 inline int edge_elimination (const edge_pair_elim_seq_t& seq, c_graph_t& cg) { 00172 int costs= 0; 00173 for (size_t k= 0; k < seq.size(); k++) 00174 costs+= edge_elimination (seq[k].i, seq[k].j, seq[k].front, cg); 00175 return costs; 00176 } 00177 00181 inline int edge_elimination (const edge_ij_elim_seq_t& seq, c_graph_t& cg) { 00182 int costs= 0; 00183 for (size_t k= 0; k < seq.size(); k++) 00184 costs+= edge_elimination (seq[k].i, seq[k].j, seq[k].front, cg); 00185 return costs; 00186 } 00187 00188 // ========================================================================= 00189 // eliminations in line graph 00190 // ========================================================================= 00191 00192 // ------------------------------------------------------------------------- 00193 // elimination of a single vertex in line graph 00194 // ------------------------------------------------------------------------- 00195 00201 int vertex_elimination (int j, line_graph_t& lg); 00202 00203 // ------------------------------------------------------------------------- 00204 // elimination of a single edge in line graph 00205 // ------------------------------------------------------------------------- 00206 00212 int front_edge_elimination (int i, int j, line_graph_t& lg); 00213 00219 int front_edge_elimination (line_graph_t::edge_t vij, line_graph_t& lg); 00220 00226 int back_edge_elimination (int i, int j, line_graph_t& lg); 00227 00233 int back_edge_elimination (line_graph_t::edge_t vij, line_graph_t& lg); 00234 00237 inline int edge_elimination (int i, int j, bool front, line_graph_t& lg) { 00238 return front ? front_edge_elimination (i, j, lg) 00239 : back_edge_elimination (i, j, lg); 00240 } 00241 00243 inline int edge_elimination (line_graph_t::edge_t vij, 00244 bool front, line_graph_t& lg) { 00245 return front ? front_edge_elimination (vij, lg) 00246 : back_edge_elimination (vij, lg); 00247 } 00248 00249 // ------------------------------------------------------------------------- 00250 // elimination sequences of edges in line graph 00251 // ------------------------------------------------------------------------- 00252 00253 // additional data structures 00254 // -------------------------- 00255 00258 struct edge_vertex_elim_t { 00259 line_graph_t::edge_t edge; 00260 bool front; 00261 }; 00262 00264 typedef vector<edge_vertex_elim_t> edge_vertex_elim_seq_t; 00265 00267 inline int edge_elimination (const edge_vertex_elim_seq_t& seq, line_graph_t& lg) { 00268 int costs= 0; 00269 for (size_t k= 0; k < seq.size(); k++) 00270 costs+= edge_elimination (seq[k].edge, seq[k].front, lg); 00271 return costs; 00272 } 00273 00274 // ------------------------------------------------------------------------- 00275 // elimination of a single face in line graph 00276 // ------------------------------------------------------------------------- 00277 00291 int face_elimination (line_graph_t::face_t f, int kr, line_graph_t& lg, accu_graph_t& ac); 00292 00305 inline int face_elimination (line_graph_t::face_t f, int kr, line_graph_t& lg) { 00306 accu_graph_t dummy (*lg.cgp, lg); 00307 return face_elimination (f, kr, lg, dummy); } 00308 00312 inline int face_elimination (line_graph_t::face_t f, line_graph_t& lg) { 00313 return face_elimination (f, -1, lg); } 00314 00321 inline int face_elimination (int i, int j, line_graph_t& lg) { 00322 line_graph_t::face_t f; bool found; 00323 tie (f, found)= edge (i, j, lg); 00324 return found ? face_elimination (f, lg) : -1; 00325 } 00326 00340 inline int face_elimination (int i, int j, int kr, line_graph_t& lg) { 00341 line_graph_t::face_t f; bool found; 00342 tie (f, found)= edge (i, j, lg); 00343 return found ? face_elimination (f, kr, lg) : -1; 00344 } 00345 00346 inline int face_elimination (int i, int j, int kr, line_graph_t& lg, accu_graph_t& ac) { 00347 line_graph_t::face_t f; bool found; 00348 tie (f, found)= edge (i, j, lg); 00349 return found ? face_elimination (f, kr, lg, ac) : -1; 00350 } 00351 00361 inline int face_elimination (triplet_t& t, line_graph_t& lg) { 00362 int k= face_elimination (t.i, t.j, t.k, lg); 00363 if (k != -1) t.k= k; return k != -1; 00364 } 00365 00378 inline int face_elimination (triplet_t& t, line_graph_t& lg, accu_graph_t& ac) { 00379 int k= face_elimination (t.i, t.j, t.k, lg, ac); 00380 if (k != -1) t.k= k; return k != -1; 00381 } 00382 00393 inline int was_non_trivial_elimination (int i, int j, int k, const line_graph_t& lg) { 00394 line_graph_t::const_ed_t el= get(boost::vertex_degree, lg); // edge label 00395 return ((k != -1 && el[i] != 1 && el[j] != 1) || k < lg.v()-1); // absorption -> a+= b in accumulation 00396 } 00397 00407 inline int was_non_trivial_elimination (line_graph_t::face_t f, int k, const line_graph_t& lg) { 00408 line_graph_t::edge_t i= source (f, lg), j= target (f, lg); 00409 return was_non_trivial_elimination (i, j, k, lg); 00410 } 00411 00412 // ------------------------------------------------------------------------- 00413 // elimination sequences of faces 00414 // ------------------------------------------------------------------------- 00415 00416 00417 // ========================================================================= 00418 // overloaded elimination functions for templates 00419 // ========================================================================= 00420 00422 inline int eliminate (c_graph_t::vertex_t v, c_graph_t& cg) { 00423 return vertex_elimination (v, cg); } 00424 00426 inline int eliminate (int j, c_graph_t& cg) { 00427 return vertex_elimination (j, cg); } 00428 00430 inline int eliminate (int j, line_graph_t& lg) { 00431 return vertex_elimination (j, lg); } 00432 00434 inline int eliminate (edge_bool_t e, c_graph_t& cg) { 00435 return edge_elimination (e, cg); 00436 } 00437 00439 inline int eliminate (edge_ij_elim_t ee, c_graph_t& cg) { 00440 return edge_elimination (ee, cg); 00441 } 00442 00448 inline int eliminate (line_graph_t::face_t f, line_graph_t& lg) { 00449 int k= face_elimination (f, -1, lg); 00450 return was_non_trivial_elimination (f, k, lg); 00451 } 00452 00460 inline int eliminate (triplet_t& t, line_graph_t& lg) { 00461 return face_elimination (t, lg); 00462 } 00463 00464 // ========================================================================= 00465 // which vertices, edges or faces can be eliminated 00466 // ========================================================================= 00467 00469 int eliminatable_vertices (const c_graph_t& cg, 00470 vector<c_graph_t::vertex_t>& vv); 00471 00476 int semi_eliminatable_vertices (const c_graph_t& cg, vector<c_graph_t::vertex_t>& vv); 00477 00482 int eliminatable_edges (const c_graph_t& cg, 00483 vector<c_graph_t::edge_t>& ev); 00484 00486 int front_eliminatable_edges (const c_graph_t& cg, 00487 vector<c_graph_t::edge_t>& ev); 00488 00490 int back_eliminatable_edges (const c_graph_t& cg, 00491 vector<c_graph_t::edge_t>& ev); 00492 00499 int eliminatable_edges (const c_graph_t& cg, 00500 vector<edge_bool_t>& ev); 00501 00508 int eliminatable_edges (const c_graph_t& cg, 00509 vector<edge_ij_elim_t>& ev); 00510 00512 unsigned int eliminatable_edges(const c_graph_t& cg, 00513 vector<EdgeElim>& ev); 00514 00516 int eliminatable_faces (const line_graph_t& lg, 00517 vector<line_graph_t::face_t>& fv); 00518 00525 inline int eliminatable_triplets (const line_graph_t& lg, vector<triplet_t>& tv) { 00526 vector<line_graph_t::face_t> fv; 00527 eliminatable_faces (lg, fv); 00528 tv.resize (0); 00529 for (size_t c= 0; c < fv.size(); c++) { 00530 int s= source (fv[c], lg), t= target (fv[c], lg); 00531 triplet_t tr (s, t, -1); tv.push_back (tr); } 00532 return tv.size(); 00533 } 00534 00535 // ========================================================================= 00536 // which vertices, edges or faces can be eliminated (overloaded versions) 00537 // ========================================================================= 00538 00540 inline int eliminatable_objects (const c_graph_t& cg, 00541 vector<c_graph_t::vertex_t>& vv) { 00542 return eliminatable_vertices (cg, vv); 00543 } 00544 00546 inline int eliminatable_objects (const c_graph_t& cg, 00547 vector<c_graph_t::edge_t>& ev) { 00548 return eliminatable_edges (cg, ev); 00549 } 00550 00552 inline int eliminatable_objects (const c_graph_t& cg, 00553 vector<edge_bool_t>& ev) { 00554 return eliminatable_edges (cg, ev); 00555 } 00556 00558 inline int eliminatable_objects (const c_graph_t& cg, 00559 vector<edge_ij_elim_t>& ev) { 00560 return eliminatable_edges (cg, ev); 00561 } 00562 00564 inline int eliminatable_objects (const line_graph_t& lg, 00565 vector<line_graph_t::face_t>& fv) { 00566 return eliminatable_faces (lg, fv); 00567 } 00568 00570 inline int eliminatable_objects (const line_graph_t& lg, 00571 vector<triplet_t>& tv) { 00572 return eliminatable_triplets (lg, tv); 00573 } 00574 00575 00576 00585 template <typename Ad_graph_t, 00586 typename El_spec_t> 00587 class elimination_history_t { 00588 private: 00589 00590 public: 00591 const Ad_graph_t og; 00592 vector<El_spec_t> seq; 00593 Ad_graph_t cg; 00594 int ccosts; 00595 00596 typedef Ad_graph_t ad_graph_t; 00597 typedef El_spec_t el_spec_t; 00598 00603 elimination_history_t () : og () {} 00604 00608 elimination_history_t (const Ad_graph_t& _cg) : 00609 og (_cg), cg (_cg), ccosts (0) { 00610 THROW_EXCEPT_MACRO (!check (), consistency_exception, "Inconsistent input graph");} 00611 00619 elimination_history_t (const Ad_graph_t& _og, const vector<El_spec_t>& _seq, 00620 const Ad_graph_t& _cg, int _ccosts= 0) : 00621 og (_og), seq (_seq), cg (_cg), ccosts (_ccosts) { 00622 THROW_EXCEPT_MACRO (!check (), consistency_exception, "Inconsistent input graphs");} 00623 00630 elimination_history_t (const Ad_graph_t& _og, const vector<El_spec_t>& _seq) : 00631 og (_og), seq (_seq) { 00632 THROW_EXCEPT_MACRO (!og.check (), consistency_exception, "Inconsistent input graph"); 00633 bool seq_ok= rebuild_graph (); 00634 THROW_EXCEPT_MACRO (!seq_ok, consistency_exception, "Inconsistent elimination sequence"); 00635 } 00636 00638 elimination_history_t (const elimination_history_t& eh) : 00639 og (eh.og), seq (eh.seq), cg (eh.cg), ccosts (eh.ccosts) { 00640 THROW_EXCEPT_MACRO (!og.check (), consistency_exception, "Inconsistent start graph"); 00641 THROW_EXCEPT_MACRO (!cg.check (), consistency_exception, "Inconsistent current graph"); 00642 THROW_EXCEPT_MACRO (!check_sequence(), consistency_exception, "Inconsistent elimination sequence"); 00643 } 00644 00646 elimination_history_t& operator= (const elimination_history_t& eh) { 00647 (Ad_graph_t&) og= eh.og; seq= eh.seq; cg= eh.cg; ccosts= eh.ccosts; 00648 THROW_DEBUG_EXCEPT_MACRO (!check (), consistency_exception, "Inconsistent graphs after assignment"); 00649 return *this; } 00650 00652 void swap (elimination_history_t& eh) { 00653 ((Ad_graph_t&) og).swap ((Ad_graph_t&) eh.og); 00654 seq.swap (eh.seq); cg.swap (eh.cg); std::swap (ccosts, eh.ccosts); 00655 THROW_DEBUG_EXCEPT_MACRO (!check (), consistency_exception, "Inconsistent graphs after swapping");} 00656 00668 int elimination (El_spec_t el) { 00669 int costs= eliminate (el, cg); 00670 if (costs > 0) {seq.push_back (el); ccosts+= costs; } 00671 return costs; } 00672 00674 bool check_sequence () const { 00675 Ad_graph_t og_copy (og); 00676 int costs= 0; 00677 for (size_t c= 0; c < seq.size(); c++) { 00678 El_spec_t el= seq[c]; // copied from seq because some eliminations change el 00679 int el_costs= eliminate (el, og_copy); 00680 if (el_costs == 0) { 00681 cout << "check_sequence failed"; 00682 write_vector (" with elimination sequence", seq); 00683 cout << " at " << c << "th entry, which is " << seq[c] << std::endl; 00684 write_graph ("at this moment the graph is", og_copy); 00685 cout << "it is " << (og_copy.check() ? "" : "not ") << "consistent\n"; 00686 write_vector ("complete elimination sequence is", seq); 00687 return false; } 00688 else costs+= el_costs; } 00689 if (cg != og_copy) { 00690 cout << "check_sequence failed because of different resulting graphs.\n"; 00691 write_graph ("current graph is", cg); 00692 write_graph ("seq applied to og results in", og_copy); 00693 write_graph ("original graph was", og); 00694 write_vector ("elimination sequence is", seq); 00695 return false; } 00696 if (ccosts != costs) { 00697 cout << "check_sequence failed because of different elimination costs.\n"; 00698 cout << "current costs are " << ccosts << std::endl; 00699 cout << "seq applied to og requires " << costs << std::endl; 00700 write_graph ("original graph was", og); 00701 write_vector ("elimination sequence is", seq); 00702 write_graph ("current graph is", cg); 00703 return false; } 00704 return true; 00705 } 00706 00708 bool check () const { 00709 if (!og.check ()) return false; // original graph inconsistent 00710 if (!cg.check ()) return false; // current graph inconsistent 00711 return check_sequence (); } 00712 00714 bool rebuild_graph () { 00715 Ad_graph_t og_copy (og); 00716 int costs= 0; 00717 for (size_t c= 0; c < seq.size(); c++) { 00718 int el_costs= eliminate (seq[c], og_copy); 00719 if (el_costs == 0) return false; else costs+= el_costs; } 00720 cg= og_copy; ccosts= costs; return true; } 00721 00727 template <typename Heuristic_t> 00728 void complete_sequence (Heuristic_t h) { 00729 vector<El_spec_t> v1, v2; 00730 for (eliminatable_objects (cg, v1); v1.size() > 0; eliminatable_objects (cg, v1)) { 00731 v2.resize (0); h (v1, cg, v2); elimination (v2[0]); }} 00732 }; 00733 00737 typedef elimination_history_t<c_graph_t, c_graph_t::vertex_t> vertex_elimination_history_t; 00741 typedef elimination_history_t<c_graph_t, edge_ij_elim_t> edge_elimination_history_t; 00745 typedef elimination_history_t<line_graph_t, triplet_t> face_elimination_history_t; 00746 00748 bool convert_elimination_sequence (const vector<c_graph_t::vertex_t>& vv, 00749 const c_graph_t& cg, 00750 vector<edge_ij_elim_t>& ev); 00751 00753 bool convert_elimination_sequence (const vector<edge_ij_elim_t>& ev, 00754 const line_graph_t& lg, 00755 vector<triplet_t>& tv); 00756 00757 #ifdef USEXAIFBOOSTER 00758 00759 EdgeRefType_E getRefType (const c_graph_t::edge_t e, 00760 const c_graph_t& angelLCG, 00761 const list<EdgeRef_t>& edge_ref_list); 00762 00763 const xaifBoosterCrossCountryInterface::LinearizedComputationalGraphEdge* getLCG_p (const c_graph_t::edge_t e, 00764 const c_graph_t& angelLCG, 00765 const list<EdgeRef_t>& edge_ref_list); 00766 00767 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex* getJAE_p (const c_graph_t::edge_t e, 00768 const c_graph_t& angelLCG, 00769 const list<EdgeRef_t>& edge_ref_list); 00770 00771 void setJaevRef (const c_graph_t::edge_t e, 00772 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex& jaev, 00773 const c_graph_t& angelLCG, 00774 const list<EdgeRef_t>& edge_ref_list); 00775 00776 void removeRef (const c_graph_t::edge_t e, 00777 const c_graph_t& angelLCG, 00778 list<EdgeRef_t>& edge_ref_list); 00779 00795 unsigned int multiply_edge_pair_directly (const c_graph_t::edge_t e1, 00796 const c_graph_t::edge_t e2, 00797 c_graph_t& angelLCG, 00798 list<EdgeRef_t>& edge_ref_list, 00799 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionList& jae_list); 00800 00816 unsigned int front_eliminate_edge_directly (c_graph_t::edge_t e, 00817 c_graph_t& angelLCG, 00818 list<EdgeRef_t>& edge_ref_list, 00819 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionList& jae_list); 00820 00836 unsigned int back_eliminate_edge_directly (c_graph_t::edge_t e, 00837 c_graph_t& angelLCG, 00838 list<EdgeRef_t>& edge_ref_list, 00839 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionList& jae_list); 00840 00841 unsigned int pair_elim (c_graph_t::edge_t e1, 00842 c_graph_t::edge_t e2, 00843 c_graph_t& angelLCG, 00844 const elimSeq_cost_t& currentElimSeq, 00845 refillDependenceMap_t& refillDependences); 00846 00847 unsigned int front_elim (c_graph_t::edge_t e, 00848 c_graph_t& angelLCG, 00849 const elimSeq_cost_t& currentElimSeq, 00850 refillDependenceMap_t& refillDependences); 00851 00852 unsigned int back_elim (c_graph_t::edge_t e, 00853 c_graph_t& angelLCG, 00854 const elimSeq_cost_t& currentElimSeq, 00855 refillDependenceMap_t& refillDependences); 00856 00857 unsigned int pairElim_noJAE (c_graph_t::edge_t e1, 00858 c_graph_t::edge_t e2, 00859 c_graph_t& angelLCG, 00860 const transformationSeq_cost_t* currentTransformationSequence, 00861 refillDependenceMap_t& refillDependences); 00862 00863 unsigned int frontEdgeElimination_noJAE (c_graph_t::edge_t e, 00864 c_graph_t& angelLCG, 00865 const transformationSeq_cost_t* currentTransformationSequence, 00866 refillDependenceMap_t& refillDependences); 00867 00868 unsigned int backEdgeElimination_noJAE (c_graph_t::edge_t e, 00869 c_graph_t& angelLCG, 00870 const transformationSeq_cost_t* currentTransformationSequence, 00871 refillDependenceMap_t& refillDependences); 00872 00873 #endif // USEXAIFBOOSTER 00874 00875 } // namespace angel 00876 00877 #endif // _eliminations_include_ 00878