angel  mercurial changeset:
include/heuristics.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         _heuristics_include_
00010 #define         _heuristics_include_
00011 
00012 #include <vector>
00013 
00014 #include "angel_types.hpp"
00015 #include "angel_io.hpp"
00016 #include "eliminations.hpp"
00017 
00018 #ifdef USE_MPI
00019 #include "gmpi.hpp"
00020 #include "angel_comm.hpp"
00021 #endif // USE_MPI
00022 
00023 #ifdef USEXAIFBOOSTER
00024 #include "reroutings.hpp"
00025 #endif // USEXAIFBOOSTER
00026 
00027 namespace angel {
00028 
00029   using std::vector;
00030   
00031 // =====================================================
00032 // Basic class for heuristics
00033 // =====================================================
00034 
00035 template <class Objective_t= int>
00036 class base_heuristic_t {
00037 protected:
00038   Objective_t   my_objective;
00039   bool          is_set;           // whether my_object is set
00040   bool          my_maximize;      // if objective value is maximized
00041 public:
00042   typedef Objective_t    objective_t;
00043   base_heuristic_t (bool _m) : is_set (false), my_maximize (_m) {}
00044   Objective_t objective() const {
00045     THROW_DEBUG_EXCEPT_MACRO (!is_set, consistency_exception, "objective not set"); return my_objective;}
00046   void set_objective (Objective_t o) {
00047     is_set= true; my_objective= o; }
00048   void set_empty_objective () {
00049     is_set= true; 
00050     my_objective= my_maximize ? std::numeric_limits<Objective_t>::min() 
00051                               : std::numeric_limits<Objective_t>::max(); }
00052   bool to_maximize() const {return my_maximize;}
00053 };
00054 
00055 template <class Object_t, class Ad_graph_t, class Op_t, class Objective_t>
00056 int standard_heuristic_op (const vector<Object_t>& v1, const Ad_graph_t& adg,
00057                            vector<Object_t>& v2, Op_t op, base_heuristic_t<Objective_t>& h);
00058 
00059 // =====================================================
00060 // for vertex elimination
00061 // =====================================================
00062 
00072 class forward_mode_vertex_t : public base_heuristic_t<int> {
00073 public:
00074   forward_mode_vertex_t () : base_heuristic_t<int> (false) {}
00075   int operator() (const vector<c_graph_t::vertex_t>& vv1,
00076                   const c_graph_t& cg, 
00077                   vector<c_graph_t::vertex_t>& vv2);
00078 };
00079 
00086 extern forward_mode_vertex_t forward_mode_vertex;
00087 
00088 // -------------------------------------------------------------------------
00089 // reverse mode
00090 // -------------------------------------------------------------------------
00091 
00098 class reverse_mode_vertex_t : public base_heuristic_t<int> {
00099 public:
00100   reverse_mode_vertex_t () : base_heuristic_t<int> (true) {}
00101   int operator() (const vector<c_graph_t::vertex_t>& vv1,
00102                   const c_graph_t& cg, 
00103                   vector<c_graph_t::vertex_t>& vv2);
00104 };
00105 
00112 extern reverse_mode_vertex_t reverse_mode_vertex;
00113 
00114 // -------------------------------------------------------------------------
00115 // Lowest Markowitz
00116 // -------------------------------------------------------------------------
00117 
00124 class lowest_markowitz_vertex_t : public base_heuristic_t<int> {
00125 public:
00126   lowest_markowitz_vertex_t () : base_heuristic_t<int> (false) {}
00127   int operator() (const vector<c_graph_t::vertex_t>& vv1,
00128                   const c_graph_t& cg, 
00129                   vector<c_graph_t::vertex_t>& vv2);
00130 };
00131 
00138 extern lowest_markowitz_vertex_t lowest_markowitz_vertex;
00139   
00140 // -------------------------------------------------------------------------
00141 // Lowest relative Markowitz
00142 // -------------------------------------------------------------------------
00143 
00150 class lowest_relative_markowitz_vertex_t : public base_heuristic_t<int> {
00151 public:
00152   lowest_relative_markowitz_vertex_t () : base_heuristic_t<int> (false) {}
00153   int operator() (const vector<c_graph_t::vertex_t>& vv1,
00154                   const c_graph_t& cg, 
00155                   vector<c_graph_t::vertex_t>& vv2);
00156 };
00157 
00164 extern lowest_relative_markowitz_vertex_t lowest_relative_markowitz_vertex;
00165 
00166 // -------------------------------------------------------------------------
00167 // Lowest fill-in
00168 // -------------------------------------------------------------------------
00169 
00176 class lowest_fill_in_vertex_t : public base_heuristic_t<int> {
00177 public:
00178   lowest_fill_in_vertex_t () : base_heuristic_t<int> (false) {}
00179   int operator() (const vector<c_graph_t::vertex_t>& vv1,
00180                   const c_graph_t& cg, 
00181                   vector<c_graph_t::vertex_t>& vv2);
00182 };
00183 
00190 extern lowest_fill_in_vertex_t lowest_fill_in_vertex;
00191 
00192 // -------------------------------------------------------------------------
00193 // LMMD
00194 // -------------------------------------------------------------------------
00195 
00202 class lmmd_vertex_t : public base_heuristic_t<int> {
00203   double weight;
00204 public:
00206   lmmd_vertex_t (double w) : base_heuristic_t<int> (false), weight (w) {}
00213   int operator() (const vector<c_graph_t::vertex_t>& vv1,
00214                   const c_graph_t& cg, 
00215                   vector<c_graph_t::vertex_t>& vv2);
00216 };
00217 
00218 
00224 extern lmmd_vertex_t lmmd_vertex;
00225 
00226 // -------------------------------------------------------------------------
00227 // MOMR
00228 // -------------------------------------------------------------------------
00229 
00234 class momr_vertex_t : public base_heuristic_t<int> {
00235 public:
00236   momr_vertex_t () : base_heuristic_t<int> (true) {}
00243   int operator() (const vector<c_graph_t::vertex_t>& vv1,
00244                   const c_graph_t& cg, 
00245                   vector<c_graph_t::vertex_t>& vv2);
00246 };
00247 
00249 extern momr_vertex_t momr_vertex;
00250 
00251 // -------------------------------------------------------------------------
00252 // Maximal overall path length reduction
00253 // -------------------------------------------------------------------------
00254 
00261 class moplr_vertex_t : public base_heuristic_t<int> {
00262 public:
00263   moplr_vertex_t () : base_heuristic_t<int> (true) {}
00264   int operator() (const vector<c_graph_t::vertex_t>& vv1,
00265                   const c_graph_t& cg, 
00266                   vector<c_graph_t::vertex_t>& vv2);
00267 };
00268 
00275 extern moplr_vertex_t moplr_vertex;
00276 
00277 // =====================================================
00278 // for edge elimination (in c-graph)
00279 // =====================================================
00280 
00294 int forward_mode_edge_f (const vector<c_graph_t::edge_t>& ev1,
00295                          bool front,
00296                          const c_graph_t& cg,
00297                          vector<c_graph_t::edge_t>& ev2);
00298 
00309 inline int forward_mode_edge_front (const vector<c_graph_t::edge_t>& ev1,
00310                                     const c_graph_t& cg,
00311                                     vector<c_graph_t::edge_t>& ev2) {
00312   return forward_mode_edge_f (ev1, true, cg, ev2);
00313 }
00314 
00324 inline int forward_mode_edge_back (const vector<c_graph_t::edge_t>& ev1,
00325                                    const c_graph_t& cg,
00326                                    vector<c_graph_t::edge_t>& ev2) {
00327   return forward_mode_edge_f (ev1, false, cg, ev2);
00328 }
00329 
00338 class forward_mode_edge_t : public base_heuristic_t<double> {
00339 public:
00340   forward_mode_edge_t () : base_heuristic_t<double> (false) {}
00341   int operator() (const vector<edge_bool_t>& ev1,
00342                   const c_graph_t& cg,
00343                   vector<edge_bool_t>& ev2);
00344 };
00345 
00357 extern forward_mode_edge_t forward_mode_edge;
00358 
00359 // -------------------------------------------------------------------------
00360 // reverse mode
00361 // -------------------------------------------------------------------------
00362 
00376 int reverse_mode_edge_f (const vector<c_graph_t::edge_t>& ev1,
00377                          bool front,
00378                          const c_graph_t& cg,
00379                          vector<c_graph_t::edge_t>& ev2);
00380 
00389 inline int reverse_mode_edge_front (const vector<c_graph_t::edge_t>& ev1,
00390                                     const c_graph_t& cg,
00391                                     vector<c_graph_t::edge_t>& ev2) {
00392   return reverse_mode_edge_f (ev1, true, cg, ev2);
00393 }
00394 
00403 inline int reverse_mode_edge_back (const vector<c_graph_t::edge_t>& ev1,
00404                                    const c_graph_t& cg,
00405                                    vector<c_graph_t::edge_t>& ev2) {
00406   return reverse_mode_edge_f (ev1, false, cg, ev2);
00407 }
00408 
00417 class reverse_mode_edge_t : public base_heuristic_t<double> {
00418 public:
00419   reverse_mode_edge_t () : base_heuristic_t<double> (false) {}
00420   int operator() (const vector<edge_bool_t>& ev1,
00421                   const c_graph_t& cg,
00422                   vector<edge_bool_t>& ev2);
00423 };
00424 
00436 extern reverse_mode_edge_t reverse_mode_edge;
00437 
00438 // -------------------------------------------------------------------------
00439 // Lowest Markowitz
00440 // -------------------------------------------------------------------------
00441 
00456 int lowest_markowitz_edge_f (const vector<c_graph_t::edge_t>& ev1,
00457                              bool front,
00458                              const c_graph_t& cg,
00459                              vector<c_graph_t::edge_t>& ev2);
00460 
00461 
00470 inline int lowest_markowitz_edge_front (const vector<c_graph_t::edge_t>& ev1,
00471                                         const c_graph_t& cg,
00472                                         vector<c_graph_t::edge_t>& ev2) {
00473   return lowest_markowitz_edge_f (ev1, true, cg, ev2);
00474 }
00475 
00476 
00485 inline int lowest_markowitz_edge_back (const vector<c_graph_t::edge_t>& ev1,
00486                                        const c_graph_t& cg,
00487                                        vector<c_graph_t::edge_t>& ev2) {
00488   return lowest_markowitz_edge_f (ev1, false, cg, ev2);
00489 }
00490 
00499 class lowest_markowitz_edge_t : public base_heuristic_t<int> {
00500 public:
00501   lowest_markowitz_edge_t () : base_heuristic_t<int> (false) {}
00502   int operator() (const vector<edge_bool_t>& ev1,
00503                   const c_graph_t& cg,
00504                   vector<edge_bool_t>& ev2);
00505 };
00506 
00513 extern lowest_markowitz_edge_t lowest_markowitz_edge;
00514 
00515 // -------------------------------------------------------------------------
00516 // Lowest relative Markowitz
00517 // -------------------------------------------------------------------------
00518 
00533 int lowest_relative_markowitz_edge_f (const vector<c_graph_t::edge_t>& ev1,
00534                                       bool front,
00535                                       const c_graph_t& cg,
00536                                       vector<c_graph_t::edge_t>& ev2);
00537 
00546 inline int lowest_relative_markowitz_edge_front (const vector<c_graph_t::edge_t>& ev1,
00547                                                  const c_graph_t& cg,
00548                                                  vector<c_graph_t::edge_t>& ev2) {
00549   return lowest_relative_markowitz_edge_f (ev1, true, cg, ev2);
00550 }
00551 
00560 inline int lowest_relative_markowitz_edge_back (const vector<c_graph_t::edge_t>& ev1,
00561                                                 const c_graph_t& cg,
00562                                                 vector<c_graph_t::edge_t>& ev2) {
00563   return lowest_relative_markowitz_edge_f (ev1, false, cg, ev2);
00564 }
00565 
00566 
00575 class lowest_relative_markowitz_edge_t : public base_heuristic_t<int> {
00576 public:
00577   lowest_relative_markowitz_edge_t () : base_heuristic_t<int> (false) {}
00578   int operator() (const vector<edge_bool_t>& ev1,
00579                   const c_graph_t& cg,
00580                   vector<edge_bool_t>& ev2);
00581 };
00582 
00589 extern lowest_relative_markowitz_edge_t lowest_relative_markowitz_edge;
00590 
00591 // -------------------------------------------------------------------------
00592 // Lowest fill-in
00593 // -------------------------------------------------------------------------
00594 
00606 int lowest_fill_in_edge_f (const vector<c_graph_t::edge_t>& ev1,
00607                            bool front,
00608                            const c_graph_t& cg,
00609                            vector<c_graph_t::edge_t>& ev2);
00610 
00619 inline int lowest_fill_in_edge_front (const vector<c_graph_t::edge_t>& ev1,
00620                                       const c_graph_t& cg,
00621                                       vector<c_graph_t::edge_t>& ev2) {
00622   return lowest_fill_in_edge_f (ev1, true, cg, ev2);
00623 }
00624 
00633 inline int lowest_fill_in_edge_back (const vector<c_graph_t::edge_t>& ev1,
00634                                      const c_graph_t& cg,
00635                                      vector<c_graph_t::edge_t>& ev2) {
00636   return lowest_fill_in_edge_f (ev1, false, cg, ev2);
00637 }
00638 
00639 // -------------------------------------------------------------------------
00640 // LMMD
00641 // -------------------------------------------------------------------------
00642 
00643 // here the class is the basic part
00651 class lmmd_edge_t : public base_heuristic_t<int> {
00652   double weight;
00653 public:
00655   lmmd_edge_t (double w) : base_heuristic_t<int> (false), weight (w) {}
00662   int operator() (const vector<edge_bool_t>& ev1,
00663                   const c_graph_t& cg,
00664                   vector<edge_bool_t>& ev2);
00665 };
00666 
00672 extern lmmd_edge_t lmmd_edge;
00673 
00674 // -------------------------------------------------------------------------
00675 // MOMR
00676 // -------------------------------------------------------------------------
00677 
00693 int momr_edge_f (const vector<c_graph_t::edge_t>& ev1,
00694                  bool front,
00695                  const c_graph_t& cg,
00696                  vector<c_graph_t::edge_t>& ev2);
00697 
00706 inline int momr_edge_front (const vector<c_graph_t::edge_t>& ev1,
00707                             const c_graph_t& cg,
00708                             vector<c_graph_t::edge_t>& ev2) {
00709   return momr_edge_f (ev1, true, cg, ev2);
00710 }
00711 
00720 inline int momr_edge_back (const vector<c_graph_t::edge_t>& ev1,
00721                            const c_graph_t& cg,
00722                            vector<c_graph_t::edge_t>& ev2) {
00723   return momr_edge_f (ev1, false, cg, ev2);
00724 }
00725   
00734 class momr_edge_t : public base_heuristic_t<int> {
00735 public:
00736   momr_edge_t () : base_heuristic_t<int> (true) {}
00737   int operator() (const vector<edge_bool_t>& ev1, const c_graph_t& cg,
00738                   vector<edge_bool_t>& ev2);
00739 };
00740 
00747 extern momr_edge_t momr_edge;
00748 
00749 // -------------------------------------------------------------------------
00750 // Minimal distance 
00751 // -------------------------------------------------------------------------
00752 
00757 class minimal_distance_edge_t : public base_heuristic_t<int> {
00758 public:
00759   minimal_distance_edge_t () : base_heuristic_t<int> (false) {}
00760   int operator() (const vector<edge_bool_t>& ev1, const c_graph_t& cg,
00761                   vector<edge_bool_t>& ev2);
00762 };
00763 
00764 // -------------------------------------------------------------------------
00765 // Maximal overall path length reduction
00766 // -------------------------------------------------------------------------
00767 
00775 int moplr_edge (const vector<c_graph_t::edge_t>& ev1,
00776                 bool front,
00777                 const c_graph_t& cg,
00778                 vector<c_graph_t::edge_t>& ev2);
00779 
00780 // =====================================================
00781 // for edge elimination (in line graph)
00782 // =====================================================
00783 
00784 
00785 // =====================================================
00786 // for face elimination
00787 // =====================================================
00788 
00789 
00796 class forward_mode_face_t : public base_heuristic_t<double> {
00797 public:
00798   forward_mode_face_t () : base_heuristic_t<double> (false) {}
00799   int operator() (const vector<line_graph_t::face_t>& fv1,
00800                   const line_graph_t& lg,
00801                   vector<line_graph_t::face_t>& fv2);
00802 };
00803   
00817 extern forward_mode_face_t forward_mode_face;
00818 
00819 // -------------------------------------------------------------------------
00820 // reverse mode
00821 // -------------------------------------------------------------------------
00822 
00829 class reverse_mode_face_t : public base_heuristic_t<double> {
00830 public:
00831   reverse_mode_face_t () : base_heuristic_t<double> (true) {}
00832   int operator() (const vector<line_graph_t::face_t>& fv1,
00833                   const line_graph_t& lg,
00834                   vector<line_graph_t::face_t>& fv2);
00835 };
00836 
00850 extern reverse_mode_face_t reverse_mode_face;
00851 
00858 class reverse_mode_face_whole_vertex_t : base_heuristic_t<int> {
00859 public:
00860   reverse_mode_face_whole_vertex_t () : base_heuristic_t<int> (false) {}
00861   int operator() (const vector<line_graph_t::face_t>& fv1,
00862                   const line_graph_t& lg,
00863                   vector<line_graph_t::face_t>& fv2);
00864 };
00865   
00876 extern reverse_mode_face_whole_vertex_t reverse_mode_face_whole_vertex;
00877 
00878 // -------------------------------------------------------------------------
00879 // Lowest Markowitz
00880 // -------------------------------------------------------------------------
00881 
00882 class lowest_markowitz_face_t : public base_heuristic_t<int> {
00883 public:
00884   lowest_markowitz_face_t () : base_heuristic_t<int> (false) {}
00885   int operator() (const vector<line_graph_t::face_t>& fv1,
00886                 const line_graph_t& lg,
00887                 vector<line_graph_t::face_t>& fv2);
00888 };
00889   
00907 extern lowest_markowitz_face_t lowest_markowitz_face;
00908 
00909 // -------------------------------------------------------------------------
00910 // Lowest Markowitz complete elimination
00911 // -------------------------------------------------------------------------
00912 
00913 //
00914 // searches for faces where j from the c-graph vertex 
00915 // triplet representation (i,j,k) has minimal Markowitz degree
00916 // 
00917 // from the set of faces a tie-breaker chose a subset that belong 
00918 // to one vertex, e.g. faces (*,j,*) with maximal j -> tie-breaker=reverse mode
00919 //
00920 // vertex j is stored and in following calls of the operator only
00921 // faces (*,j,*) are returned as long as there some
00922 // when no faces are found anymore then a new vertex is searched
00923 //
00924 
00925 // declaration needed in next function
00926 void markowitz_on_line_graph (const line_graph_t& lg, vector<int>& mdegree);
00927 
00939 template <class Heuristic_t>
00940 class lowest_markowitz_face_complete_t : public base_heuristic_t<int> {
00941   int lastv; 
00942   Heuristic_t tiebreaker;
00943 public:
00945   lowest_markowitz_face_complete_t (Heuristic_t t) : 
00946     base_heuristic_t<int> (false), lastv (-1), tiebreaker (t) {}
00947   
00954   int operator() (const vector<line_graph_t::face_t>& fv1,
00955                   const line_graph_t& lg,
00956                   vector<line_graph_t::face_t>& fv2);
00957 };
00958   
00959 // -------------------------------------------------------------------------
00960 // MOMR
00961 // -------------------------------------------------------------------------
00962 
00969 class momr_face_t : public base_heuristic_t<int> {
00970 public:
00971   momr_face_t () : base_heuristic_t<int> (true) {}
00972   int operator() (const vector<line_graph_t::face_t>& fv1,
00973                   const line_graph_t& lg,
00974                   vector<line_graph_t::face_t>& fv2);
00975 };
00976   
00987 extern momr_face_t momr_face;
00988 
00989 // -------------------------------------------------------------------------
00990 // Minimal distance 
00991 // -------------------------------------------------------------------------
00992 
01004 class minimal_distance_face_t : public base_heuristic_t<int> {
01005 public:
01006   minimal_distance_face_t () : base_heuristic_t<int> (false) {}
01007   int operator() (const vector<line_graph_t::face_t>& fv1, const line_graph_t& lg,
01008                   vector<line_graph_t::face_t>& fv2);
01009 };
01010 
01011 // =====================================================
01012 // edge_ij_elim_t heuristics (derived from edge elimination heuristics)
01013 // =====================================================
01014 
01016 template <class Edge_heuristic_t>
01017 class edge_ij_elim_heuristic_t {
01018   Edge_heuristic_t  h;
01019 public:
01021   edge_ij_elim_heuristic_t (Edge_heuristic_t _h) : h (_h) {}
01022   int operator() (const vector<edge_ij_elim_t>& eev1,
01023                   const c_graph_t& cg,
01024                   vector<edge_ij_elim_t>& eev2) {
01025     vector<edge_bool_t>   ebv1, ebv2;
01026     for (size_t c= 0; c < eev1.size(); c++) {
01027       c_graph_t::edge_t edge; bool found;
01028       tie (edge, found)= angel::edge (eev1[c].i, eev1[c].j, cg);
01029       if (found) ebv1.push_back (std::make_pair (edge, eev1[c].front)); }
01030     h (ebv1, cg, ebv2);
01031     eev2.resize (0);
01032     for (size_t c= 0; c < ebv2.size(); c++) {
01033       edge_ij_elim_t ee (source (ebv2[c].first, cg), 
01034                          target (ebv2[c].first, cg), ebv2[c].second);
01035       eev2.push_back (ee); }
01036     return eev2.size();
01037   }
01038 };
01039 
01040 
01041 // =====================================================
01042 // triplet_t heuristics (derived from face elimination heuristics)
01043 // =====================================================
01044 
01049 template <class Face_heuristic_t>
01050 class triplet_heuristic_t {
01051   Face_heuristic_t  h;
01052 public:
01054   triplet_heuristic_t (Face_heuristic_t _h) : h (_h) {}
01055   int operator() (const vector<triplet_t>& tv1,
01056                   const line_graph_t& lg,
01057                   vector<triplet_t>& tv2) {
01058     vector<line_graph_t::face_t> fv1, fv2;
01059     for (size_t c= 0; c < tv1.size(); c++) {
01060       line_graph_t::face_t face; bool found;
01061       tie (face, found)= angel::edge (tv1[c].i, tv1[c].j, lg);
01062       if (found) fv1.push_back (face); }
01063     h (fv1, lg, fv2);
01064     tv2.resize (0);
01065     for (size_t c= 0, tc= 0; c < fv2.size(); c++) {
01066       int s= source (fv2[c], lg), t= target (fv2[c], lg);
01067       for (; s != tv1[tc].i || t != tv1[tc].j; tc++);
01068       tv2.push_back (tv1[tc]); }
01069     return tv2.size();
01070   }
01071 };
01072 
01081 template <class Vertex_heuristic_t>
01082 class emulated_vertex_heuristic_t {
01083   Vertex_heuristic_t  h;
01084   c_graph_t::vertex_t last_vertex;
01085 public:
01087   emulated_vertex_heuristic_t (Vertex_heuristic_t _h) : h (_h), last_vertex (0) {}
01088   int operator() (const vector<edge_ij_elim_t>& tv1, const c_graph_t& cg,
01089                   vector<edge_ij_elim_t>& tv2);
01090 };
01091 
01092 
01093 // =====================================================
01094 // combining heuristics
01095 // =====================================================
01096 
01107 template <class Heuristic1_t, class Heuristic2_t>
01108 class heuristic_pair_t {
01109 private:
01110   Heuristic1_t h1;
01111   Heuristic2_t h2;
01112 public:
01114   heuristic_pair_t (Heuristic1_t _h1, Heuristic2_t _h2):
01115     h1 (_h1), h2 (_h2) {}
01117   template <class Vector_t, class Ad_graph_t>
01118   int operator() (const Vector_t& v1, const Ad_graph_t& adg, Vector_t& v2) {
01119     Vector_t vt; h1 (v1, adg, vt); return h2 (vt, adg, v2); }
01120 };
01121 
01128 template <class Heuristic1_t, class Heuristic2_t, class Heuristic3_t>
01129 class heuristic_triplet_t {
01130 private:
01131   Heuristic1_t h1;
01132   Heuristic2_t h2;
01133   Heuristic3_t h3;
01134 public:
01135   heuristic_triplet_t (Heuristic1_t _h1, Heuristic2_t _h2, Heuristic3_t _h3):
01136     h1 (_h1), h2 (_h2), h3 (_h3) {}
01137 
01138   template <class Vector_t, class Ad_graph_t>
01139   int operator() (const Vector_t& v1, const Ad_graph_t& adg, Vector_t& v2) {
01140     Vector_t vt1, vt2; h1 (v1, adg, vt1); h2 (vt1, adg, vt2); 
01141     return h3 (vt2, adg, v2);}
01142 };
01143 
01144 // =====================================================
01145 // apply heuristic to some graph
01146 // =====================================================
01147 
01162 template <class Object_t, class Ad_graph_t, class Heuristic_t>
01163 inline int use_heuristic (const Ad_graph_t& adg, vector<Object_t>& el_seq,
01164                           Heuristic_t h) {
01165   Ad_graph_t adg_copy (adg);
01166   vector<Object_t> v1;
01167   eliminatable_objects (adg_copy, v1);
01168   int costs= 0;
01169   el_seq.resize (0); // clean elimination sequence
01170 
01171   while (!v1.empty()) {
01172     vector<Object_t> v2;
01173     h (v1, adg_copy, v2);
01174     Object_t o= v2[0];
01175     costs+= eliminate (o, adg_copy);
01176     el_seq.push_back (o);
01177     eliminatable_objects (adg_copy, v1);
01178   }
01179   return costs;
01180 }
01181 
01194 template <class Object_t, class Ad_graph_t, class Heuristic_t>
01195 inline int use_heuristic_noconst (Ad_graph_t& adg, vector<Object_t>& el_seq,
01196                                    Heuristic_t h) {
01197   Ad_graph_t& adg_copy (adg);
01198   vector<Object_t> v1;
01199   eliminatable_objects (adg_copy, v1);
01200   int costs= 0;
01201   el_seq.resize (0); // clean elimination sequence
01202 
01203   while (!v1.empty()) {
01204     vector<Object_t> v2;
01205     h (v1, adg_copy, v2);
01206     Object_t o= v2[0];
01207     costs+= eliminate (o, adg_copy);
01208     el_seq.push_back (o);
01209     eliminatable_objects (adg_copy, v1);
01210   }
01211   return costs;
01212 }
01213 
01224 template <class Object_t, class Ad_graph_t, class Heuristic_t>
01225 inline int use_heuristic_debug (const Ad_graph_t& adg, vector<Object_t>& el_seq,
01226                                  Heuristic_t h) {
01227   // Ad_graph_t adg_copy (adg);
01228   Ad_graph_t adg_copy; 
01229   write_graph ("\nuse_heuristic_debug: passed graph", adg);
01230   cout << "edges are ";
01231   typename Ad_graph_t::edge_iterator ei, e_end;
01232   for (tie (ei, e_end)= edges (adg); ei != e_end; ++ei)
01233     cout << '(' << source (*ei, adg) << ", " << target (*ei, adg) << "), ";
01234   cout << "\n";
01235 
01236   write_graph ("\nuse_heuristic_debug: copied graph", adg_copy);
01237   adg_copy= adg;
01238   write_graph ("\nuse_heuristic_debug: copied graph", adg_copy);
01239   vector<Object_t> v1;
01240   eliminatable_objects (adg_copy, v1);
01241   int costs= 0;
01242   el_seq.resize (0); // clean elimination sequence
01243 
01244   while (!v1.empty()) {
01245     write_vector ("use_heuristic_debug: eliminatable objects", v1);
01246     vector<Object_t> v2;
01247     h (v1, adg_copy, v2);
01248     write_vector ("use_heuristic_debug: selected objects", v2);
01249     Object_t o= v2[0];
01250     costs+= eliminate (o, adg_copy);
01251     write_graph ("use_heuristic_debug: resulting graph", adg_copy);
01252     el_seq.push_back (o);
01253     eliminatable_objects (adg_copy, v1);
01254   }
01255   return costs;
01256 }
01257 
01258 
01270 template <class Object_t, class Ad_graph_t, class Heuristic_t, class Output_t>
01271 inline int use_heuristic_trace (const Ad_graph_t& adg, vector<Object_t>& el_seq,
01272                                 Heuristic_t h, Output_t output) {
01273   Ad_graph_t adg_copy (adg);
01274   vector<Object_t> v1;
01275   eliminatable_objects (adg_copy, v1);
01276   int costs= 0;
01277   el_seq.resize (0); // clean elimination sequence
01278 
01279   while (!v1.empty()) {
01280     vector<Object_t> v2;
01281     h (v1, adg_copy, v2);
01282     Object_t o= v2[0];
01283     int ocosts= eliminate (o, adg_copy);
01284     costs+= ocosts;
01285     output (cout, o); 
01286     cout << " costs " << ocosts << " --> overall " << costs << endl;
01287     el_seq.push_back (o);
01288     eliminatable_objects (adg_copy, v1);
01289   }
01290   return costs;
01291 }
01292 
01306 template <class Object_t, class Ad_graph_t, class Heuristic_t, class Output_t>
01307 inline int apply_heuristic (const Ad_graph_t& adg, vector<Object_t>& el_seq,
01308                             Heuristic_t h, Output_t output) {
01309   Ad_graph_t adg_copy (adg);
01310   vector<Object_t> v1;
01311   eliminatable_objects (adg_copy, v1);
01312   output.write_graph ("Original graph", adg_copy);
01313   int costs= 0, iteration= 0;
01314   el_seq.resize (0); // clean elimination sequence
01315 
01316   while (!v1.empty()) {
01317     vector<Object_t> v2;
01318     h (v1, adg_copy, v2);
01319     Object_t o= v2[0];
01320     int ocosts= eliminate (o, adg_copy);
01321     costs+= ocosts;
01322     output << "Elimination of " << o << " costs " << ocosts << " --> overall " << costs << '\n';
01323     std::ostringstream gtext; gtext << "Graph after " << ++iteration << "iterations\n";
01324     output.write_graph (gtext.str(), adg_copy);
01325     el_seq.push_back (o);
01326     eliminatable_objects (adg_copy, v1);
01327   }
01328   return costs;
01329 }
01330 
01332 template <class Object_t, class Ad_graph_t, class Heuristic1_t, class Heuristic2_t, 
01333           class Heuristic3_t, class Heuristic4_t, class Heuristic5_t>
01334 inline int best_heuristic (const Ad_graph_t& adg, vector<Object_t>& el_seq,
01335                            Heuristic1_t h1, Heuristic2_t h2, Heuristic3_t h3, 
01336                            Heuristic4_t h4, Heuristic5_t h5);
01337 
01338 // =====================================================
01339 // find subset of v1 that is best w.r.t. op
01340 // =====================================================
01341 
01343 template <class Object_t, class Ad_graph_t, class Op_t>
01344 int find_best_subset (const vector<Object_t>& v1, const Ad_graph_t& adg,
01345                       vector<Object_t>& v2, Op_t op, bool maximize) {
01346   v2.resize (0);
01347 
01348   if (v1.size() == 0) return 0;
01349   int best= maximize ? -op (v1[0], adg) : op (v1[0], adg);
01350   v2.push_back (v1[0]);
01351 
01352   for (size_t c= 1; c < v1.size(); c++) {
01353     Object_t o= v1[c];
01354     int value= maximize ? -op (o, adg) : op (o, adg);
01355     if (value < best) v2.resize (0);
01356     if (value <= best) {
01357       v2.push_back (o); best= value;}
01358   }
01359   return v2.size();
01360 }
01361 
01362 #ifdef USEXAIFBOOSTER
01363 
01364 // =====================================================
01365 // scarcity preserving eliminations
01366 // =====================================================
01367 
01375 int edge_elim_effect (const edge_bool_t be,
01376                       const c_graph_t& angelLCG,
01377                       const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel);
01378 
01386 int edge_elim_effect(const EdgeElim ee,
01387                      const c_graph_t& angelLCG,
01388                      const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel);
01389 
01398 bool maintaining_edge_eliminations(const vector<EdgeElim>& bev1,
01399                                    const c_graph_t& angelLCG,
01400                                    const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01401                                    vector<EdgeElim>& bev2);
01402 
01411 bool reducing_edge_eliminations(const vector<EdgeElim>& bev1,
01412                                 const c_graph_t& angelLCG,
01413                                 const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01414                                 vector<EdgeElim>& bev2);
01415 
01426 bool refill_avoiding_edge_eliminations(const vector<EdgeElim>& bev1,
01427                                        c_graph_t& angelLCG,
01428                                        const refillDependenceMap_t refillDependences,
01429                                        vector<EdgeElim>& bev2);
01430 
01434 bool rerouting_considerate_edge_eliminations(const vector<EdgeElim>& bev,
01435                                              const c_graph_t& angelLCG,
01436                                              const std::vector<Transformation>& transformationsPerformedV,
01437                                              vector<EdgeElim>& reroutingConsiderateEdgeElimsV);
01438 
01439 unsigned int lowestMarkowitzEdgeElim(const vector<EdgeElim>& inEEV,
01440                                      const c_graph_t& angelLCG,
01441                                      vector<EdgeElim>& outEEV);
01442 
01443 bool reverseModeEdgeElim(const vector<EdgeElim>& inEEV,
01444                          const c_graph_t& angelLCG,
01445                          vector<EdgeElim>& outEEV);
01446 
01447 // ==============================================================================
01448 // |                    FILTERS FOR REROUTINGS                                  |
01449 // ==============================================================================
01450 
01454 size_t noncyclicReroutings(const vector<Rerouting>& erv,
01455                            const std::vector<Transformation>& transformationsPerformedV,
01456                            const c_graph_t& angelLCG,
01457                            vector<Rerouting>& noncyclicReroutingsV);
01458 /*
01459 bool maintaining_reroutings (const vector<edge_reroute_t>& erv,
01460                              const c_graph_t& angelLCG,
01461                              const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01462                              vector<edge_reroute_t>& maintainReroutingsV);
01463 */
01464 
01468 bool reducing_reroutings (const vector<Rerouting>& erv,
01469                           const c_graph_t& angelLCG,
01470                           const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01471                           vector<Rerouting>& reducingReroutingsV);
01472 
01473 // ==============================================================================
01474 // |            FILTERS FOR ELIMINATIONS AND REROUTINGS (TRANSFORMATIONS)       |
01475 // ==============================================================================
01476 
01480 int transformation_effect(const Transformation t,
01481                           const c_graph_t& angelLCG,
01482                           const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel);
01483 
01487 bool all_viable_transformations(c_graph_t& angelLCG,
01488                                 const std::vector<Transformation>& transformationsPerformedV,
01489                                 vector<Transformation>& allViableTransformationsV);
01490 
01494 bool maintaining_transformations(const vector<Transformation>& tv,
01495                                  const c_graph_t& angelLCG,
01496                                  const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01497                                  vector<Transformation>& maintainingTransformationsV);
01498 
01503 bool reducing_transformations(const vector<Transformation>& tv,
01504                               const c_graph_t& angelLCG,
01505                               const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01506                               vector<Transformation>& reducingTransformationsV);
01507 
01511 bool refill_avoiding_transformations(const vector<Transformation>& tv,
01512                                      c_graph_t& angelLCG,
01513                                      const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01514                                      const refillDependenceMap_t& refillDependences,
01515                                      vector<Transformation>& refillAvoidingTransformationsV);
01516 
01520 bool rerouting_considerate_transformations(const vector<Transformation>& tv,
01521                                            const c_graph_t& angelLCG,
01522                                            const std::vector<Transformation>& transformationsPerformedV,
01523                                            vector<Transformation>& reroutingConsiderateTransformationsV); 
01524 
01528 bool lowest_markowitz_transformations(const vector<Transformation>& tv,
01529                                       const c_graph_t& angelLCG,
01530                                       vector<Transformation>& lowestMarkowitzTransformationsV);
01531 
01535 bool reverse_mode_transformations (const vector<Transformation>& tv,
01536                                    const c_graph_t& angelLCG,
01537                                    vector<Transformation>& reverseModeTransformationsV);
01538 
01539 #endif // USEXAIFBOOSTER
01540 
01541 #ifdef USE_MPI
01542 
01543 template <class Heuristic_t, class Comm_t>
01544 class par_heuristic_t {
01545   Heuristic_t       h;
01546   Comm_t            comm;
01547 public:
01549   par_heuristic_t (Heuristic_t _h, Comm_t _comm) : h (_h), comm (_comm) {}
01550   template <class Vector_t, class Ad_graph_t>
01551   int operator() (const Vector_t& v1, const Ad_graph_t& adg, Vector_t& v2); 
01552 };
01553 
01554 template <class Comm_t>
01555 class split_vector_t {
01556   Comm_t            comm;
01557 public:
01558   split_vector_t (Comm_t _comm) : comm (_comm) {}
01559   template <class Vector_t, class Ad_graph_t>
01560   int operator() (const Vector_t& v1, const Ad_graph_t&, Vector_t& v2) {
01561     v2.resize (0);
01562     int me= comm.Get_rank(), np= comm.Get_size();
01563     size_t first= block_begin (me, np, v1.size()), last= block_begin (me + 1, np, v1.size()) - 1;
01564     for (; first <= last; first++) v2.push_back (v1[first]);
01565     return v2.size(); }
01566 };
01567 
01568 typedef split_vector_t<GMPI::Intracomm> std_split_vector_t;
01569 
01570 template <class Comm_t>
01571 class bcast_best_t {
01572   Comm_t            comm;
01573 public:
01574   bcast_best_t (Comm_t _comm) : comm (_comm) {}
01575   template <class Vector_t, class Ad_graph_t>
01576   int operator() (const Vector_t& v1, const Ad_graph_t&, Vector_t& v2);
01577 };
01578 
01579 typedef bcast_best_t<GMPI::Intracomm> std_bcast_best_t;
01580 
01581 template <class Heuristic_t, class Comm_t>
01582 class par_frame_t {
01583 private:
01584   split_vector_t<Comm_t>   my_split_vector;
01585   Heuristic_t              h;
01586   bcast_best_t<Comm_t>     my_bcast_best;
01587   heuristic_triplet_t<split_vector_t<Comm_t>,Heuristic_t,bcast_best_t<Comm_t> > my_triplet;
01588 public:
01589   par_frame_t (Heuristic_t _h, Comm_t _comm) : my_split_vector (_comm), h (_h), 
01590                        my_bcast_best (_comm), my_triplet (my_split_vector, h, my_bcast_best) {}
01591   template <class Vector_t, class Ad_graph_t>
01592   int operator() (const Vector_t& v1, const Ad_graph_t& adg, Vector_t& v2) {
01593     return my_triplet (v1, adg, v2); }
01594 };
01595 
01596 template <class Heuristic1_t, class Heuristic2_t, class Comm_t>
01597 class par_heuristic_pair_t {
01598 private:
01599   typedef par_heuristic_t<Heuristic1_t,Comm_t>   ph1_t;
01600   typedef par_heuristic_t<Heuristic2_t,Comm_t>   ph2_t;
01601   typedef heuristic_pair_t<ph1_t,ph2_t>          pair_t;
01602   typedef par_frame_t<pair_t,Comm_t>             par_heuristic_t;
01603   ph1_t              ph1;
01604   ph2_t              ph2;
01605   pair_t             pair;
01606   par_heuristic_t    par_heuristic;
01607 public:
01608   par_heuristic_pair_t (Heuristic1_t _h1, Heuristic2_t _h2, Comm_t _comm) :
01609     ph1 (_h1, _comm), ph2 (_h2, _comm), pair (ph1, ph2), par_heuristic (pair, _comm) {}
01610   template <class Vector_t, class Ad_graph_t>
01611   int operator() (const Vector_t& v1, const Ad_graph_t& adg, Vector_t& v2) {
01612     return par_heuristic (v1, adg, v2); }
01613 };
01614 
01615 template <class Heuristic1_t, class Heuristic2_t, class Heuristic3_t, class Comm_t>
01616 class par_heuristic_triplet_t {
01617 private:
01618   typedef par_heuristic_t<Heuristic1_t,Comm_t>   ph1_t;
01619   typedef par_heuristic_t<Heuristic2_t,Comm_t>   ph2_t;
01620   typedef par_heuristic_t<Heuristic3_t,Comm_t>   ph3_t;
01621   typedef heuristic_triplet_t<ph1_t,ph2_t,ph3_t> triplet_t;
01622   typedef par_frame_t<triplet_t,Comm_t>          par_heuristic_t;
01623   ph1_t              ph1;
01624   ph2_t              ph2;
01625   ph3_t              ph3;
01626   triplet_t          triplet;
01627   par_heuristic_t    par_heuristic;
01628 public:
01629   par_heuristic_triplet_t (Heuristic1_t _h1, Heuristic2_t _h2, Heuristic3_t _h3, Comm_t _comm) :
01630     ph1 (_h1, _comm), ph2 (_h2, _comm), ph3 (_h3, _comm), triplet (ph1, ph2, ph3), 
01631     par_heuristic (triplet, _comm) {}
01632   template <class Vector_t, class Ad_graph_t>
01633   int operator() (const Vector_t& v1, const Ad_graph_t& adg, Vector_t& v2) {
01634     return par_heuristic (v1, adg, v2); }
01635 };
01636 
01637 #endif // USE_MPI
01638 
01639 } // namespace angel
01640 
01641 #include "heuristics_impl.hpp"
01642 
01643 #endif  // _heuristics_include_
01644 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines