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