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