angel  mercurial changeset:
include/eliminations.hpp
Go to the documentation of this file.
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 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines