angel
mercurial changeset:
|
00001 // $Id: heuristics_impl.hpp,v 1.5 2004/02/22 18:44:46 gottschling Exp $ 00002 /* 00003 ############################################################# 00004 # This file is part of angel released under the BSD license # 00005 # The full COPYRIGHT notice can be found in the top # 00006 # level directory of the angel distribution # 00007 ############################################################# 00008 */ 00009 00010 00011 #include <set> 00012 // #include <limits> 00013 #include <limits.h> 00014 #include "angel_exceptions.hpp" 00015 00016 namespace angel { 00017 using std::vector; 00018 00019 template <typename Heuristic_t> 00020 int lowest_markowitz_face_complete_t<Heuristic_t>::operator() (const vector<line_graph_t::face_t>& fv1, 00021 const line_graph_t& lg, 00022 vector<line_graph_t::face_t>& fv2) { 00023 fv2.resize(0); 00024 line_graph_t::const_evn_t evn= get(boost::vertex_name, lg); 00025 00026 // if there are still faces from the vertex with 00027 // the lowest Markowitz degree chosen at last return these faces 00028 typedef line_graph_t::face_t face_t; 00029 if (lastv != -1) { 00030 for (size_t c= 0; c < fv1.size(); c++) { 00031 face_t f= fv1[c]; 00032 if (lastv == evn[source(f, lg)].second) fv2.push_back (f); } 00033 if (fv2.size() != 0) return fv2.size(); 00034 } 00035 00036 // otherwise search new vertex (vertices) 00037 vector<int> mdegree; 00038 markowitz_on_line_graph (lg, mdegree); 00039 00040 vector<face_t> fvlm; // faces via vertices with miminal Markowitz 00041 fvlm.push_back (fv1[0]); 00042 int minm= mdegree[evn[source(fv1[0], lg)].second]; // minimal Markowitz 00043 00044 for (size_t c= 1; c < fv1.size(); c++) { 00045 face_t f= fv1[c]; 00046 int m= mdegree[evn[source(f, lg)].second]; 00047 if (m < minm) {fvlm.resize (0); minm= m;} 00048 if (m == minm) fvlm.push_back (f); } 00049 00050 tiebreaker (fvlm, lg, fv2); 00051 THROW_DEBUG_EXCEPT_MACRO (fv2.size() == 0, consistency_exception, "Tiebreaker returned empty vector"); 00052 lastv= evn[source(fv2[0], lg)].second; 00053 00054 // test if all returned faces belong to the same vertex 00055 #ifndef NDEBUG 00056 for (size_t c= 1; c < fv2.size(); c++) 00057 THROW_EXCEPT_MACRO (lastv != evn[source(fv2[c], lg)].second, consistency_exception, 00058 "Returned faces does not belong to the same vertex"); 00059 #endif 00060 00061 return fv2.size(); 00062 } // end of operator 00063 00064 00065 00066 template <class Vertex_heuristic_t> 00067 int emulated_vertex_heuristic_t<Vertex_heuristic_t>::operator() (const vector<edge_ij_elim_t>& eev1, 00068 const c_graph_t& cg, 00069 vector<edge_ij_elim_t>& eev2) { 00070 eev2.resize (0); 00071 00072 // looking for egde eliminations belonging to last vertex elimination 00073 // and which other vertex eliminations could be performed 00074 std::set<c_graph_t::vertex_t> vs; 00075 for (size_t c= 0; c < eev1.size(); c++) { 00076 c_graph_t::vertex_t v= eev1[c].front ? eev1[c].j : eev1[c].i; 00077 if (v == last_vertex) eev2.push_back (eev1[c]); 00078 vs.insert (v);} 00079 00080 if (eev2.size() > 0) return eev2.size(); // belonging to last vertex elimination 00081 00082 vector<c_graph_t::vertex_t> vv1 (vs.begin(), vs.end()), vv2; 00083 h (vv1, cg, vv2); 00084 for (size_t c= 0; c < eev1.size(); c++) { 00085 c_graph_t::vertex_t v= eev1[c].front ? eev1[c].j : eev1[c].i; 00086 if (find (vv2.begin(), vv2.end(), v) != vv2.end()) eev2.push_back (eev1[c]); } 00087 return eev2.size(); 00088 } 00089 00090 template <class Object_t, class Ad_graph_t, class Heuristic1_t, class Heuristic2_t, 00091 class Heuristic3_t, class Heuristic4_t, class Heuristic5_t> 00092 inline int best_heuristic (const Ad_graph_t& adg, vector<Object_t>& el_seq, 00093 Heuristic1_t h1, Heuristic2_t h2, Heuristic3_t h3, 00094 Heuristic4_t h4, Heuristic5_t h5) { 00095 vector<std::pair<int, vector<Object_t> > > results (5); 00096 results[0].first= use_heuristic (adg, results[0].second, h1); 00097 results[1].first= use_heuristic (adg, results[1].second, h2); 00098 results[2].first= use_heuristic (adg, results[2].second, h3); 00099 results[3].first= use_heuristic (adg, results[3].second, h4); 00100 results[4].first= use_heuristic (adg, results[4].second, h5); 00101 00102 size_t bestIndex = 0; 00103 int bestCost = results[0].first; 00104 for (size_t c = 1; c < 5; c++) { 00105 if (results[c].first < bestCost) { 00106 bestIndex = c; 00107 bestCost = results[c].first; 00108 } 00109 } 00110 el_seq = results[bestIndex].second; 00111 return bestCost; 00112 } 00113 00114 #ifdef USE_MPI 00115 template <class Heuristic_t, class Comm_t> 00116 template <class Vector_t, class Ad_graph_t> 00117 int par_heuristic_t<Heuristic_t, Comm_t>::operator() (const Vector_t& v1, const Ad_graph_t& adg, 00118 Vector_t& v2) { 00119 00120 // best local objects 00121 typedef typename Heuristic_t::objective_t objective_t; 00122 h (v1, adg, v2); 00123 objective_t my_objective= h.objective(), best_objective; 00124 00125 // find best global objective value 00126 MPI::Datatype datatype= GMPI::which_mpi_t (my_objective); 00127 MPI::Op op= h.to_maximize() ? MPI::MAX : MPI::MIN; 00128 comm.Allreduce (&my_objective, &best_objective, 1, datatype, op); 00129 00130 // if there are better objectives elsewhere --> throw my objects away 00131 if (my_objective != best_objective) v2.resize (0); 00132 return v2.size(); 00133 } 00134 00135 template <class Comm_t> 00136 template <class Vector_t, class Ad_graph_t> 00137 int bcast_best_t<Comm_t>::operator() (const Vector_t& v1, const Ad_graph_t&, Vector_t& v2) { 00138 int my_pe_size[2], sum_pe_size[2]; 00139 my_pe_size[1]= v1.size(); my_pe_size[0]= v1.size() == 0 ? 0 : comm.Get_rank(); 00140 comm.Allreduce (my_pe_size, sum_pe_size, 2, MPI::INT, MPI::SUM); 00141 THROW_EXCEPT_MACRO (sum_pe_size[1] != 1, consistency_exception, "v1 must contain 1 element overall!"); 00142 v2= v1; 00143 GMPI::comm_ref_t<int, Vector_t> comm_ref (v2); // reference used in communication 00144 comm.Bcast (comm_ref, sum_pe_size[0]); 00145 return v2.size(); 00146 } 00147 00148 #endif // USE_MPI 00149 00151 template <class Object_t, class Ad_graph_t, class Op_t, class Objective_t> 00152 int standard_heuristic_op (const vector<Object_t>& v1, const Ad_graph_t& adg, 00153 vector<Object_t>& v2, Op_t op, base_heuristic_t<Objective_t>& h) { 00154 v2.resize (0); 00155 Objective_t best= h.to_maximize() ? std::numeric_limits<Objective_t>::min() : 00156 std::numeric_limits<Objective_t>::max(); 00157 00158 for (size_t c= 0; c < v1.size(); c++) { 00159 Object_t o= v1[c]; 00160 Objective_t value= op (o, adg); 00161 if (h.to_maximize()) { 00162 if (value > best) v2.resize (0); 00163 if (value >= best) { v2.push_back (o); best= value; } 00164 } else { 00165 if (value < best) v2.resize (0); 00166 if (value <= best) { v2.push_back (o); best= value;} } } 00167 h.set_objective (best); 00168 return v2.size(); 00169 } 00170 00171 00172 } // namespace angel