angel » src

heuristics.cpp

Go to the documentation of this file.
00001 // $Id: heuristics.cpp,v 1.11 2008/02/28 14:57:33 gottschling Exp $
00002 
00003 #include <limits.h>
00004 #include <algorithm>
00005 
00006 #include "angel/include/heuristics.hpp"
00007 #include "angel/include/angel_exceptions.hpp"
00008 #include "angel/include/angel_tools.hpp"
00009 #ifdef USEXAIFBOOSTER
00010 #include "angel/include/reroutings.hpp"
00011 using namespace xaifBoosterCrossCountryInterface;
00012 #endif
00013 
00014 namespace angel {
00015 
00016 using namespace std;
00017 using namespace boost;
00018 
00019 // =====================================================
00020 // for vertex elimination
00021 // =====================================================
00022 
00023 int forward_mode_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
00024                                        const c_graph_t& cg, 
00025                                        vector<c_graph_t::vertex_t>& vv2) {
00026   vv2.resize (0);
00027   if (vv1.size() == 0) {set_empty_objective (); return 0; }
00028   vv2.push_back (vv1[0]);
00029 
00030   for (size_t c= 1; c < vv1.size(); c++) 
00031     if (vv1[c] < vv2[0]) vv2[0]= vv1[c];
00032   set_objective (vv2[0]);
00033   return 1;
00034 }
00035 
00036 forward_mode_vertex_t forward_mode_vertex;
00037 
00038 // -------------------------------------------------------------------------
00039 // reverse mode
00040 // -------------------------------------------------------------------------
00041 
00042 int reverse_mode_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
00043                                        const c_graph_t& cg, 
00044                                        vector<c_graph_t::vertex_t>& vv2) {
00045   vv2.resize (0);
00046   if (vv1.size() == 0) {set_empty_objective (); return 0; }
00047   vv2.push_back (vv1[0]);
00048 
00049   for (size_t c= 1; c < vv1.size(); c++)
00050     if (vv1[c] > vv2[0]) vv2[0]= vv1[c];
00051   set_objective (vv2[0]);
00052   return 1;
00053 }
00054 
00055 reverse_mode_vertex_t reverse_mode_vertex;
00056 
00057 // -------------------------------------------------------------------------
00058 // Lowest Markowitz 
00059 // -------------------------------------------------------------------------
00060 
00061 // operator for lowest Markowitz on vertices 
00062 struct lmv_op_t {
00063   int operator() (c_graph_t::vertex_t v, const c_graph_t& cg) {
00064     return in_degree (v, cg) * out_degree (v, cg); }
00065 };
00066 
00067 int lowest_markowitz_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
00068                                            const c_graph_t& cg, 
00069                                            vector<c_graph_t::vertex_t>& vv2) {
00070   lmv_op_t   lmv_op;
00071   return standard_heuristic_op (vv1, cg, vv2, lmv_op, *this);
00072 }
00073 
00074 lowest_markowitz_vertex_t lowest_markowitz_vertex;
00075 
00076 // -------------------------------------------------------------------------
00077 // Lowest relative Markowitz
00078 // -------------------------------------------------------------------------
00079 
00080 // operator for lowest relative Markowitz on vertices and edges
00081 struct lrm_op_t {
00082   vector<int> indep, dep;
00083   lrm_op_t (const c_graph_t& cg) : indep (num_vertices (cg)), dep (num_vertices (cg)) {
00084     number_independent_vertices (cg, indep); number_dependent_vertices (cg, dep); }
00085   int operator() (bool front, c_graph_t::edge_t edge, const c_graph_t& cg) {
00086     return front ? out_degree (target (edge, cg), cg) - dep[target (edge, cg)]
00087                  : in_degree (source (edge, cg), cg) - indep[source (edge, cg)]; }
00088   int operator() (edge_bool_t eb, const c_graph_t& cg) {
00089     return eb.second ? out_degree (target (eb.first, cg), cg) - dep[target (eb.first, cg)]
00090                      : in_degree (source (eb.first, cg), cg) - indep[source (eb.first, cg)]; }
00091   int operator() (c_graph_t::vertex_t v, const c_graph_t& cg) {
00092     return in_degree (v, cg) * out_degree (v, cg) - indep[v] * dep[v]; }
00093 };
00094 
00095 int lowest_relative_markowitz_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
00096                                                     const c_graph_t& cg, 
00097                                                     vector<c_graph_t::vertex_t>& vv2) {
00098   lrm_op_t   lrm_op (cg);
00099   return standard_heuristic_op (vv1, cg, vv2, lrm_op, *this);
00100 }
00101 
00102 lowest_relative_markowitz_vertex_t lowest_relative_markowitz_vertex;
00103 
00104 // -------------------------------------------------------------------------
00105 // subroutine of Lowest fill-in
00106 // -------------------------------------------------------------------------
00107 
00108 // how many new in_edges has j:target(e) by back-eliminating e
00109 int new_in_edges (c_graph_t::edge_t e, const c_graph_t& cg) {
00110 
00111   typedef c_graph_t::vertex_t        vertex_t;
00112   typedef c_graph_t::iei_t           iei_t;
00113 
00114   iei_t    siei, sie_end, tiei, tie_end;
00115   tie (siei, sie_end)= in_edges (source (e, cg), cg);
00116   tie (tiei, tie_end)= in_edges (target (e, cg), cg);
00117   int new_edges= 0;
00118 
00119   vector<vertex_t> nsl; // list of new sources to check double insertions
00120 
00121   for (; siei != sie_end; ++siei) {
00122     vertex_t ss= source (*siei, cg);
00123     iei_t i= tiei;
00124     for (; i != tie_end; ++i)
00125       if (source (*i, cg) == ss) break;
00126     if (i == tie_end
00127         && find (nsl.begin(), nsl.end(), ss) == nsl.end()) {
00128       nsl.push_back (ss); new_edges++; }
00129   }
00130 
00131   return new_edges;
00132 }
00133 
00134 // how many new out_edges has j:=source(e) by front-eliminating e
00135 int new_out_edges (c_graph_t::edge_t e, const c_graph_t& cg) {
00136 
00137   typedef c_graph_t::vertex_t        vertex_t;
00138   typedef c_graph_t::oei_t           oei_t;
00139 
00140   oei_t    soei, soe_end, toei, toe_end;
00141   tie (soei, soe_end)= out_edges (source (e, cg), cg);
00142   tie (toei, toe_end)= out_edges (target (e, cg), cg);
00143   int new_edges= 0;
00144 
00145   vector<vertex_t> ntl; // list of new targets to check double insertions
00146 
00147   for (; toei != toe_end; ++toei) {
00148     vertex_t tt= target (*toei, cg);
00149     oei_t i= soei;
00150     for (; i != soe_end; ++i)
00151       if (target (*i, cg) == tt) break;
00152     if (i == soe_end
00153         && find (ntl.begin(), ntl.end(), tt) == ntl.end()) {
00154       ntl.push_back (tt); new_edges++; }
00155   }
00156 
00157   return new_edges;
00158 }
00159 
00160 
00161 // -------------------------------------------------------------------------
00162 // Lowest fill-in
00163 // -------------------------------------------------------------------------
00164 
00165 
00166 // operator for lowest fill-in on vertices 
00167 struct fiv_op_t {
00168   int operator() (c_graph_t::vertex_t v, const c_graph_t& cg) {
00169     int                  fill_ins= 0;
00170     c_graph_t::iei_t     iei, ie_end;
00171     for (tie (iei, ie_end)= in_edges (v, cg); iei != ie_end; ++iei)
00172       fill_ins+= new_out_edges (*iei, cg);
00173     return fill_ins; }
00174 };
00175 
00176 int lowest_fill_in_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
00177                                          const c_graph_t& cg, 
00178                                          vector<c_graph_t::vertex_t>& vv2) {
00179   fiv_op_t   fiv_op;
00180   return standard_heuristic_op (vv1, cg, vv2, fiv_op, *this);
00181 }
00182 
00183 lowest_fill_in_vertex_t lowest_fill_in_vertex;
00184 
00185 // -------------------------------------------------------------------------
00186 // subroutines of LMMD MOMR
00187 // -------------------------------------------------------------------------
00188 
00189 // how much the markowitz degree of j:=source(e) is enlarged by front-eliminating e
00190 // this is in_degree(j) * #new out_edges(j) 
00191 int markowitz_enlargement_front (c_graph_t::edge_t e, const c_graph_t& cg,
00192                                  bool eliminate_parallel_edges= false) {
00193   int ee= 0; // number of eliminated edges
00194   c_graph_t::vertex_t s= source (e, cg), t= target (e, cg);
00195   if (vertex_type (t, cg) == intermediate){ // if dependent edges are not eliminated
00196     if (eliminate_parallel_edges) {
00197       c_graph_t::oei_t soei, soe_end;
00198       for (tie (soei, soe_end)= out_edges (s, cg); soei != soe_end; soei++)
00199         ee+= target (*soei, cg) == t;
00200     } else ee= 1;
00201   }
00202   return in_degree (source (e, cg), cg) * (new_out_edges (e, cg) - ee);
00203 }
00204 
00205 // how much is the markowitz degree of j:=target(e2) enlarged by front-eliminating e
00206 int markowitz_enlargement_front (c_graph_t::edge_t e, c_graph_t::edge_t e2, 
00207                                  const c_graph_t& cg) {
00208 
00209   THROW_DEBUG_EXCEPT_MACRO (target (e, cg) != source (e2, cg), consistency_exception,
00210                          "e and e2 does not match"); 
00211 
00212   c_graph_t::vertex_t j= target (e2, cg), se= source (e, cg), te= target (e, cg);
00213 
00214   // if e is last in_edge of te than e2 will be eliminated -> j has one in_edge less
00215   // int in_edge_change= in_degree (te, cg) == 1 ? -1 : 0; 
00216 
00217   // if e is last in_edge of te than e2 and its parallel edges will be eliminated 
00218   // -> j has one or more in_edges less
00219   int in_edge_change= in_degree (te, cg) == 1 ? - count_parallel_edges (e2, cg) : 0; 
00220 
00221   // if source(e) is not source of an in_edge of j -> j has one in_edge more
00222   c_graph_t::iei_t  iei, ie_end;
00223   for (tie (iei, ie_end)= in_edges (j, cg); iei != ie_end; ++iei)
00224     if (source (*iei, cg) == se) break;
00225   if (iei == ie_end) in_edge_change++;
00226 
00227   return in_edge_change * out_degree (j, cg);
00228 }
00229 
00230 // how much the markowitz degree of j:=target(e) is enlarged by back-eliminating e
00231 // this is out_degree(j) * #new in_edges(j) 
00232 int markowitz_enlargement_back (c_graph_t::edge_t e, const c_graph_t& cg,
00233                                 bool eliminate_parallel_edges= false) {
00234 
00235   int ee= 0; // number of eliminated edges
00236   if (eliminate_parallel_edges) {
00237     c_graph_t::vertex_t s= source (e, cg), t= target (e, cg);
00238     c_graph_t::iei_t tiei, tie_end;
00239     for (tie (tiei, tie_end)= in_edges (t, cg); tiei != tie_end; ++tiei)
00240       ee+= source (*tiei, cg) == s;
00241   } else ee= 1;
00242 
00243   return out_degree (target (e, cg), cg) * (new_in_edges (e, cg) - ee);
00244 }
00245 
00246 // how much is the markowitz degree of j:=source(e2) enlarged by back-eliminating e
00247 int markowitz_enlargement_back (c_graph_t::edge_t e, c_graph_t::edge_t e2, 
00248                                 const c_graph_t& cg) {
00249 
00250   // assert (source (e, cg) == target (e2, cg));
00251   THROW_DEBUG_EXCEPT_MACRO (source (e, cg) != target (e2, cg), consistency_exception,
00252                          "e and e2 does not match"); 
00253 
00254   c_graph_t::vertex_t j= source (e2, cg), se= source (e, cg), te= target (e, cg);
00255 
00256   // if e is last out_edge of se than e2 will be eliminated -> j has one out_edge less
00257   int out_edge_change= out_degree (se, cg) == 1 ? -1 : 0; 
00258 
00259   // if target(e) is not target of an out_edge of j -> j has one out_edge more
00260   c_graph_t::oei_t    oei, oe_end;
00261   for (tie (oei, oe_end)= out_edges (j, cg); oei != oe_end; ++oei)
00262     if (target (*oei, cg) == te) break;
00263   if (oei == oe_end) out_edge_change++;
00264 
00265   return out_edge_change * in_degree (j, cg);
00266 }
00267 
00268 // how much is the markowitz degree of all neighbors of v increased by its elimination
00269 // multiply occurred neighbors are counted only once
00270 int markowitz_enlargement_all_neighbors (c_graph_t::vertex_t v, const c_graph_t& cg) {
00271 
00272   using namespace std;
00273 
00274   typedef c_graph_t::vertex_t              vertex_t;
00275 
00276   int enl= 0;
00277 
00278   // parallel edges does not cause multiple Markowitz changes
00279   vector<vertex_t> cv; // already checked vertices
00280   cv.reserve (10);     // reduce mallocs
00281 
00282   c_graph_t::iei_t     iei, ie_end;
00283   tie (iei, ie_end)= in_edges (v, cg);
00284   for (; iei != ie_end; ++iei) {
00285     vertex_t v= source (*iei, cg);
00286     if (find (cv.begin(), cv.end(), v) == cv.end()) {
00287       enl+= markowitz_enlargement_front (*iei, cg, true);
00288       cv.push_back (v); } }
00289 
00290   cv.resize (0);             // reduce search space
00291   c_graph_t::oei_t     oei, oe_end;
00292   tie (oei, oe_end)= out_edges (v, cg);
00293   for (; oei != oe_end; ++oei) {
00294     vertex_t v= target (*oei, cg);    
00295     if (find (cv.begin(), cv.end(), v) == cv.end()) {
00296       enl+= markowitz_enlargement_back (*oei, cg, true);
00297       cv.push_back (v); } }
00298   return enl;
00299 }
00300 
00301 struct markowitz_enlargement_front_t {
00302   c_graph_t::edge_t _e;                  // first edge is stored
00303   markowitz_enlargement_front_t (c_graph_t::edge_t e) : _e (e) {}
00304   int operator() (c_graph_t::edge_t e2, const c_graph_t& cg) const {
00305     return markowitz_enlargement_front (_e, e2, cg); }
00306 };
00307 
00308 struct markowitz_enlargement_back_t {
00309   c_graph_t::edge_t _e;                  // first edge is stored
00310   markowitz_enlargement_back_t (c_graph_t::edge_t e) : _e (e) {}
00311   int operator() (c_graph_t::edge_t e2, const c_graph_t& cg) const {
00312     return markowitz_enlargement_back (_e, e2, cg); }
00313 };
00314 
00315 
00316 // -------------------------------------------------------------------------
00317 // LMMD
00318 // -------------------------------------------------------------------------
00319 
00320 // operator that computes LMMD value for a single vertex
00321 struct lmmdv_op_t {
00322   double w; // weight
00323   lmmdv_op_t (double _w) : w (_w) {}
00324   int operator() (c_graph_t::vertex_t v, const c_graph_t& cg) {
00325     int markowitz= in_degree (v, cg) * out_degree (v, cg),
00326       damage= markowitz_enlargement_all_neighbors (v, cg);
00327     return int (double (markowitz) + w * double (damage)); }
00328 };
00329 
00330 int lmmd_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
00331                                const c_graph_t& cg, 
00332                                vector<c_graph_t::vertex_t>& vv2) {
00333   lmmdv_op_t      lmmdv_op (weight);
00334   return standard_heuristic_op (vv1, cg, vv2, lmmdv_op, *this);
00335 }
00336   
00337 lmmd_vertex_t lmmd_vertex (1.0);
00338 
00339 // -------------------------------------------------------------------------
00340 // MOMR
00341 // -------------------------------------------------------------------------
00342 
00343 // operator that computes MOMR value for a single vertex
00344 struct momrv_op_t {
00345   int operator() (c_graph_t::vertex_t v, const c_graph_t& cg) {
00346     int momr= in_degree (v, cg) * out_degree (v, cg)
00347               - markowitz_enlargement_all_neighbors (v, cg);
00348 #ifndef NDEBUG
00349     c_graph_t         gtmp (cg);  vertex_elimination (v, gtmp);
00350     THROW_DEBUG_EXCEPT_MACRO (overall_markowitz_degree (cg) - overall_markowitz_degree (gtmp) != momr, 
00351                            consistency_exception, "momr not correct"); 
00352 #endif
00353     return momr; }
00354 };
00355 
00356 int momr_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
00357                                const c_graph_t& cg, 
00358                                vector<c_graph_t::vertex_t>& vv2) {
00359   momrv_op_t      momrv_op;
00360   return standard_heuristic_op (vv1, cg, vv2, momrv_op, *this);
00361 }
00362 
00363 momr_vertex_t momr_vertex;
00364 
00365 // -------------------------------------------------------------------------
00366 // subroutines of Maximal overall path length reduction
00367 // -------------------------------------------------------------------------
00368 
00369 // overall path length reduction of face (e1, e2)
00370 inline int oplr_face (c_graph_t::edge_t e1, c_graph_t::edge_t e2,
00371                       const vector<int>& vni, const vector<int>& vli, 
00372                       const vector<int>& vno, const vector<int>& vlo, 
00373                       const c_graph_t& cg) {
00374 
00375   // assert (target (e1, cg) == source (e2, cg));
00376   THROW_DEBUG_EXCEPT_MACRO (target (e1, cg) != source (e2, cg), consistency_exception,
00377                          "e1 and e2 does not match"); 
00378 
00379   c_graph_t::vertex_t p= source (e1, cg), s= target (e2, cg);
00380 
00381   c_graph_t::edge_t e;
00382   bool found;
00383   boost::tie (e, found)= edge (p, s, cg);
00384 
00385   return found ? vno[s] * (vni[p] + vli[p]) + vni[p] * (vno[s] + vlo[s])
00386                : vni[p] * vno[s];
00387 }
00388 
00389 int oplr_edge_front (c_graph_t::edge_t e,
00390                      const vector<int>& vni, const vector<int>& vli, 
00391                      const vector<int>& vno, const vector<int>& vlo, 
00392                      const c_graph_t& cg) {
00393 
00394   int oplr= 0;
00395   graph_traits<c_graph_t>::out_edge_iterator    oei, oe_end;
00396   tie (oei, oe_end)= out_edges (target (e, cg), cg);
00397 
00398   for (; oei != oe_end; ++oei)
00399     oplr+= oplr_face (e, *oei, vni, vli, vno, vlo, cg);
00400 
00401   return oplr;
00402 }
00403 
00404 int oplr_edge_back (c_graph_t::edge_t e,
00405                     const vector<int>& vni, const vector<int>& vli, 
00406                     const vector<int>& vno, const vector<int>& vlo, 
00407                     const c_graph_t& cg) {
00408 
00409   int oplr= 0;
00410   graph_traits<c_graph_t>::in_edge_iterator    iei, ie_end;
00411   tie (iei, ie_end)= in_edges (source (e, cg), cg);
00412 
00413   for (; iei != ie_end; ++iei)
00414     oplr+= oplr_face (*iei, e, vni, vli, vno, vlo, cg);
00415 
00416   return oplr;
00417 }
00418 
00419 // -------------------------------------------------------------------------
00420 // Maximal overall path length reduction
00421 // -------------------------------------------------------------------------
00422 
00423 // operator that computes path length reduction for a single vertex
00424 struct oplrv_op_t {
00425   vector<int> vni, vli, vno, vlo;
00426   oplrv_op_t (const c_graph_t& cg) {
00427     in_out_path_lengths (cg, vni, vli, vno, vlo); }
00428   int operator () (c_graph_t::vertex_t v, const c_graph_t& cg) {
00429     int oplr= 0;
00430     c_graph_t::iei_t    iei, ie_end;
00431     for (tie (iei, ie_end)= in_edges (v, cg); iei != ie_end; ++iei)
00432       oplr+= oplr_edge_front (*iei, vni, vli, vno, vlo, cg);
00433     return oplr; }
00434 };
00435 
00436 int moplr_vertex_t::operator() (const vector<c_graph_t::vertex_t>& vv1,
00437                                 const c_graph_t& cg, 
00438                                 vector<c_graph_t::vertex_t>& vv2) {
00439   oplrv_op_t oplrv_op (cg);
00440   return standard_heuristic_op (vv1, cg, vv2, oplrv_op, *this);
00441 }
00442 
00443 moplr_vertex_t moplr_vertex;
00444 
00445 // =====================================================
00446 // for edge elimination (in c-graph)
00447 // =====================================================
00448 
00449 int forward_mode_edge_f (const vector<c_graph_t::edge_t>& ev1,
00450                          bool front,
00451                          const c_graph_t& cg,
00452                          vector<c_graph_t::edge_t>& ev2) {
00453   ev2.resize (0);
00454 
00455   if (ev1.size() == 0) return 0;
00456   ev2.push_back (ev1[0]);
00457 
00458   for (size_t c= 1; c < ev1.size(); c++)
00459     if (front ? inv_lex_less (ev1[c], ev2[0], cg) : lex_less (ev1[c], ev2[0], cg)) 
00460       ev2[0]= ev1[c];
00461 
00462   return 1;
00463 }
00464 
00465 // objective function for forward mode in edge elimination
00466 // works up to 47 million vertices in IEEE arithmetic
00467 inline double fme_obj (edge_bool_t eb, const c_graph_t& cg) {
00468   c_graph_t::edge_t   edge= eb.first;
00469   // front is prefered -> add something if not front because we minimize
00470   int high, low, notfront;
00471   if (eb.second) high= target (edge, cg), low= source (edge, cg), notfront= 0;
00472   else high= source (edge, cg), low= target (edge, cg), notfront= 1;
00473   return (2 * high + notfront) * double (cg.x()) + low;
00474 }
00475 
00476 int forward_mode_edge_t::operator() (const vector<edge_bool_t>& ev1,
00477                                      const c_graph_t& cg,
00478                                      vector<edge_bool_t>& ev2) {
00479   ev2.resize (0);
00480   if (ev1.size() == 0) {set_empty_objective (); return 0; }
00481   ev2.push_back (ev1[0]);
00482 
00483   for (size_t c= 1; c < ev1.size(); c++) {
00484 //    THROW_DEBUG_EXCEPT_MACRO (fme_obj (ev1[c], cg) < fme_obj (ev2[0], cg) != lex_less (ev1[c], ev2[0], cg),
00485 //                         consistency_exception, "objective function and comparator does not match");
00486     if (lex_less (ev1[c], ev2[0], cg)) ev2[0]= ev1[c]; }
00487   set_objective (fme_obj (ev2[0], cg));
00488   return 1;
00489 }
00490 
00491 forward_mode_edge_t forward_mode_edge;
00492 
00493 // remark fm: if all eliminatable edges are considered than only front elimination is used
00494 //            this way one can force same sequences in vertex, edge and face elimination
00495 //            when forward mode is used as sole criterion
00496 
00497 // -------------------------------------------------------------------------
00498 // reverse mode
00499 // -------------------------------------------------------------------------
00500 
00501 int reverse_mode_edge_f (const vector<c_graph_t::edge_t>& ev1,
00502                          bool front,
00503                          const c_graph_t& cg,
00504                          vector<c_graph_t::edge_t>& ev2) {
00505   ev2.resize (0);
00506 
00507   if (ev1.size() == 0) return 0;
00508   ev2.push_back (ev1[0]);
00509 
00510   for (size_t c= 1; c < ev1.size(); c++)
00511     if (front ? inv_lex_greater (ev1[c], ev2[0], cg) : lex_greater (ev1[c], ev2[0], cg)) 
00512       ev2[0]= ev1[c];
00513 
00514   return 1;
00515 }
00516 
00517 // objective function for reverse mode in edge elimination
00518 // works up to 47 million vertices in IEEE arithmetic
00519 inline double rme_obj (edge_bool_t eb, const c_graph_t& cg) {
00520   c_graph_t::edge_t   edge= eb.first;
00521   // front is prefered -> add something if front because we maximize
00522   int high, low, front;
00523   if (eb.second) high= target (edge, cg), low= source (edge, cg), front= 1;
00524   else high= source (edge, cg), low= target (edge, cg), front= 0;
00525   return (2 * high + front) * double (cg.x()) + low;
00526 }
00527 
00528 int reverse_mode_edge_t::operator() (const vector<edge_bool_t>& ev1,
00529                                      const c_graph_t& cg,
00530                                      vector<edge_bool_t>& ev2) {
00531   ev2.resize (0);
00532 
00533   if (ev1.size() == 0) {set_empty_objective (); return 0; }
00534   ev2.push_back (ev1[0]);
00535 
00536   for (size_t c= 1; c < ev1.size(); c++) {
00537 //    THROW_DEBUG_EXCEPT_MACRO ((rme_obj (ev1[c], cg) > rme_obj (ev2[0], cg)) != lex_greater (ev1[c], ev2[0], cg),
00538 //                         consistency_exception, "objective function and comparator does not match");
00539     if (lex_greater (ev1[c], ev2[0], cg)) ev2[0]= ev1[c]; }
00540     set_objective (rme_obj (ev2[0], cg));
00541   return 1;
00542 }
00543 
00544 reverse_mode_edge_t reverse_mode_edge;
00545 
00546 // remark rm: if all eliminatable edges are considered than only front elimination is used
00547 //            this way one can force same sequences in vertex, edge and face elimination
00548 //            when reverse mode is used as sole criterion
00549 
00550 // -------------------------------------------------------------------------
00551 // Lowest Markowitz
00552 // -------------------------------------------------------------------------
00553 
00554 int lowest_markowitz_edge_f (const vector<c_graph_t::edge_t>& ev1,
00555                              bool front,
00556                              const c_graph_t& cg,
00557                              vector<c_graph_t::edge_t>& ev2) {
00558   ev2.resize (0);
00559 
00560   if (ev1.size() == 0) return 0;
00561   int min_degree= front ? out_degree (target (ev1[0], cg), cg)
00562                         : in_degree (source (ev1[0], cg), cg);
00563   ev2.push_back (ev1[0]);
00564 
00565   for (size_t c= 1; c < ev1.size(); c++) {
00566     c_graph_t::edge_t e= ev1[c];
00567     int degree= front ? out_degree (target (e, cg), cg)
00568                       : in_degree (source (e, cg), cg);
00569     if (degree < min_degree) ev2.resize (0);
00570     if (degree <= min_degree) {
00571       ev2.push_back (e); min_degree= degree;}
00572   }
00573   return ev2.size();
00574 }
00575 
00576 // operator that computes the Markowitz degree for a single edge elimination
00577 struct lme_op_t {
00578   int operator() (edge_bool_t eb, const c_graph_t& cg) {
00579     return eb.second ? out_degree (target (eb.first, cg), cg)
00580                      : in_degree (source (eb.first, cg), cg); }
00581 };
00582 
00583 int lowest_markowitz_edge_t::operator() (const vector<edge_bool_t>& ev1,
00584                                          const c_graph_t& cg,
00585                                          vector<edge_bool_t>& ev2) {
00586   lme_op_t      lme_op;
00587   return standard_heuristic_op (ev1, cg, ev2, lme_op, *this);
00588 }
00589 
00590 lowest_markowitz_edge_t lowest_markowitz_edge;
00591 
00592 // -------------------------------------------------------------------------
00593 // Lowest relative Markowitz
00594 // -------------------------------------------------------------------------
00595 
00596 int lowest_relative_markowitz_edge_f (const vector<c_graph_t::edge_t>& ev1,
00597                                       bool front,
00598                                       const c_graph_t& cg,
00599                                       vector<c_graph_t::edge_t>& ev2) {
00600   ev2.resize (0);
00601   if (ev1.size() == 0) return 0;
00602   lrm_op_t   lrm_op (cg);
00603   int min_degree= lrm_op (front, ev1[0], cg);
00604   ev2.push_back (ev1[0]);
00605 
00606   for (size_t c= 1; c < ev1.size(); c++) {
00607     int degree= lrm_op (front, ev1[c], cg); 
00608     if (degree < min_degree) ev2.resize (0);
00609     if (degree <= min_degree) {
00610       ev2.push_back (ev1[c]); min_degree= degree;} }
00611   return ev2.size();
00612 }
00613 
00614 int lowest_relative_markowitz_edge_t::operator() (const vector<edge_bool_t>& ev1,
00615                                                   const c_graph_t& cg,
00616                                                   vector<edge_bool_t>& ev2) {
00617   lrm_op_t   lrm_op (cg);
00618   return standard_heuristic_op (ev1, cg, ev2, lrm_op, *this);
00619 }
00620 
00621 lowest_relative_markowitz_edge_t lowest_relative_markowitz_edge;
00622 
00623 // -------------------------------------------------------------------------
00624 // Lowest fill-in
00625 // -------------------------------------------------------------------------
00626 
00627 inline int fill_in_front (c_graph_t::edge_t e, const c_graph_t& cg) {
00628   return new_out_edges (e, cg);
00629 }
00630 
00631 inline int fill_in_back (c_graph_t::edge_t e, const c_graph_t& cg) {
00632   return new_in_edges (e, cg);
00633 }
00634 
00635 
00636 int lowest_fill_in_edge_f (const vector<c_graph_t::edge_t>& ev1,
00637                            bool front,
00638                            const c_graph_t& cg,
00639                            vector<c_graph_t::edge_t>& ev2) {
00640   ev2.resize (0);
00641 
00642   if (ev1.size() == 0) return 0;
00643   int min_degree= front ? fill_in_front (ev1[0], cg)
00644                         : fill_in_back (ev1[0], cg);
00645   ev2.push_back (ev1[0]);
00646 
00647   for (size_t c= 1; c < ev1.size(); c++) {
00648     c_graph_t::edge_t e= ev1[c];
00649     int degree= front ? fill_in_front (e, cg)
00650                       : fill_in_back (e, cg);
00651     if (degree < min_degree) ev2.resize (0);
00652     if (degree <= min_degree) {
00653       ev2.push_back (e); min_degree= degree;}
00654   }
00655 
00656   return ev2.size();
00657 }
00658 
00659 
00660 // -------------------------------------------------------------------------
00661 // LMMD
00662 // -------------------------------------------------------------------------
00663 
00664 lmmd_edge_t lmmd_edge (1.0);
00665 
00666 inline int lmmd_edge_front (c_graph_t::edge_t e, double w, const c_graph_t& cg) {
00667   int markowitz= out_degree (target (e, cg), cg); 
00668   markowitz_enlargement_front_t me (e);
00669   int damage= markowitz_enlargement_front (e, cg)
00670               + sum_over_all_out_edges (target (e, cg), cg, me);
00671   return int (double (markowitz) + w * double (damage));
00672 }
00673 
00674 inline int lmmd_edge_back (c_graph_t::edge_t e, double w, const c_graph_t& cg) {
00675   int markowitz= in_degree (source (e, cg), cg);
00676   markowitz_enlargement_back_t me (e);
00677   int damage= markowitz_enlargement_back (e, cg)
00678               + sum_over_all_in_edges (source (e, cg), cg, me);
00679   return int (double (markowitz) + w * double (damage));
00680 }
00681 
00682 struct lmmde_op_t {
00683   double w; // weight
00684   lmmde_op_t (double _w) : w (_w) {}
00685   int operator() (edge_bool_t eb, const c_graph_t& cg) {
00686     return eb.second ? lmmd_edge_front (eb.first, w, cg)
00687                      : lmmd_edge_back (eb.first, w, cg); }
00688 };
00689 
00690 int lmmd_edge_t::operator() (const vector<edge_bool_t>& ev1,
00691                              const c_graph_t& cg,
00692                              vector<edge_bool_t>& ev2) {
00693   lmmde_op_t      lmmde_op (weight);
00694   return standard_heuristic_op (ev1, cg, ev2, lmmde_op, *this);
00695 }
00696 
00697 
00698 // -------------------------------------------------------------------------
00699 // MOMR
00700 // -------------------------------------------------------------------------
00701 
00702 inline int momr_edge_front (c_graph_t::edge_t e, const c_graph_t& cg) {
00703 
00704   markowitz_enlargement_front_t me (e);
00705   int momr= out_degree (target (e, cg), cg) - markowitz_enlargement_front (e, cg)
00706            - sum_over_all_out_edges (target (e, cg), cg, me);
00707 
00708 #ifndef NDEBUG
00709   c_graph_t         gtmp (cg);
00710 
00711   // eliminating e in gtmp does not work -> edge_descriptor from gtmp needed
00712   c_graph_t::edge_t   etmp;
00713   c_graph_t::ei_t     ei, e_end;
00714   c_graph_t::vertex_t s= source (e, cg), t= target (e, cg);
00715   for (boost::tie (ei, e_end)= edges (gtmp); ei != e_end; ++ei)
00716     if (source (*ei, gtmp) == s && target (*ei, gtmp) == t) {
00717       etmp= *ei; break; }
00718   // assert (ei != e_end); // otherwise edge not found
00719   THROW_DEBUG_EXCEPT_MACRO (ei == e_end, consistency_exception, "No matching edge found"); 
00720 
00721   front_edge_elimination (etmp, gtmp);
00722   // assert (overall_markowitz_degree (cg) - overall_markowitz_degree (gtmp) == momr);
00723   THROW_DEBUG_EXCEPT_MACRO (overall_markowitz_degree (cg) - overall_markowitz_degree (gtmp) != momr, 
00724                          consistency_exception, "momr not correct"); 
00725 #endif
00726   return momr;
00727 }
00728 
00729 inline int momr_edge_back (c_graph_t::edge_t e, const c_graph_t& cg) {
00730   // reduction of markowitz degree in vertex source (e)
00731   int momr= in_degree (source (e, cg), cg);
00732   // target (e) can get a larger markowitz degree due to new in_edges
00733   momr-= markowitz_enlargement_back (e, cg);
00734 
00735   // the predecessors of source (e) can get a larger markowitz degree
00736   // due to a new out_edge to target (e)
00737   c_graph_t::iei_t    iei, ie_end;
00738   tie (iei, ie_end)= in_edges (source (e, cg), cg);
00739   for (; iei != ie_end; ++iei)
00740     momr-= markowitz_enlargement_back (e, *iei, cg);
00741 #ifndef NDEBUG
00742   markowitz_enlargement_back_t me (e);
00743   int momr2= in_degree (source (e, cg), cg) - markowitz_enlargement_back (e, cg)
00744             - sum_over_all_in_edges (source (e, cg), cg, me);
00745   // assert (momr == momr2);
00746   THROW_DEBUG_EXCEPT_MACRO (momr2 != momr, consistency_exception, "momr not correct"); 
00747 
00748   c_graph_t         gtmp (cg);
00749   c_graph_t::vi_t   vi, v_end;
00750   int old_overall_markowitz= 0, new_overall_markowitz= 0;
00751   for (boost::tie (vi, v_end)= vertices (gtmp); vi != v_end; ++vi)
00752     old_overall_markowitz+= in_degree (*vi, gtmp) * out_degree (*vi, gtmp);
00753 
00754   // eliminating e in gtmp does not work -> edge_descriptor from gtmp needed
00755   c_graph_t::edge_t   etmp;
00756   c_graph_t::ei_t     ei, e_end;
00757   c_graph_t::vertex_t s= source (e, cg), t= target (e, cg);
00758   for (boost::tie (ei, e_end)= edges (gtmp); ei != e_end; ++ei)
00759     if (source (*ei, gtmp) == s && target (*ei, gtmp) == t) {
00760       etmp= *ei; break; }
00761   // assert (ei != e_end); // otherwise edge not found
00762   THROW_DEBUG_EXCEPT_MACRO (ei == e_end, consistency_exception, "No matching edge found"); 
00763 
00764   back_edge_elimination (etmp, gtmp);
00765   for (boost::tie (vi, v_end)= vertices (gtmp); vi != v_end; ++vi)
00766     new_overall_markowitz+= in_degree (*vi, gtmp) * out_degree (*vi, gtmp);
00767   // assert (old_overall_markowitz-new_overall_markowitz == momr);
00768   THROW_DEBUG_EXCEPT_MACRO (old_overall_markowitz-new_overall_markowitz != momr, 
00769                          consistency_exception, "momr not correct"); 
00770 #endif
00771   return momr;
00772 }
00773 
00774 // operator for MOMR on edges
00775 struct momre_op_t {
00776   int operator() (bool front, c_graph_t::edge_t edge, const c_graph_t& cg) {
00777     return front ? momr_edge_front (edge, cg) : momr_edge_back (edge, cg); }
00778   int operator() (edge_bool_t eb, const c_graph_t& cg) {
00779     return eb.second ? momr_edge_front (eb.first, cg) : momr_edge_back (eb.first, cg); }
00780 };
00781 
00782 int momr_edge_f (const vector<c_graph_t::edge_t>& ev1,
00783                  bool front,
00784                  const c_graph_t& cg,
00785                  vector<c_graph_t::edge_t>& ev2) {
00786   ev2.resize (0);
00787   if (ev1.size() == 0) return 0;
00788   momre_op_t momre_op;
00789   int max_momr= momre_op (front, ev1[0], cg);
00790   ev2.push_back (ev1[0]);
00791 
00792   for (size_t c= 1; c < ev1.size(); c++) {
00793     int momr= momre_op (front, ev1[c], cg); 
00794     if (momr > max_momr) ev2.resize (0);
00795     if (momr >= max_momr) {
00796       ev2.push_back (ev1[c]); max_momr= momr;}
00797   }
00798   return ev2.size();
00799 }
00800 
00801 int momr_edge_t::operator() (const vector<edge_bool_t>& ev1, const c_graph_t& cg,
00802                              vector<edge_bool_t>& ev2) {
00803   momre_op_t   momre_op;
00804   return standard_heuristic_op (ev1, cg, ev2, momre_op, *this);
00805 }
00806 
00807 momr_edge_t momr_edge;
00808 
00809 // -------------------------------------------------------------------------
00810 // Minimal distance 
00811 // -------------------------------------------------------------------------
00812 
00813 // operator for minimal distances on faces
00814 struct diste_op_t {
00815   int operator() (edge_bool_t eb, const c_graph_t& cg) {
00816     c_graph_t::vertex_t           i= source (eb.first, cg), j= target (eb.first, cg), dist= 0;
00817     vector<c_graph_t::vertex_t>   nb;
00818     if (eb.second) {
00819       successor_set (j, cg, nb);
00820       for (size_t c= 0; c < nb.size(); c++)
00821         if (nb[c] - i > dist) dist= nb[c] - i;
00822     } else {
00823       predecessor_set (j, cg, nb);
00824       for (size_t c= 0; c < nb.size(); c++)
00825         if (j - nb[c] > dist) dist= j - nb[c]; }
00826     THROW_DEBUG_EXCEPT_MACRO (dist <= 0, consistency_exception, "Wrong distance in edge elimination");
00827     return dist; }
00828 };
00829 
00830 int minimal_distance_edge_t::operator() (const vector<edge_bool_t>& ev1, const c_graph_t& cg,
00831                                          vector<edge_bool_t>& ev2) {
00832   return standard_heuristic_op (ev1, cg, ev2, diste_op_t(), *this);
00833 }
00834 
00835 minimal_distance_edge_t minimal_distance_edge;
00836 
00837 // -------------------------------------------------------------------------
00838 // Maximal overall path length reduction
00839 // -------------------------------------------------------------------------
00840 
00841 int moplr_edge (const vector<c_graph_t::edge_t>& ev1,
00842                 bool front,
00843                 const c_graph_t& cg,
00844                 vector<c_graph_t::edge_t>& ev2) {
00845   ev2.resize (0);
00846   if (ev1.size() == 0) return 0;
00847 
00848   vector<int> vni, vli, vno, vlo;
00849   in_out_path_lengths (cg, vni, vli, vno, vlo);
00850 
00851   int max_oplr= front ? oplr_edge_front (ev1[0], vni, vli, vno, vlo, cg)
00852                       : oplr_edge_back (ev1[0], vni, vli, vno, vlo, cg);
00853   ev2.push_back (ev1[0]);
00854 
00855   for (size_t c= 1; c < ev1.size(); c++) {
00856     c_graph_t::edge_t e= ev1[c];
00857     int oplr= front ? oplr_edge_front (e, vni, vli, vno, vlo, cg)
00858                     : oplr_edge_back (e, vni, vli, vno, vlo, cg);
00859     if (oplr > max_oplr) ev2.resize (0);
00860     if (oplr >= max_oplr) {
00861       ev2.push_back (e); max_oplr= oplr;}
00862   }
00863 
00864   return ev2.size();
00865 }
00866 
00867 
00868 
00869 // =====================================================
00870 // for face elimination
00871 // =====================================================
00872 
00873 // objective function for forward and reverse mode in face elimination
00874 // works up to 165 thousands vertices in IEEE arithmetic
00875 inline double fmf_obj (line_graph_t::face_t f, const line_graph_t& lg) {
00876   int i, j, k, x= lg.x();
00877   face_vertex_name (f, lg, i, j, k);
00878   return ((double (j) * double (x)) + double (i)) * double (x) + double (k);
00879 }
00880 
00881 int forward_mode_face_t::operator() (const vector<line_graph_t::face_t>& fv1,
00882                                      const line_graph_t& lg,
00883                                      vector<line_graph_t::face_t>& fv2) {
00884   fv2.resize (0);
00885   if (fv1.size() == 0) {set_empty_objective (); return 0; }
00886   fv2.push_back (fv1[0]);
00887 
00888   for (size_t c= 1; c < fv1.size(); c++) {
00889 //    THROW_DEBUG_EXCEPT_MACRO (fmf_obj (fv1[c], lg) < fmf_obj (fv2[0], lg) != lex_less_face (fv1[c], fv2[0], lg),
00890 //                         consistency_exception, "objective function and comparator does not match");
00891     if (lex_less_face (fv1[c], fv2[0], lg)) fv2[0]= fv1[c]; }
00892   set_objective (fmf_obj (fv2[0], lg));
00893   return 1;
00894 }
00895 
00896 forward_mode_face_t forward_mode_face;
00897 
00898 // -------------------------------------------------------------------------
00899 // reverse mode
00900 // -------------------------------------------------------------------------
00901 
00902 int reverse_mode_face_t::operator() (const vector<line_graph_t::face_t>& fv1,
00903                                      const line_graph_t& lg,
00904                                      vector<line_graph_t::face_t>& fv2) {
00905   fv2.resize (0);
00906   if (fv1.size() == 0) {set_empty_objective (); return 0; }
00907   fv2.push_back (fv1[0]);
00908 
00909   for (size_t c= 1; c < fv1.size(); c++) {
00910 //    THROW_DEBUG_EXCEPT_MACRO (fmf_obj (fv1[c], lg) < fmf_obj (fv2[0], lg) != lex_less_face (fv1[c], fv2[0], lg),
00911 //                         consistency_exception, "objective function and comparator does not match");
00912     if (!lex_less_face (fv1[c], fv2[0], lg)) fv2[0]= fv1[c]; }
00913   set_objective (fmf_obj (fv2[0], lg));
00914   return 1;
00915 }
00916 
00917 reverse_mode_face_t reverse_mode_face;
00918 
00919 int reverse_mode_face_whole_vertex_t::operator() (const vector<line_graph_t::face_t>& fv1,
00920                                                   const line_graph_t& lg,
00921                                                   vector<line_graph_t::face_t>& fv2) {
00922   fv2.resize (0);
00923   if (fv1.size() == 0) return 0;
00924   fv2.push_back (fv1[0]);
00925   line_graph_t::const_evn_t evn= get(boost::vertex_name, lg);
00926 
00927   int maxv= evn[source(fv1[0], lg)].second;
00928 
00929   for (size_t c= 1; c < fv1.size(); c++) {
00930     line_graph_t::face_t f= fv1[c];
00931     int v= evn[source(f, lg)].second;
00932     if (v > maxv) {fv2.resize (0); maxv= v;}
00933     if (v == maxv) fv2.push_back (f); }
00934 
00935   return fv2.size();
00936 }
00937 
00938 reverse_mode_face_whole_vertex_t reverse_mode_face_whole_vertex;
00939 
00940 // -------------------------------------------------------------------------
00941 // subroutine of Lowest Markowitz on line graph
00942 // -------------------------------------------------------------------------
00943 
00944 void markowitz_on_line_graph (const line_graph_t& lg,
00945                               vector<int>& mdegree) {
00946 
00947   line_graph_t::const_evn_t   evn= get(vertex_name, lg);
00948   int                         max_vertex_cg= 0;
00949   line_graph_t::ei_t          ei, e_end;
00950   for (boost::tie (ei, e_end)= vertices (lg); ei != e_end; ++ei)
00951     if (max_vertex_cg < evn[*ei].second) max_vertex_cg= evn[*ei].second;
00952     
00953   // number of faces in which vertex j occurs in the center
00954   // filter out independent and dependent vertices (i,i,k) or (i,k,k)
00955   mdegree.resize (0); mdegree.resize (max_vertex_cg+1);
00956   line_graph_t::fi_t          fi, f_end;
00957   for (boost::tie (fi, f_end)= edges (lg); fi != f_end; ++fi) {
00958     line_graph_t::edge_t s= source (*fi, lg), t= target (*fi, lg);
00959     if (evn[s].first != evn[s].second && evn[t].first != evn[t].second)
00960         mdegree[evn[s].second]++; }
00961 }
00962 
00963 
00964 
00965 // -------------------------------------------------------------------------
00966 // Lowest Markowitz
00967 // -------------------------------------------------------------------------
00968 
00969 // operator for lowest Markowitz on faces
00970 struct lmf_op_t {
00971   vector<int> mdegree;
00972   lmf_op_t (const line_graph_t& lg) {
00973     markowitz_on_line_graph (lg, mdegree); }
00974   int operator() (line_graph_t::face_t f, const line_graph_t& lg) {
00975     int i, j, k; face_vertex_name (f, lg, i, j, k);
00976     THROW_DEBUG_EXCEPT_MACRO (mdegree[j] == 0, consistency_exception, "Un-eliminatable face in fv1"); 
00977     return mdegree[j]; }
00978 };
00979 
00980 int lowest_markowitz_face_t::operator() (const vector<line_graph_t::face_t>& fv1,
00981                                          const line_graph_t& lg,
00982                                          vector<line_graph_t::face_t>& fv2) {
00983   lmf_op_t      lmf_op (lg);
00984   return standard_heuristic_op (fv1, lg, fv2, lmf_op, *this);
00985 }
00986 
00987 
00988 // -------------------------------------------------------------------------
00989 // MOMR
00990 // -------------------------------------------------------------------------
00991 
00992 // will a face (p,i,k) from (i,j)'s predecessor (p,i) to (i,k) be inserted ?
00993 // or does it already exist
00994 class new_pik_t {
00995   int i, k;
00996 public:
00997   new_pik_t (int _i, int _k) : i (_i), k (_k) {}
00998   int operator() (line_graph_t::face_t pij, const line_graph_t& lg) const {
00999     line_graph_t::edge_t pi= source (pij, lg);
01000     // for independent edges, new faces doesn't affect Mark. -> stop
01001     if (vertex_type (pi, lg) == independent) return 0; 
01002     line_graph_t::ofi_t ofi, of_end;
01003     for (tie (ofi, of_end)= out_edges (pi, lg); ofi != of_end; ++ofi) {
01004       int v1, v2;
01005       edge_vertex_name (target (*ofi, lg), lg, v1, v2); 
01006       // assert (v1 == i);
01007       THROW_DEBUG_EXCEPT_MACRO (v1 != i, consistency_exception, "Adjacency corrupted in line graph"); 
01008       if (v2 == k) return 0; } // (p,i,k) found
01009     return 1;
01010   }
01011 };
01012 
01013 struct source_not_independent_t {
01014   int operator() (line_graph_t::face_t f, const line_graph_t& lg) const {
01015     return (vertex_type (source (f, lg), lg) != independent); }
01016 };
01017 
01018 // will a face (i,k,s) to (j,k)'s successor (k,s) from (i,k) be inserted ?
01019 // or does it already exist
01020 class new_iks_t {
01021   int i, k;
01022 public:
01023   new_iks_t (int _i, int _k) : i (_i), k (_k) {}
01024   int operator() (line_graph_t::face_t jks, const line_graph_t& lg) const {
01025     line_graph_t::edge_t ks= target (jks, lg);
01026     // for dependent edges, new faces doesn't affect Mark. -> stop
01027     if (vertex_type (ks, lg) == dependent) return 0; 
01028     line_graph_t::ifi_t ifi, if_end;
01029     for (tie (ifi, if_end)= in_edges (ks, lg); ifi != if_end; ++ifi) {
01030       int v1, v2;
01031       edge_vertex_name (source (*ifi, lg), lg, v1, v2);
01032       // assert (v2 == k);
01033       THROW_DEBUG_EXCEPT_MACRO (v2 != k, consistency_exception, "Adjacency corrupted in line graph"); 
01034       if (v1 == i) return 0; } // (i,k,s) found
01035     return 1;
01036   }
01037 };
01038 
01039 struct target_not_dependent_t {
01040   int operator() (line_graph_t::face_t f, const line_graph_t& lg) const {
01041     return (vertex_type (target (f, lg), lg) != dependent); }
01042 };
01043 
01044 // operator for MOMR on faces
01045 struct momrf_op_t {
01046   int operator() (line_graph_t::face_t f, const line_graph_t& lg) {
01047     int momr= 1; // the face itself
01048     int i, j, k; // f's vertices w.r.t. c-graph
01049     face_vertex_name (f, lg, i, j, k);
01050     line_graph_t::edge_t ij= source (f, lg), jk= target (f, lg);
01051 
01052     new_pik_t new_pik (i, k);
01053     momr-= sum_over_all_in_edges (ij, lg, new_pik);
01054     if (out_degree (ij, lg) == 1) 
01055       momr+= sum_over_all_in_edges (ij, lg, source_not_independent_t());
01056 
01057     new_iks_t new_iks (i, k);
01058     momr-= sum_over_all_out_edges (jk, lg, new_iks);
01059     if (in_degree (jk, lg) == 1) 
01060       momr+= sum_over_all_out_edges (jk, lg, target_not_dependent_t());
01061 #ifndef NDEBUG
01062     line_graph_t         gtmp (lg);
01063 
01064     // eliminating f in gtmp does not work -> edge_descriptor from gtmp needed
01065     line_graph_t::face_t   ftmp;
01066     ftmp= *same_edge (f, lg, gtmp);
01067     face_elimination (ftmp, gtmp);
01068 
01069     int old_overall_markowitz= overall_markowitz_degree (lg);
01070     int new_overall_markowitz= overall_markowitz_degree (gtmp);
01071     if (old_overall_markowitz - new_overall_markowitz != momr) {
01072       write_graph ("AD edge before elimination", lg);
01073       line_graph_t::const_evn_t                 evn= get(vertex_name, lg);
01074       write_vertex_property (cout, "vertices of this edge graph", evn, lg);
01075       cout << "overall_markowitz_degree is " << old_overall_markowitz << "\n"; 
01076       cout << "elimination of face: ";
01077       write_face_op_t wf (gtmp); wf (cout, ftmp); 
01078       cout << endl;
01079       write_graph ("AD edge after elimination", gtmp);
01080       line_graph_t::evn_t                 evntmp= get(vertex_name, gtmp);
01081       write_vertex_property (cout, "vertices of this edge graph", evntmp, lg);
01082       cout << "overall_markowitz_degree is " << new_overall_markowitz 
01083            << " momr is " << momr << "\n"; 
01084       line_graph_t         gtmp2 (lg);
01085       ftmp= *same_edge (f, lg, gtmp2);
01086       face_elimination (ftmp, gtmp2);
01087     }
01088     // assert (overall_markowitz_degree (lg) - overall_markowitz_degree (gtmp) == momr);
01089     THROW_DEBUG_EXCEPT_MACRO (overall_markowitz_degree (lg) - overall_markowitz_degree (gtmp) != momr, 
01090                            consistency_exception, "momr not correct"); 
01091 #endif
01092     return momr; }
01093 };
01094 
01095 int momr_face_t::operator() (const vector<line_graph_t::face_t>& fv1,
01096                              const line_graph_t& lg,
01097                              vector<line_graph_t::face_t>& fv2) {
01098   momrf_op_t   momrf_op;
01099   return standard_heuristic_op (fv1, lg, fv2, momrf_op, *this);
01100 }
01101 
01102 momr_face_t momr_face;
01103 
01104 // -------------------------------------------------------------------------
01105 // Minimal distance 
01106 // -------------------------------------------------------------------------
01107 
01108 // operator for minimal distances on faces
01109 struct distf_op_t {
01110   int operator() (line_graph_t::face_t f, const line_graph_t& lg) {
01111     int i, j, k; face_vertex_name (f, lg, i, j, k);
01112     return k - i; }
01113 };
01114 
01115 int minimal_distance_face_t::operator() (const vector<line_graph_t::face_t>& fv1,
01116                                          const line_graph_t& lg, vector<line_graph_t::face_t>& fv2) {
01117   return standard_heuristic_op (fv1, lg, fv2, distf_op_t(), *this);
01118 }
01119 
01120 #ifdef USEXAIFBOOSTER
01121 
01122 // -------------------------------------------------------------------------
01123 // Scarcity preserving edge eliminations
01124 // -------------------------------------------------------------------------
01125 int edge_elim_effect (const edge_bool_t be,
01126                       const c_graph_t& angelLCG,
01127                       const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) {
01128   
01129   boost::property_map<c_graph_t, EdgeType>::const_type eType = get(EdgeType(), angelLCG);
01130   c_graph_t::oei_t oei, oe_end;
01131   c_graph_t::iei_t iei, ie_end;
01132   c_graph_t::edge_t absorb_e;
01133   bool found_absorb;
01134 
01135   c_graph_t::edge_t e = be.first;
01136   bool isFront = be.second;
01137   int nontrivialEdgeChange = 0;
01138 
01139   // No awareness: removal of e decreases edge count
01140   if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange--;
01141   // unit awareness: e must be nonunit for its removal to decrease nontrivial edges
01142   else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[e] != UNIT_EDGE) nontrivialEdgeChange--;
01143   // constant awareness: e must be variable for its removal to decrease nontrivial edges
01144   else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[e] == VARIABLE_EDGE) nontrivialEdgeChange--;
01145 
01146   if (isFront) { // front-elimination
01147     // if tgt(e) is isolated by the elimination
01148     if (in_degree (target (e, angelLCG), angelLCG) == 1) {
01149       for (tie (oei, oe_end) = out_edges (target (e, angelLCG), angelLCG); oei != oe_end; ++oei) {
01150         // all the outedges of tgt(e) will go away.  we need to see how this affects nontrivial edge count
01151         if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange--;
01152         else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*oei] != UNIT_EDGE) nontrivialEdgeChange--;
01153         else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*oei] == VARIABLE_EDGE) nontrivialEdgeChange--;
01154       } // end all outedges of tgt(e)
01155     }
01156 
01157     // determine effect of absorption/fill-in
01158     for (tie (oei, oe_end) = out_edges (target (e, angelLCG), angelLCG); oei != oe_end; ++oei) {
01159       tie (absorb_e, found_absorb) = edge (source (e, angelLCG), target (*oei, angelLCG), angelLCG);
01160       if (found_absorb) { // absorption
01161         //no awareness: no increase in edge count
01162         //unit awareness: absorb_e will be nonunit afterwards.  increase only if absorb_e was previously unit 
01163         if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange++;
01164         // constant awareness: increase if absorb edge is nonvariable and either e or *oei is variable
01165         else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
01166           if (eType[e] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE) nontrivialEdgeChange++;
01167       }
01168       else { // fill-in
01169         if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange++;
01170         // unit awareness: if either is nonunit, the fill-in is nonunit
01171         else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[e] != UNIT_EDGE || eType[*oei] != UNIT_EDGE)) nontrivialEdgeChange++;
01172         // constant awareness: if either is variable, the fill-in is variable
01173         else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[e] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE)) nontrivialEdgeChange++;
01174       }
01175     } // end all successors of tgt(e)
01176 
01177   } // end front-elimination
01178   else { // back-elimination
01179 
01180     // consider in-edges lost due to isolating src(e) (requires src(e) is not dependent)
01181     if (out_degree (source (e, angelLCG), angelLCG) == 1 && vertex_type (source (e, angelLCG), angelLCG) != dependent) {
01182       for (tie (iei, ie_end) = in_edges (source (e, angelLCG), angelLCG); iei != ie_end; ++iei) {
01183         if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange--;
01184         else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*iei] != UNIT_EDGE) nontrivialEdgeChange--;
01185         else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*iei] == VARIABLE_EDGE) nontrivialEdgeChange--;
01186       } // end all inedges of src(e)
01187     }
01188               
01189     // determine effect of absorption/fill-in
01190     for (tie (iei, ie_end) = in_edges (source (e, angelLCG), angelLCG); iei != ie_end; ++iei) {
01191       tie (absorb_e, found_absorb) = edge (source (*iei, angelLCG), target (e, angelLCG), angelLCG);
01192       if (found_absorb) { // absorption
01193         //no awareness: no increase in edge count
01194         //unit awareness: absorb_e will be nonunit afterwards.  increase only if absorb_e was previously unit
01195         if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE) nontrivialEdgeChange++;
01196         // constant awareness: increase if absorb edge is nonvariable and either e or *oei is variable
01197         else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
01198           if (eType[e] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE) nontrivialEdgeChange++;
01199       }
01200       else { // fill-in
01201         if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) nontrivialEdgeChange++;
01202          // unit awareness: if either is nonunit, the fill-in is nonunit
01203         else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[e] != UNIT_EDGE || eType[*iei] != UNIT_EDGE)) nontrivialEdgeChange++;
01204         // constant awareness: if either is variable, the fill-in is variable
01205         else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[e] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)) nontrivialEdgeChange++;
01206       }
01207     } // end all predecessors of src(e)
01208   } // end back-elimination
01209 
01210   return nontrivialEdgeChange;
01211 }
01212 
01213 int edge_elim_effect(const EdgeElim ee,
01214                      const c_graph_t& angelLCG,
01215                      const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) {
01216   return edge_elim_effect(make_pair(ee.getE(angelLCG), ee.isFront()), angelLCG, ourAwarenessLevel);
01217 } // end edge_elim_effect()
01218 
01219 bool maintaining_edge_eliminations(const vector<EdgeElim>& bev1,
01220                                    const c_graph_t& angelLCG,
01221                                    const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01222                                    vector<EdgeElim>& bev2) {
01223   bev2.clear();
01224   if (bev1.empty()) return 0;
01225 
01226   for (size_t c = 0; c < bev1.size(); c++)
01227     if (edge_elim_effect (bev1[c], angelLCG, ourAwarenessLevel) <= 0)
01228       bev2.push_back (bev1[c]);
01229 
01230 #ifndef NDEBUG
01231   cout << "     Of " << bev1.size() << " edge eliminations passed to maintaining_edge_eliminations(), " << bev2.size() << " maintain the nontrivial edge count" << endl;
01232 #endif
01233 
01234   if (bev2.empty()) {
01235     bev2 = bev1;
01236     return false;
01237   }
01238   else return true;
01239 } // end count_maintain_edge_eliminations()
01240 
01241 bool reducing_edge_eliminations(const vector<EdgeElim>& bev1,
01242                                 const c_graph_t& angelLCG,
01243                                 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01244                                 vector<EdgeElim>& bev2) {
01245   bev2.clear();
01246   if (bev1.empty()) return 0;
01247 
01248   for (size_t c = 0; c < bev1.size(); c++)
01249     if (edge_elim_effect (bev1[c], angelLCG, ourAwarenessLevel) < 0)
01250       bev2.push_back (bev1[c]);
01251 
01252   #ifndef NDEBUG
01253   cout << "     Of " << bev1.size() << " edge eliminations passed to reducing_edge_eliminations()"
01254        << ", " << bev2.size() << " reduce the nontrivial edge count" << endl;
01255   #endif
01256 
01257   if(bev2.empty()) {
01258     bev2 = bev1;
01259     return false;
01260   }
01261   else return true;
01262 } // end count_maintain_edge_eliminations()
01263 
01264 bool refill_avoiding_edge_eliminations(const vector<EdgeElim>& bev1,
01265                                        c_graph_t& angelLCG,
01266                                        const refillDependenceMap_t refillDependences,
01267                                        vector<EdgeElim>& bev2) {
01268   bev2.clear();
01269   if (bev1.empty())
01270     return 0;
01271 
01272   c_graph_t::iei_t iei, ie_end;
01273   c_graph_t::oei_t oei, oe_end;
01274   refillDependenceMap_t::const_iterator depMap_i;
01275   vertex_set_t::const_iterator vDepSet_i;
01276   property_map<pure_c_graph_t, VertexVisited>::type visited = get(VertexVisited(), angelLCG);
01277   c_graph_t::vi_t cleari, clear_end;
01278 
01279   for (size_t c = 0; c < bev1.size(); c++) {
01280     c_graph_t::edge_t e = bev1[c].getE(angelLCG); // the direction of elimination (front/back) doesn't matter
01281 
01282     depMap_i = refillDependences.find(make_pair(source (e, angelLCG), target(e, angelLCG)));
01283     if (depMap_i != refillDependences.end()) { // we have refill dependences to consider for e
01284 #ifndef NDEBUG
01285       cout << "edge " << e << " has some refill dependences. Checking them..." << endl;
01286 #endif
01287       vertex_set_t vDepSet = depMap_i->second; // extract the vertex dependence set for e
01288 
01289       // check all vertices that this edge depends on
01290       // the dependence vertex can't be both below tgt(e) and above src(e)
01291       for (vDepSet_i = vDepSet.begin(); vDepSet_i != vDepSet.end(); vDepSet_i++) {
01292         // clear visited property for all vertices
01293         for (tie(cleari, clear_end) = vertices(angelLCG); cleari != clear_end; ++cleari) visited[*cleari] = false;
01294         if (reachable (source (e, angelLCG), *vDepSet_i, angelLCG)) {
01295           // clear visited property for all vertices (again)
01296           for (tie(cleari, clear_end) = vertices(angelLCG); cleari != clear_end; ++cleari) visited[*cleari] = false;
01297           if (reachable (*vDepSet_i, target (e, angelLCG), angelLCG)) {
01298 #ifndef NDEBUG
01299             cout << "edge " << e << " has an unmet refill dependence on vertex " << *vDepSet_i << endl;
01300 #endif
01301             break;
01302           } // end if vertex dependency is not met
01303         }
01304       } // end all vertex dependences
01305 
01306       // all vertex dependences for this edge have been met
01307       if (vDepSet_i == vDepSet.end())
01308         bev2.push_back(bev1[c]);
01309     } // end if vertex dependences exist
01310     else bev2.push_back(bev1[c]);
01311 
01312   } // end iterate over bev1
01313 
01314 #ifndef NDEBUG
01315   cout << "     Of " << bev1.size() << " edge eliminations passed to refill_avoiding_edge_eliminations(), " << bev2.size() << " don't violate refill dependences" << endl;
01316 #endif
01317 
01318   if (bev2.empty()) {
01319     bev2 = bev1;
01320     return false;
01321   }
01322   else return true;
01323 } // end refill_avoiding_edge_eliminations()
01324 
01325 bool rerouting_considerate_edge_eliminations(const vector<EdgeElim>& bev,
01326                                              const c_graph_t& angelLCG,
01327                                              const std::vector<Transformation>& transformationsPerformedV,
01328                                              vector<EdgeElim>& reroutingConsiderateEdgeElimsV) {
01329   reroutingConsiderateEdgeElimsV.clear();
01330   if (bev.empty())
01331     return false;
01332 
01333   // Check every for every possible edge elimination
01334   for (size_t i = 0; i < bev.size(); i++) {
01335     size_t j;
01336 
01337     if (bev[i].isFront()) { // front-elimination
01338       // check all previously performed reroutings to see if the edge elim undoes it
01339       for (j = 0; j < transformationsPerformedV.size(); j++) {
01340         if (transformationsPerformedV[j].isRerouting()
01341          && transformationsPerformedV[j].getRerouting().isPre()
01342          && source(transformationsPerformedV[j].getRerouting().getE(angelLCG), angelLCG) == bev[i].getSource()
01343          && source(transformationsPerformedV[j].getRerouting().getPivotE(angelLCG), angelLCG) == bev[i].getTarget())
01344             break;
01345       }
01346     } // end front-elimination
01347 
01348     else { // back-elimination
01349       for (j = 0; j < transformationsPerformedV.size(); j++) {
01350         if (transformationsPerformedV[j].isRerouting()
01351          && !transformationsPerformedV[j].getRerouting().isPre()
01352          && target(transformationsPerformedV[j].getRerouting().getE(angelLCG), angelLCG) == bev[i].getTarget()
01353          && target(transformationsPerformedV[j].getRerouting().getPivotE(angelLCG), angelLCG) == bev[i].getSource())
01354             break;
01355       } // end all transformations
01356     } // end back-elimination
01357 
01358     if (j == transformationsPerformedV.size())
01359       reroutingConsiderateEdgeElimsV.push_back(bev[i]);
01360   } // end iterate over bev
01361 
01362 #ifndef NDEBUG
01363   cout << "     Of " << bev.size() << " edge eliminations passed to rerouting_considerate_edge_eliminations(), " << reroutingConsiderateEdgeElimsV.size() << " don't undo a rerouting" << endl;
01364 #endif
01365 
01366   if (reroutingConsiderateEdgeElimsV.empty()) {
01367     reroutingConsiderateEdgeElimsV = bev;
01368     return false;
01369   }
01370   else return true;
01371 } // end rerouting_considerate_edge_eliminations()
01372 
01373 unsigned int lowestMarkowitzEdgeElim(const vector<EdgeElim>& inEEV,
01374                                      const c_graph_t& angelLCG,
01375                                      vector<EdgeElim>& outEEV) {
01376   outEEV.clear();
01377   if (inEEV.empty())
01378     return 0;
01379 
01380   vector<edge_bool_t> inBEV, outBEV;
01381 
01382   for (size_t i = 0; i < inEEV.size(); i++)
01383     inBEV.push_back(inEEV[i].getBool(angelLCG));
01384 
01385   lowest_markowitz_edge(inBEV, angelLCG, outBEV);
01386 
01387   for (size_t i = 0; i < outBEV.size(); i++)
01388     outEEV.push_back(EdgeElim (outBEV[i], angelLCG));
01389 
01390   return outEEV.size();
01391 } // end lowestMarkowitzEdgeElim()
01392 
01393 bool reverseModeEdgeElim(const vector<EdgeElim>& inEEV,
01394                          const c_graph_t& angelLCG,
01395                          vector<EdgeElim>& outEEV) {
01396   outEEV.clear();
01397   if (inEEV.empty())
01398     return false;
01399 
01400   vector<edge_bool_t> inBEV, outBEV;
01401 
01402   for (size_t i = 0; i < inEEV.size(); i++)
01403     inBEV.push_back(inEEV[i].getBool(angelLCG));
01404 
01405   reverse_mode_edge(inBEV, angelLCG, outBEV);
01406 
01407   for (size_t i = 0; i < outBEV.size(); i++)
01408     outEEV.push_back(EdgeElim (outBEV[i], angelLCG));
01409 
01410   return true;
01411 } // end reverseModeEdgeElim()
01412 
01413 // ==============================================================================
01414 // |                    FILTERS FOR REROUTINGS                                  |
01415 // ==============================================================================
01416 
01417 size_t noncyclicReroutings (const vector<Rerouting>& erv,
01418                             const std::vector<Transformation>& transformationsPerformedV,
01419                             const c_graph_t& angelLCG,
01420                             vector<Rerouting>& noncyclicReroutingsV) {
01421   noncyclicReroutingsV.clear();
01422   if (erv.empty())
01423     return 0;
01424   size_t j;
01425   // check each rerouting in erv to see whether it has already been performed
01426   for (size_t i = 0; i < erv.size(); i++) {
01427     // go through the history 
01428     for (j = 0; j < transformationsPerformedV.size(); j++)
01429       if (transformationsPerformedV[j].isRerouting()
01430        && transformationsPerformedV[j].getRerouting() == erv[i]);
01431           break;
01432     if (j == transformationsPerformedV.size()) // if it made it all the way through, the rerouting hasn't already been performed
01433       noncyclicReroutingsV.push_back(erv[i]);
01434   } // end iterate over erv
01435   return noncyclicReroutingsV.size();
01436 } // end noncyclicReroutings()
01437 
01438 /*
01439 bool maintaining_reroutings (const vector<edge_reroute_t>& erv,
01440                              const c_graph_t& angelLCG,
01441                              const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01442                              vector<edge_reroute_t>& maintainingReroutingsV) {
01443   maintainingReroutingsV.clear();
01444   if (erv.empty()) return 0;
01445 
01446   bool dummyBool;
01447 
01448   for (size_t i = 0; i < erv.size(); i++) {
01449     cout << "reroute_effect = " << reroute_effect(erv[i], angelLCG, ourAwarenessLevel, dummyBool) << endl;
01450     if (reroute_effect(erv[i], angelLCG, ourAwarenessLevel, dummyBool) <= 0)
01451       maintainingReroutingsV.push_back(erv[i]);
01452   }
01453   cout << "Of " << erv.size() << " reroutings passed to maintaining_reroutings(), " << maintainingReroutingsV.size() << " maintain the nontrivial edge count" << endl;
01454 
01455   if (maintainingReroutingsV.empty()) {
01456     maintainingReroutingsV = erv;
01457     return false;
01458   }
01459   else return true;
01460 } // end maintaining_reroutings()
01461 */
01462 
01463 /*
01464 bool reducing_reroutings (const vector<edge_reroute_t>& erv,
01465                           const c_graph_t& angelLCG,
01466                           const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01467                           vector<edge_reroute_t>& reducingReroutingsV) {
01468   reducingReroutingsV.clear();
01469   if (erv.empty()) return 0;
01470   size_t i;
01471 
01472   vector<edge_reroute_t> reducingReroutingstypes12V, reducingReroutingstype3V;
01473 
01474   if (edge_reducing_rerouteElims_types12 (erv, angelLCG, ourAwarenessLevel, false, reducingReroutingstypes12V))
01475     for (i = 0; i < reducingReroutingstypes12V.size(); i++)
01476       reducingReroutingsV.push_back(reducingReroutingstypes12V[i]);
01477 
01478   if (edge_reducing_rerouteElims_type3 (erv, angelLCG, ourAwarenessLevel, false, reducingReroutingstype3V))
01479     for (i = 0; i < reducingReroutingstype3V.size(); i++)
01480       reducingReroutingsV.push_back(reducingReroutingstype3V[i]);
01481 #ifndef NDEBUG
01482   cout << "     Of " << erv.size() << " reroutings passed to reducing_reroutings(), " << reducingReroutingsV.size() << " reduce the nontrivial edge count when followed by elimination" << endl;
01483 #endif
01484   if (reducingReroutingsV.empty()) {
01485     //reducingReroutingsV = erv;
01486     return false;
01487   }
01488   else return true;
01489 } // end reducing_reroutings()
01490 */
01491 
01492 bool reducing_reroutings (const vector<Rerouting>& erv,
01493                           const c_graph_t& angelLCG,
01494                           const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01495                           vector<Rerouting>& reducingReroutingsV) {
01496   reducingReroutingsV.clear();
01497   if (erv.empty())
01498     return 0;
01499 
01500   boost::property_map<c_graph_t, EdgeType>::const_type eType = get(EdgeType(), angelLCG);
01501   c_graph_t::iei_t iei, ie_end;
01502   c_graph_t::oei_t oei, oe_end;
01503   c_graph_t::edge_t absorb_e, increment_absorb_e, decrement_absorb_e;
01504   bool found_absorb_e;
01505 
01506   for (size_t i = 0; i < erv.size(); i++) {
01507     edge_reroute_t er = erv[i].getER(angelLCG);
01508     // first record effect of the rerouting itself
01509     bool incrementIsTrivial;
01510     int nontrivialEdgeChange_rerouting = reroute_effect (er, angelLCG, ourAwarenessLevel, incrementIsTrivial);
01511 
01512     c_graph_t::edge_t e = er.e;
01513     c_graph_t::edge_t pe = er.pivot_e;
01514     er.pivot_eliminatable = false;
01515     er.increment_eliminatable = false;
01516     er.type3EdgeElimVector.clear();
01517 
01518     int nontrivialEdgeChange_elimIncrement = 0;
01519     int nontrivialEdgeChange_elimPivot = 0;
01520 
01521     if (er.isPre) { // pre-routing
01522       //---------------------------------------------------------------------------------------------------------------------------
01523       // determine effect of back-eliminating the increment edge on the nontrivial edge count (nontrivialEdgeChange_elimIncrement)
01524       //---------------------------------------------------------------------------------------------------------------------------
01525 
01526       // cannot back-eliminate the increment edge if src(e) is an independent
01527       if (in_degree (source (e, angelLCG), angelLCG) > 0) {
01528         // determine effect of removing the increment edge
01529         if (!incrementIsTrivial) nontrivialEdgeChange_elimIncrement--;
01530 
01531         // examine effect of back-eliminating increment edge
01532         for (tie(iei, ie_end) = in_edges(source(e, angelLCG), angelLCG); iei != ie_end; ++iei) {
01533           tie(absorb_e, found_absorb_e) = edge(source(*iei, angelLCG), source(pe, angelLCG), angelLCG);
01534           if (found_absorb_e) { // absorption: count when the absorb_e goes from trivial to nontrivial
01535             if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE)            nontrivialEdgeChange_elimIncrement++;
01536             else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
01537               if (eType[*iei] == VARIABLE_EDGE || !incrementIsTrivial)                                          nontrivialEdgeChange_elimIncrement++;
01538           } // end absorption
01539           else { // fill-in: is the fill-in trivial or not?
01540             if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS)                                                                              nontrivialEdgeChange_elimIncrement++;
01541             else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[*iei] != UNIT_EDGE || !incrementIsTrivial))          nontrivialEdgeChange_elimIncrement++;
01542             else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[*iei] == VARIABLE_EDGE || !incrementIsTrivial))  nontrivialEdgeChange_elimIncrement++;
01543           } // end fill-in
01544         } // end all preds of src(e)
01545         if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_elimIncrement < 0) er.increment_eliminatable = true;
01546       } // end if increment edge can be back-eliminated
01547       
01548       //------------------------------------------------------------------------------------------------------------------------------------------------
01549       // determine effect of front-eliminating the pivot edge on the nontrivial edge count (nontrivialEdgeChange_elimPivot)
01550       //------------------------------------------------------------------------------------------------------------------------------------------------
01551 
01552       // front-elimination of pivot edge MUST isolate the target
01553       if (in_degree(target(pe, angelLCG), angelLCG) == 2 && vertex_type(target(pe, angelLCG), angelLCG) != dependent) {
01554 
01555         // determine effect of eliminating the pivot edge
01556         if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS)                                          nontrivialEdgeChange_elimPivot--;
01557         else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[pe] != UNIT_EDGE)         nontrivialEdgeChange_elimPivot--;
01558         else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[pe] == VARIABLE_EDGE) nontrivialEdgeChange_elimPivot--;
01559 
01560         // iterate over successors of tgt(pe); the fill/absorb edges will have the same source as the pivot edge
01561         for (tie (oei, oe_end) = out_edges(target(pe, angelLCG), angelLCG); oei != oe_end; ++oei) {
01562           // determine effect of removing *oei
01563           if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS)                                                        nontrivialEdgeChange_elimPivot--;
01564           else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*oei] != UNIT_EDGE)             nontrivialEdgeChange_elimPivot--;
01565           else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*oei] == VARIABLE_EDGE)     nontrivialEdgeChange_elimPivot--;
01566 
01567           tie (absorb_e, found_absorb_e) = edge (source(pe, angelLCG), target(*oei, angelLCG), angelLCG);
01568           if (found_absorb_e) { // absorption: we need to detect of it goes from trivial to nontrivial
01569             if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE)            nontrivialEdgeChange_elimPivot++;
01570             else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
01571               if (eType[pe] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE)                                   nontrivialEdgeChange_elimPivot++;
01572           } // end absorption case
01573           else { // fill-in
01574             if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS)                                                                                      nontrivialEdgeChange_elimPivot++;
01575             else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[pe] != UNIT_EDGE || eType[*oei] != UNIT_EDGE))                       nontrivialEdgeChange_elimPivot++;
01576             else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[pe] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE))   nontrivialEdgeChange_elimPivot++;
01577           } // end fill-in case
01578 
01579         } // end all successors of tgt(e)=tgt(pe)
01580         if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_elimPivot < 0) er.pivot_eliminatable = true;
01581       } // end determine nontrivialEdgeChange_elimPivot
01582 
01583       //------------------------------------------------------------------------------------------------------------------------------------------------
01584       // determine effect of back-eliminating (type 3) 
01585       //------------------------------------------------------------------------------------------------------------------------------------------------
01586 
01587       // iterate over outedges of tgt(e), consider back-elimination of *oei
01588       for (tie(oei, oe_end) = out_edges(target(e, angelLCG), angelLCG); oei != oe_end; ++oei) {
01589         int nontrivialEdgeChange_backElimination = 0;
01590 
01591         // consider loss of *oei
01592         if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS
01593         || (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*oei] != UNIT_EDGE)
01594         || (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*oei] == VARIABLE_EDGE)) nontrivialEdgeChange_backElimination--;
01595 
01596         // consider fill/absorb effect of back-eliminating *oei
01597         for (tie(iei, ie_end) = in_edges(target(e, angelLCG), angelLCG); iei != ie_end; ++iei) {
01598           if (*iei == e) continue; // skip the rerouted edge
01599           tie(absorb_e, found_absorb_e) = edge(source(*iei, angelLCG), target(*oei, angelLCG), angelLCG);
01600           if (found_absorb_e) { // absorption: only counts if it goes from trivial to nontrivial
01601             if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE)            nontrivialEdgeChange_backElimination++;
01602             else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
01603               if (eType[*oei] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)                                 nontrivialEdgeChange_backElimination++;
01604           }
01605           else { // fill-in
01606             if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS)                                                                                      nontrivialEdgeChange_backElimination++;
01607             else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[*oei] != UNIT_EDGE || eType[*iei] != UNIT_EDGE))             nontrivialEdgeChange_backElimination++;
01608             else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[*oei] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)) nontrivialEdgeChange_backElimination++;
01609           }
01610         } // end all inedges of tgt(e)
01611         if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_backElimination < 0) er.type3EdgeElimVector.push_back(target(*oei, angelLCG));
01612       } // end all outedges of tgt(e) (end type 3)
01613 
01614     } // end pre-routing
01615     else { // post-routing
01616 
01617       //------------------------------------------------------------------------------------------------------------------------------------------------
01618       // determine effect of front-eliminating the increment edge on the nontrivial edge count
01619       //------------------------------------------------------------------------------------------------------------------------------------------------
01620 
01621       // cannot front-eliminate the increment edge if tgt(e) is a dependent
01622       if (vertex_type(target(e, angelLCG), angelLCG) != dependent)  {
01623         // determine effect of removing the increment edge
01624         if (!incrementIsTrivial) nontrivialEdgeChange_elimIncrement--;
01625 
01626         // examine effect of front-eliminating increment edge
01627         for (tie (oei, oe_end) = out_edges(target(e, angelLCG), angelLCG); oei != oe_end; ++oei) {
01628           tie (absorb_e, found_absorb_e) = edge(target(pe, angelLCG), target(*oei, angelLCG), angelLCG);
01629           if (found_absorb_e) { // absorption: count when the absorb_e goes from trivial to nontrivial
01630             if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE)            nontrivialEdgeChange_elimIncrement++;
01631             else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
01632               if (eType[*oei] == VARIABLE_EDGE || !incrementIsTrivial)                                          nontrivialEdgeChange_elimIncrement++;
01633           } // end absorption
01634           else { // fill-in: is the fill-in trivial or not?
01635             if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS)                                                                              nontrivialEdgeChange_elimIncrement++;
01636             else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[*oei] != UNIT_EDGE || !incrementIsTrivial))          nontrivialEdgeChange_elimIncrement++;
01637             else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[*oei] == VARIABLE_EDGE || !incrementIsTrivial))  nontrivialEdgeChange_elimIncrement++;
01638           } // end fill-in
01639         } // end all preds of src(e)
01640         if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_elimIncrement < 0) er.increment_eliminatable = true;
01641       } // end if increment edge can be front-eliminated
01642 
01643       //------------------------------------------------------------------------------------------------------------------------------------------------
01644       // determine effect of back-eliminating the pivot edge on the nontrivial edge count
01645       //------------------------------------------------------------------------------------------------------------------------------------------------
01646 
01647       // front-elimination of pivot edge MUST isolate the target
01648       if (out_degree (source(pe, angelLCG), angelLCG) == 2 && in_degree (source(pe, angelLCG), angelLCG) > 0) {
01649 
01650         // determine effect of eliminating the pivot edge
01651         if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS)                                          nontrivialEdgeChange_elimPivot--;
01652         else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[pe] != UNIT_EDGE)         nontrivialEdgeChange_elimPivot--;
01653         else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[pe] == VARIABLE_EDGE) nontrivialEdgeChange_elimPivot--;
01654 
01655         // iterate over predecessors of src(pe)
01656         // the fill/absorb edges will have the same target as the pivot edge
01657         for (tie (iei, ie_end) = in_edges(source(pe, angelLCG), angelLCG); iei != ie_end; ++iei) {
01658           // determine effect of removing the outedge
01659           if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS)                                                        nontrivialEdgeChange_elimPivot--;
01660           else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*iei] != UNIT_EDGE)             nontrivialEdgeChange_elimPivot--;
01661           else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*iei] == VARIABLE_EDGE)     nontrivialEdgeChange_elimPivot--;
01662 
01663           tie (absorb_e, found_absorb_e) = edge (source(*iei, angelLCG), target(pe, angelLCG), angelLCG);
01664           if (found_absorb_e) { // absorption: we need to detect of it goes from trivial to nontrivial
01665             if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE)            nontrivialEdgeChange_elimPivot++;
01666             else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
01667               if (eType[pe] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)                                   nontrivialEdgeChange_elimPivot++;
01668           } // end absorption case
01669           else { // fill-in
01670             if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS)                                                                                      nontrivialEdgeChange_elimPivot++;
01671             else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[pe] != UNIT_EDGE || eType[*iei] != UNIT_EDGE))                       nontrivialEdgeChange_elimPivot++;
01672             else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[pe] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE))   nontrivialEdgeChange_elimPivot++;
01673           } // end fill-in case
01674 
01675         } // end all successors of tgt(e)=tgt(pe)
01676         if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_elimPivot < 0) er.pivot_eliminatable = true;
01677       } // end determine nontrivialEdgeChange_elimPivot
01678 
01679       //------------------------------------------------------------------------------------------------------------------------------------------------
01680       // determine effect of front-eliminating (type 3) 
01681       //------------------------------------------------------------------------------------------------------------------------------------------------
01682 
01683       // iterate over inedges of src(e), consider front-elimination of *iei
01684       if (vertex_type(source(e, angelLCG), angelLCG) != dependent) {
01685         for (tie(iei, ie_end) = in_edges(source(e, angelLCG), angelLCG); iei != ie_end; ++iei) {
01686           int nontrivialEdgeChange_frontElimination = 0;
01687 
01688           // consider loss of *iei
01689           if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS
01690           || (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*iei] != UNIT_EDGE)
01691           || (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*iei] == VARIABLE_EDGE)) nontrivialEdgeChange_frontElimination--;
01692 
01693           // consider fill/absorb effect of front-eliminating *iei
01694           for (tie(oei, oe_end) = out_edges(source(e, angelLCG), angelLCG); oei != oe_end; ++oei) {
01695             if (*oei == e) continue; // skip the rerouted edge
01696             tie(absorb_e, found_absorb_e) = edge(source(*iei, angelLCG), target(*oei, angelLCG), angelLCG);
01697             if (found_absorb_e) { // absorption: only counts if it goes from trivial to nontrivial
01698               if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[absorb_e] == UNIT_EDGE)                  nontrivialEdgeChange_frontElimination++;
01699               else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[absorb_e] != VARIABLE_EDGE)
01700                 if (eType[*oei] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)                                       nontrivialEdgeChange_frontElimination++;
01701             }
01702             else { // fill-in
01703               if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS)                                                                            nontrivialEdgeChange_frontElimination++;
01704               else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && (eType[*oei] != UNIT_EDGE || eType[*iei] != UNIT_EDGE))           nontrivialEdgeChange_frontElimination++;
01705               else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && (eType[*oei] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE))       nontrivialEdgeChange_frontElimination++;
01706             } // end fill-in
01707           } // end all outedges of src(e)
01708           if (nontrivialEdgeChange_rerouting + nontrivialEdgeChange_frontElimination < 0) er.type3EdgeElimVector.push_back(source(*iei, angelLCG));
01709         } // end all inedges of src(e)
01710       } // end type 3
01711     } // end post-routing
01712 
01713     if (er.pivot_eliminatable || er.increment_eliminatable || !er.type3EdgeElimVector.empty())
01714       reducingReroutingsV.push_back(Rerouting (er, angelLCG));
01715 
01716   } // end iterate through erv
01717 
01718 #ifndef NDEBUG
01719   cout << "     Of " << erv.size() << " reroutings passed to reducing_reroutings(), " << reducingReroutingsV.size() << " reduce the nontrivial edge count when followed by elimination" << endl;
01720 #endif
01721 
01722   return !reducingReroutingsV.empty();
01723 } // end reducing_reroutings()
01724 
01725 // ==============================================================================
01726 // |            FILTERS FOR ELIMINATIONS AND REROUTINGS (TRANSFORMATIONS)       |
01727 // ==============================================================================
01728 
01729 int transformation_effect(const Transformation t,
01730                           const c_graph_t& angelLCG,
01731                           const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) {
01732   int effect;
01733   if (t.isRerouting()) {
01734     bool dummy_incrementIsTrivial;
01735     effect = reroute_effect(t.getRerouting().getER(angelLCG), angelLCG, ourAwarenessLevel, dummy_incrementIsTrivial);
01736   }
01737   else
01738     effect = edge_elim_effect(t.getEdgeElim(), angelLCG, ourAwarenessLevel);
01739   return effect;
01740 } // end transformation_effect()
01741 
01742 bool all_viable_transformations (c_graph_t& angelLCG,
01743                                  const std::vector<Transformation>& transformationsPerformedV,
01744                                  vector<Transformation>& allViableTransformationsV) {
01745   allViableTransformationsV.clear();
01746   // find all eliminatable edges
01747   vector<EdgeElim> allEdgeElimsV;
01748   eliminatable_edges(angelLCG, allEdgeElimsV);
01749   for (size_t i = 0; i < allEdgeElimsV.size(); i++)
01750     allViableTransformationsV.push_back(Transformation (allEdgeElimsV[i]));
01751   // find viable reroutings
01752   vector<Rerouting> allReroutingsV, noncyclicReroutingsV;
01753   reroutable_edges (angelLCG, allReroutingsV);
01754   noncyclicReroutings (allReroutingsV, transformationsPerformedV, angelLCG, noncyclicReroutingsV);
01755   for (size_t i = 0; i < noncyclicReroutingsV.size(); i++)
01756     allViableTransformationsV.push_back(Transformation (noncyclicReroutingsV[i]));
01757   #ifndef NDEBUG
01758   cout << "\tThere are " << allEdgeElimsV.size() << " viable Edge eliminations in G" << endl;
01759   cout << "\tOf " << allReroutingsV.size() << " possible reroutings, " << noncyclicReroutingsV.size() << " are noncyclic" << endl;
01760   cout << "\t\tThere are " << allViableTransformationsV.size() << " viable transformations in G" << endl;
01761   #endif
01762   return !allViableTransformationsV.empty();
01763 } // end all_viable_transformations()
01764 
01765 bool maintaining_transformations(const vector<Transformation>& tv,
01766                                  const c_graph_t& angelLCG,
01767                                  const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01768                                  vector<Transformation>& maintainingTransformationsV) {
01769   maintainingTransformationsV.clear();
01770   if (tv.empty())
01771     return false;
01772 
01773   vector<Rerouting> tempReroutingsV;
01774   vector<EdgeElim> tempEdgeElimsV, tempMaintainingEdgeElimsV;
01775 
01776   // create temporary lists
01777   for (size_t i = 0; i < tv.size(); i++)
01778     tv[i].isRerouting() ? tempReroutingsV.push_back(tv[i].getRerouting())
01779                         : tempEdgeElimsV.push_back(tv[i].getEdgeElim());
01780 
01781   // if there are edge elims, push them to the transformation vector
01782   if (maintaining_edge_eliminations(tempEdgeElimsV, angelLCG, ourAwarenessLevel, tempMaintainingEdgeElimsV)) 
01783     for (size_t i = 0; i < tempMaintainingEdgeElimsV.size(); i++)
01784       maintainingTransformationsV.push_back(Transformation (tempMaintainingEdgeElimsV[i]));
01785 
01786   // push all reroutings to the transformation vector
01787   for (size_t i = 0; i < tempReroutingsV.size(); i++)
01788     maintainingTransformationsV.push_back(Transformation (tempReroutingsV[i]));
01789 
01790   #ifndef NDEBUG
01791   cout << "Of " << tv.size() << " transformations passed to maintaining_transformations()"
01792        << ", " << maintainingTransformationsV.size() << " maintain the nontrivial edge count" << endl;
01793   #endif
01794 
01795   // if there are neither edge elims nor reroutings, return the transformation vector we were passed
01796   if (maintainingTransformationsV.empty()) {
01797     maintainingTransformationsV = tv;
01798     return false;
01799   }
01800   else return true;
01801 } // end count_maintaining_transformations()
01802 
01803 bool reducing_transformations(const vector<Transformation>& tv,
01804                               const c_graph_t& angelLCG,
01805                               const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01806                               vector<Transformation>& reducingTransformationsV) {
01807   reducingTransformationsV.clear();
01808   if (tv.empty())
01809     return 0;
01810 
01811   vector<Rerouting> tempReroutingsV, tempReducingReroutingsV;
01812   vector<EdgeElim> tempEdgeElimsV, tempReducingEdgeElimsV;
01813 
01814   // split tv into separate temporary lists
01815   for (size_t i = 0; i < tv.size(); i++)
01816     tv[i].isRerouting() ? tempReroutingsV.push_back(tv[i].getRerouting())
01817                         : tempEdgeElimsV.push_back(tv[i].getEdgeElim());
01818 
01819   // if there are edge elims, push them to the transformation vector
01820   if (reducing_edge_eliminations(tempEdgeElimsV, angelLCG, ourAwarenessLevel, tempReducingEdgeElimsV)) 
01821     for (size_t i = 0; i < tempReducingEdgeElimsV.size(); i++)
01822       reducingTransformationsV.push_back(Transformation (tempReducingEdgeElimsV[i]));
01823 
01824   // if there are reroutings, push them to the transformation vector
01825   if (reducing_reroutings(tempReroutingsV, angelLCG, ourAwarenessLevel, tempReducingReroutingsV))
01826     for (size_t i = 0; i < tempReducingReroutingsV.size(); i++)
01827       reducingTransformationsV.push_back(Transformation (tempReducingReroutingsV[i]));
01828 
01829 #ifndef NDEBUG
01830   cout << "Of " << tv.size() << " transformations passed to reducing_transformations(), " << reducingTransformationsV.size() << " reduce the nontrivial edge count" << endl;
01831 #endif
01832 
01833   // if there are neither edge elims nor reroutings, return only the edge elims
01834   if (reducingTransformationsV.empty()) {
01835     for (size_t i = 0; i < tempEdgeElimsV.size(); i++) // push back all the edge elims
01836       reducingTransformationsV.push_back(Transformation (tempEdgeElimsV[i]));
01837     // if there are no edge elims that maintain or reduce, and no reroutings that reduce: push back all edge elims
01838     if (reducingTransformationsV.empty()) {
01839       vector<EdgeElim> allEdgeElimsV;
01840       eliminatable_edges(angelLCG, allEdgeElimsV);
01841       for (size_t j = 0; j < allEdgeElimsV.size(); j++)
01842         reducingTransformationsV.push_back(Transformation (allEdgeElimsV[j]));
01843     }
01844     return false;
01845   }    
01846 /*
01847   // if there are neither edge elims nor reroutings, return the transformation vector we were passed
01848   if (reducingTransformationsV.empty()) {
01849     reducingTransformationsV = tv;
01850     return false;
01851   } */
01852   else return true;
01853 
01854 } // end count_reducing_transformations()
01855 
01856 bool refill_avoiding_transformations(const vector<Transformation>& tv,
01857                                      c_graph_t& angelLCG,
01858                                      const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
01859                                      const refillDependenceMap_t& refillDependences,
01860                                      vector<Transformation>& refillAvoidingTransformationsV) {
01861   refillAvoidingTransformationsV.clear();
01862   if (tv.empty())
01863     return false;
01864 
01865   vector<Rerouting> tempReroutingsV;
01866   vector<EdgeElim> tempEdgeElimsV, tempRefillAvoidingEdgeElimsV;
01867 
01868   // create temporary edge elim and rerouting vectors
01869   for (size_t i = 0; i < tv.size(); i++)
01870     tv[i].isRerouting() ? tempReroutingsV.push_back(tv[i].getRerouting())
01871                         : tempEdgeElimsV.push_back(tv[i].getEdgeElim());
01872 
01873   // run edge elims through the refill filter
01874   if (refill_avoiding_edge_eliminations(tempEdgeElimsV, angelLCG, refillDependences, tempRefillAvoidingEdgeElimsV)) {
01875     // push refill avoiding edge elims to the transformation vector
01876     for (size_t i = 0; i < tempRefillAvoidingEdgeElimsV.size(); i++)
01877       refillAvoidingTransformationsV.push_back(Transformation (tempRefillAvoidingEdgeElimsV[i]));
01878     // push all reroutings to the transformation vector
01879     for (size_t i = 0; i < tempReroutingsV.size(); i++)
01880       refillAvoidingTransformationsV.push_back(Transformation (tempReroutingsV[i]));
01881     return true;
01882   } // end if refill avoiders were found
01883 
01884   else { // none of the edge elims avoid refill
01885     refillAvoidingTransformationsV = tv;
01886     return false;
01887   }
01888 } // end refill_avoiding_transformations()
01889 
01890 bool rerouting_considerate_transformations(const vector<Transformation>& tv,
01891                                            const c_graph_t& angelLCG,
01892                                            const std::vector<Transformation>& transformationsPerformedV,
01893                                            vector<Transformation>& reroutingConsiderateTransformationsV) {
01894   reroutingConsiderateTransformationsV.clear();
01895   if (tv.empty())
01896     return false;
01897 
01898   vector<Transformation> tempReroutingsV;
01899   vector<EdgeElim> tempEdgeElimsV, tempReroutingConsiderateEdgeElimsV;
01900 
01901   // create temporary edge elim and rerouting vectors
01902   for (size_t i = 0; i < tv.size(); i++)
01903     tv[i].isRerouting() ? tempReroutingsV.push_back(tv[i].getRerouting())
01904                         : tempEdgeElimsV.push_back(tv[i].getEdgeElim());
01905 
01906   // pass all edge elims through the edge elim filter
01907   if (rerouting_considerate_edge_eliminations(tempEdgeElimsV, angelLCG, transformationsPerformedV, tempReroutingConsiderateEdgeElimsV)) {
01908     // add preferred edge elims to the transformations vector to be returned
01909     for (size_t i = 0; i < tempReroutingConsiderateEdgeElimsV.size(); i++)
01910       reroutingConsiderateTransformationsV.push_back(Transformation (tempReroutingConsiderateEdgeElimsV[i]));
01911     // push all reroutings to the transformation vector
01912     for (size_t i = 0; i < tempReroutingsV.size(); i++)
01913       reroutingConsiderateTransformationsV.push_back(Transformation (tempReroutingsV[i]));
01914     return true;
01915   } // end if rerouting considerate edge elims were found
01916 
01917   else { // none of the edge elims are rerouting considerate
01918     reroutingConsiderateTransformationsV = tv;
01919     return false;
01920   }
01921 } // end rerouting_considerate_transformations ()
01922 
01923 bool lowest_markowitz_transformations(const vector<Transformation>& tv,
01924                                       const c_graph_t& angelLCG,
01925                                       vector<Transformation>& lowestMarkowitzTransformationsV) {
01926   lowestMarkowitzTransformationsV.clear();
01927   if (tv.empty())
01928     return false;
01929   // create temporary edge elim vector
01930   vector<EdgeElim> tempEdgeElimsV, tempLowestMarkowitzEdgeElimsV;
01931   for (size_t i = 0; i < tv.size(); i++)
01932     if (!tv[i].isRerouting())
01933       tempEdgeElimsV.push_back(tv[i].getEdgeElim());
01934   // if no edge elims, return exactly what we got
01935   if (tempEdgeElimsV.empty()) {
01936     lowestMarkowitzTransformationsV = tv;
01937     return false;
01938   }
01939   lowestMarkowitzEdgeElim(tempEdgeElimsV, angelLCG, tempLowestMarkowitzEdgeElimsV);
01940   // add preferred edge elims to the transformations vector to be returned
01941   for (size_t i = 0; i < tempLowestMarkowitzEdgeElimsV.size(); i++)
01942     lowestMarkowitzTransformationsV.push_back(Transformation (tempLowestMarkowitzEdgeElimsV[i]));
01943   return true;
01944 } // end lowest_markowitz_transformations()
01945 
01946 bool reverse_mode_transformations(const vector<Transformation>& tv,
01947                                   const c_graph_t& angelLCG,
01948                                   vector<Transformation>& reverseModeTransformationsV) {
01949   reverseModeTransformationsV.clear();
01950   if (tv.empty())
01951     return false;
01952   // create temporary edge elim vector
01953   vector<EdgeElim> tempEdgeElimsV, tempReverseModeEdgeElimsV;
01954   for (size_t i = 0; i < tv.size(); i++)
01955     if (!tv[i].isRerouting())
01956       tempEdgeElimsV.push_back(tv[i].getEdgeElim());
01957   // if no edge elims, return exactly what we got
01958   if (tempEdgeElimsV.empty()) {
01959     reverseModeTransformationsV = tv;
01960     return false;
01961   }
01962   reverseModeEdgeElim(tempEdgeElimsV, angelLCG, tempReverseModeEdgeElimsV);
01963   // add preferred edge elims to the transformations vector to be returned
01964   for (size_t i = 0; i < tempReverseModeEdgeElimsV.size(); i++)
01965     reverseModeTransformationsV.push_back(Transformation (tempReverseModeEdgeElimsV[i]));
01966   return true;
01967 } // end reverse_mode_transformations()
01968 
01969 #endif // USEXAIFBOOSTER
01970 
01971 } // namespace angel
01972 
01973 // to do: some names are confusing, e.g. ev for a face vector
Generated on Wed Mar 11 10:33:11 2009 for angel by  doxygen 1.5.3