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 _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