angel  mercurial changeset:
src/eliminations.cpp
Go to the documentation of this file.
00001 // $Id: eliminations.cpp,v 1.13 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 #include "angel/include/eliminations.hpp"
00011 #include "angel/include/angel_tools.hpp"
00012 #include "angel/include/angel_io.hpp"
00013 
00014 namespace angel {
00015 
00016 using namespace std;
00017 using namespace boost;
00018 
00019 // =========================================================================
00020 // eliminations in c-graph
00021 // =========================================================================
00022 
00023 // -------------------------------------------------------------------------
00024 // elimination of a single vertex in compute graph
00025 // -------------------------------------------------------------------------
00026 
00027 int vertex_elimination (c_graph_t::vertex_t v, c_graph_t& cg) {
00028   // vector used since eliminations invalidate iterators
00029   vector<c_graph_t::edge_t> ev;
00030   c_graph_t::oei_t oei, oe_end;
00031   for (tie (oei, oe_end)= out_edges (v, cg); oei != oe_end; ++oei)
00032     ev.push_back (*oei);
00033 
00034   int costs= 0;
00035   for (size_t n= 0; n < ev.size(); n++)
00036     costs+= back_edge_elimination (ev[n], cg);
00037   // UN: print graph after elimination
00038   // graphviz_display(cg);
00039   return costs;
00040 }
00041 
00042 // -------------------------------------------------------------------------
00043 // elimination of a single egde in compute graph
00044 // -------------------------------------------------------------------------
00045 
00046 int front_edge_elimination (c_graph_t::edge_t edge_ij, c_graph_t& cg) {
00047   using boost::tie;
00048 
00049   typedef c_graph_t::vertex_t          vertex_t;
00050   typedef c_graph_t::edge_t            edge_t;
00051   typedef c_graph_t::oei_t             oei_t;
00052   c_graph_t::ew_t                      ew= get(edge_weight, cg);
00053   boost::property_map<c_graph_t, EdgeType>::type eType = get(EdgeType(), cg);
00054   // write_edge_property (std::cout, "edge weights ", ew, cg);
00055 
00056   vertex_t i= source (edge_ij, cg), j= target (edge_ij, cg);
00057 
00058   if (cg.vertex_type (j) == dependent) return 0;
00059 
00060   int c_ji= ew[edge_ij];
00061   // safe edges in vector because iterators will be invalidated
00062   oei_t oei, oe_end;
00063   std::vector<edge_t> ev;
00064   for (tie (oei, oe_end)= out_edges (j, cg); oei != oe_end; ++oei)
00065     ev.push_back (*oei);
00066 
00067   for (size_t n= 0; n < ev.size(); n++) {
00068     edge_t edge_jk= ev[n];
00069     vertex_t k= target (edge_jk, cg);
00070     int d= c_ji * ew[edge_jk];
00071 
00072     bool   found_ik;
00073     edge_t edge_ik;
00074     tie (edge_ik, found_ik)= edge (i, k, cg);
00075     if (found_ik) { // absorption
00076       ew[edge_ik]+= d;
00077       if (eType[edge_ij] == VARIABLE_EDGE || eType[edge_jk] == VARIABLE_EDGE)   eType[edge_ik] = VARIABLE_EDGE;
00078       else if (eType[edge_ik] != VARIABLE_EDGE)                                 eType[edge_ik] = CONSTANT_EDGE;
00079     } 
00080     else { // fill-in
00081       tie (edge_ik, found_ik)= add_edge (i, k, cg.next_edge_number++, cg);
00082       ew[edge_ik]= d;
00083       if (eType[edge_ij] == VARIABLE_EDGE || eType[edge_jk] == VARIABLE_EDGE)   eType[edge_ik] = VARIABLE_EDGE;
00084       else if (eType[edge_ij] == UNIT_EDGE && eType[edge_jk] == UNIT_EDGE)      eType[edge_ik] = UNIT_EDGE;
00085       else                                                                      eType[edge_ik] = CONSTANT_EDGE;
00086     }
00087   }
00088   remove_edge (edge_ij, cg);
00089 
00090   // if ij was the last in_edge of j then all out-edges (stored in ev) become unreachable
00091   // targets of out-edges shall be reachable by the set of edge_ik's
00092   if (in_degree (j, cg) == 0)
00093     for (size_t n= 0; n < ev.size(); n++)
00094     remove_edge (ev[n], cg);
00095   // is overkill: remove_unreachable_edges (j, cg);
00096 
00097   return ev.size();
00098 }
00099 
00100 int back_edge_elimination (c_graph_t::edge_t edge_ij, c_graph_t& cg) {
00101   using namespace boost;
00102   using boost::tie;
00103 
00104   typedef c_graph_t::vertex_t          vertex_t;
00105   typedef c_graph_t::edge_t            edge_t;
00106   typedef c_graph_t::iei_t             iei_t;
00107   c_graph_t::ew_t                      ew= get(edge_weight, cg);
00108   boost::property_map<c_graph_t, EdgeType>::type eType = get(EdgeType(), cg);
00109 
00110   vertex_t i= source (edge_ij, cg), j= target (edge_ij, cg);
00111 
00112   if (cg.vertex_type (i) == independent) return 0;
00113 
00114   int c_ji= ew[edge_ij];
00115   // safe edges in vector because iterators will be invalidated
00116   iei_t iei, ie_end;
00117   std::vector<edge_t> ev;
00118   for (tie (iei, ie_end)= in_edges (i, cg); iei != ie_end; ++iei)
00119     ev.push_back (*iei);
00120 
00121   for (size_t n= 0; n < ev.size(); n++) {
00122     edge_t edge_ki= ev[n];
00123     vertex_t k= source (edge_ki, cg);
00124     int d= c_ji * ew[edge_ki];
00125 
00126     bool   found_kj;
00127     edge_t edge_kj;
00128     tie (edge_kj, found_kj)= edge (k, j, cg);
00129     if (found_kj) { // absorption 
00130       ew[edge_kj]+= d;
00131       if (eType[edge_ij] == VARIABLE_EDGE || eType[edge_ki] == VARIABLE_EDGE)   eType[edge_kj] = VARIABLE_EDGE;
00132       else if (eType[edge_kj] != VARIABLE_EDGE)                                 eType[edge_kj] = CONSTANT_EDGE;
00133     }
00134     else { // fill-in
00135       tie (edge_kj, found_kj)= add_edge (k, j, cg.next_edge_number++, cg);
00136       ew[edge_kj]= d; 
00137       if (eType[edge_ij] == VARIABLE_EDGE || eType[edge_ki] == VARIABLE_EDGE)   eType[edge_kj] = VARIABLE_EDGE;
00138       else if (eType[edge_ij] == UNIT_EDGE && eType[edge_ki] == UNIT_EDGE)      eType[edge_kj] = UNIT_EDGE;
00139       else                                                                      eType[edge_kj] = CONSTANT_EDGE;
00140     }
00141   }
00142   remove_edge (edge_ij, cg);
00143 
00144   // if ij was the last out_edge of i then all in-edges (stored in ev) become irrelevant
00145   // except if i is a dependent vertex
00146   // sources of in-edges shall be relevant due to the set of edge_ik's
00147   if (out_degree (i, cg) == 0 && vertex_type (i, cg) != dependent)
00148     for (size_t n= 0; n < ev.size(); n++)
00149       remove_edge (ev[n], cg); 
00150   // is overkill: remove_irrelevant_edges (i, cg);
00151 
00152   return ev.size();
00153 }
00154 
00155 
00156 
00157 
00158 
00159 // =========================================================================
00160 // eliminations in line graph
00161 // =========================================================================
00162 
00163 // -------------------------------------------------------------------------
00164 // elimination of a single vertex in line graph
00165 // -------------------------------------------------------------------------
00166 
00167 int vertex_elimination (int j, line_graph_t& lg) {
00168   vector<line_graph_t::face_t> fv;
00169   line_graph_t::evn_t evn= get(vertex_name, lg);
00170   line_graph_t::ei_t        ei, eend;
00171   for (tie (ei, eend)= vertices (lg); ei != eend; ++ei) 
00172     if (evn[*ei].second == j) {
00173       line_graph_t::ofi_t ofi, of_end;
00174       for (tie (ofi, of_end)= out_edges (*ei, lg); ofi != of_end; ++ofi) 
00175         fv.push_back (*ofi);
00176     }
00177   int costs= 0;
00178   for (size_t c= 0; c < fv.size(); c++)
00179     costs+= face_elimination (fv[c], lg);
00180   return costs;
00181 }  
00182 
00183 // -------------------------------------------------------------------------
00184 // elimination of a single egde in line graph
00185 // -------------------------------------------------------------------------
00186 
00187 int front_edge_elimination (int i, int j, line_graph_t& lg) {
00188   vector<line_graph_t::edge_t>    ev;
00189   find_edge (i, j, lg, ev);
00190   int costs= 0;
00191   for (size_t c= 0; c < ev.size(); c++)
00192     costs+= front_edge_elimination (ev[c], lg);
00193 
00194   return costs;
00195 }
00196 
00197 int front_edge_elimination (line_graph_t::edge_t vij, line_graph_t& lg) { 
00198   std::vector<line_graph_t::face_t> fv;
00199   line_graph_t::ofi_t oi, oend;
00200   for (boost::tie (oi, oend)= out_edges (vij, lg); oi != oend; ++oi)
00201     fv.push_back (*oi);
00202 
00203   int costs= 0;
00204   for (size_t n= 0; n < fv.size(); n++)
00205     costs+= face_elimination (fv[n], lg);
00206 
00207   return costs;
00208 }
00209 
00210 
00211 int back_edge_elimination (int i, int j, line_graph_t& lg) {
00212   vector<line_graph_t::edge_t>    ev;
00213   find_edge (i, j, lg, ev);
00214   int costs= 0;
00215   for (size_t c= 0; c < ev.size(); c++)
00216     costs+= back_edge_elimination (ev[c], lg);
00217   return costs;
00218 }
00219 
00220 int back_edge_elimination (line_graph_t::edge_t vij,
00221                            line_graph_t& lg) {
00222   std::vector<line_graph_t::face_t> fv;
00223   line_graph_t::ifi_t ii, iend;
00224   for (boost::tie (ii, iend)= in_edges (vij, lg); ii != iend; ++ii)
00225     fv.push_back (*ii);
00226 
00227   int costs= 0;
00228   for (size_t n= 0; n < fv.size(); n++)
00229     costs+= face_elimination (fv[n], lg);
00230 
00231   return costs;
00232 }
00233 
00234 // -------------------------------------------------------------------------
00235 // elimination of a single face in line graph
00236 // -------------------------------------------------------------------------
00237 
00238 int face_elimination (line_graph_t::face_t f, int kr, line_graph_t& lg, accu_graph_t& ac) {
00239 
00240   typedef line_graph_t::edge_t edge_t;
00241   edge_t                       i= source (f, lg), j= target (f, lg);
00242   vector<edge_t>               pi, sj, same_p, same_s, same;
00243 
00244   if ((int) i >= lg.v() || (int) j >= lg.v()) {
00245     return -1;}
00246 
00247   same_predecessors (i, lg, same_p); // same pred. as i
00248   same_successors (j, lg, same_s);
00249   same.resize (max (same_p.size(), same_s.size()));
00250   vector<edge_t>::iterator se= set_intersection (same_p.begin(), same_p.end(), same_s.begin(),
00251                                                  same_s.end(), same.begin());
00252   THROW_DEBUG_EXCEPT_MACRO (se-same.begin() >= 2, consistency_exception,
00253                          "More than one mergeable vertex in face elimination"); 
00254 
00255   if (kr != -1) {
00256     if (se != same.begin()) { // if matching vertex found, it must be kr (k requested)
00257       if (same[0] != edge_t (kr)) return -1;
00258     } else {
00259       if (kr < lg.v()) {
00260         edge_t e= vertex (kr, lg);
00261         if (out_degree (e, lg) > 0 || in_degree (e, lg) > 0) {
00262           return -1; } }
00263       // insert enough empty vertices
00264       for (; kr > lg.v();) {add_vertex (lg); ac.exp_nr.push_back (-1); }
00265     } }
00266 
00267   line_graph_t::ed_t   el= get(vertex_degree, lg);  // edge label
00268   int d= el[i] * el[j];
00269 
00270   THROW_DEBUG_EXCEPT_MACRO ((int) ac.exp_nr.size() != lg.v(), consistency_exception,
00271                          "Array exp_nr has wrong size"); 
00272   edge_t k;
00273   if (se != same.begin()) { // absorption
00274     k= same[0]; el[k]+= d; 
00275     ac.accu_exp.resize (ac.accu_exp.size() + 1);
00276     ac.accu_exp[ac.accu_exp.size()-1].set_graph (k, i, j, ac.exp_nr);
00277     ac.exp_nr[k]= ac.accu_exp.size()-1;
00278   } else {                  // new or empty edge
00279     if (kr == -1 || kr == lg.v()) {
00280       k= add_vertex (lg); ac.exp_nr.push_back(-1); }
00281     else k= vertex (kr, lg);             // this is an empty edge
00282 
00283     ac.accu_exp.resize (ac.accu_exp.size() + 1);
00284     ac.accu_exp[ac.accu_exp.size()-1].set_graph(accu_exp_t::mult, i, j, ac.exp_nr);
00285     ac.exp_nr[k]= ac.accu_exp.size()-1;
00286     line_graph_t::evn_t evn= get(vertex_name, lg);
00287     // assert (evn[i].second == evn[j].first); // adjacent edges ?
00288     THROW_DEBUG_EXCEPT_MACRO (evn[i].second != evn[j].first, consistency_exception,
00289                            "Adjacency corrupted in line graph"); 
00290     evn[k]= make_pair (evn[i].first, evn[j].second);
00291 
00292     sorted_predecessor_set (i, lg, pi); sorted_successor_set (j, lg, sj);
00293     for (size_t c= 0; c < pi.size(); c++)
00294       add_edge (pi[c], k, lg);
00295     for (size_t c= 0; c < sj.size(); c++)
00296       add_edge (k, sj[c], lg);
00297     el[k]= d;
00298     lg.cons_ok= false;
00299   }
00300   THROW_DEBUG_EXCEPT_MACRO (kr != -1 && edge_t (kr) != k, consistency_exception,
00301                          "Inserted Vertex has wrong number"); 
00302 
00303   remove_edge (f, lg);
00304 
00305   if (remove_irrelevant_edges (i, lg, true) > 0) // i is isolated
00306     lg.cons_ok= false;
00307   else {
00308     THROW_DEBUG_EXCEPT_MACRO (in_degree (i, lg) == 0 || out_degree (i, lg) == 0, consistency_exception,
00309                            "Undetected isolated vertex"); 
00310     vector<edge_t> same;
00311     same_neighbors (i, lg, same);
00312     THROW_DEBUG_EXCEPT_MACRO (same.size() >= 2, consistency_exception,
00313                            "More than one mergeable vertex in face elimination"); 
00314     if (same.size() > 0) { // mergeable vertex (edge in c-graph)
00315       edge_t i2= same[0];
00316       el[i]+= el[i2];
00317       clear_vertex (i2, lg); 
00318       ac.accu_exp.resize (ac.accu_exp.size() + 1);
00319       ac.accu_exp[ac.accu_exp.size()-1].set_graph (accu_exp_t::add, i, i2, ac.exp_nr);
00320       ac.exp_nr[i]= ac.accu_exp.size()-1;
00321       lg.cons_ok= false;}
00322   }
00323     
00324   if (remove_unreachable_edges (j, lg, true) > 0)  // j is isolated
00325     lg.cons_ok= false;
00326   else {
00327     THROW_DEBUG_EXCEPT_MACRO (in_degree (j, lg) == 0 || out_degree (j, lg) == 0, consistency_exception,
00328                            "Undetected isolated vertex"); 
00329     vector<edge_t> same;
00330     same_neighbors (j, lg, same);
00331     THROW_DEBUG_EXCEPT_MACRO (same.size() >= 2, consistency_exception,
00332                            "More than one mergeable vertex in face elimination"); 
00333     if (same.size() > 0) { // mergeable vertex (edge)
00334       edge_t j2= same[0];
00335       el[j]+= el[j2];
00336       clear_vertex (j2, lg); 
00337       ac.accu_exp.resize (ac.accu_exp.size() + 1);
00338       ac.accu_exp[ac.accu_exp.size()-1].set_graph (accu_exp_t::add, j, j2, ac.exp_nr);
00339       ac.exp_nr[j]= ac.accu_exp.size()-1;
00340       lg.cons_ok= false; }
00341   }
00342  
00343   return k;
00344 }
00345 
00346 // =========================================================================
00347 // which vertices, edges or faces can be eliminated
00348 // =========================================================================
00349 
00350 int eliminatable_vertices (const c_graph_t& cg, vector<c_graph_t::vertex_t>& vv) {
00351   vv.resize (0);
00352   c_graph_t::vi_t vi, v_end;
00353   for (tie(vi, v_end)= vertices(cg); vi != v_end; ++vi)
00354     if (cg.vertex_type (*vi) == intermediate) // only intermediate vertices can be eliminated
00355       vv.push_back (*vi);
00356   return vv.size();
00357 }
00358 
00359 int semi_eliminatable_vertices (const c_graph_t& cg, vector<c_graph_t::vertex_t>& vv) {
00360   vv.resize (0);
00361   c_graph_t::vi_t vi, v_end;
00362   for (tie(vi, v_end)= vertices(cg); vi != v_end; ++vi)
00363     // either intermediate or dependent with outgoing edges
00364     if (cg.vertex_type (*vi) == intermediate 
00365         || 
00366         (cg.vertex_type (*vi) == dependent && out_degree (*vi, cg) > 0))
00367       vv.push_back (*vi);
00368   return vv.size();
00369 }
00370 
00371 int eliminatable_edges (const c_graph_t& cg, 
00372                         std::vector<c_graph_t::edge_t>& ev) {
00373   // in fact it only copies the edges into a vector for better treatment
00374   ev.resize(0);
00375   c_graph_t::ei_t      ei, e_end;
00376   for (tie (ei, e_end)= edges (cg); ei != e_end; ++ei)
00377     ev.push_back (*ei);
00378   return ev.size();
00379 }
00380 
00381 int front_eliminatable_edges (const c_graph_t& cg, 
00382                               std::vector<c_graph_t::edge_t>& ev) {
00383   // in fact it only copies the edges into a vector for better treatment
00384   ev.resize(0);
00385   c_graph_t::ei_t      ei, e_end;
00386   for (tie (ei, e_end)= edges (cg); ei != e_end; ++ei)
00387     if (vertex_type (target (*ei, cg), cg) != dependent)
00388       ev.push_back (*ei);
00389   return ev.size();
00390 }
00391 
00392 int back_eliminatable_edges (const c_graph_t& cg, 
00393                              std::vector<c_graph_t::edge_t>& ev) {
00394   // in fact it only copies the edges into a vector for better treatment
00395   ev.resize(0);
00396   c_graph_t::ei_t      ei, e_end;
00397   for (tie (ei, e_end)= edges (cg); ei != e_end; ++ei)
00398     if (vertex_type (source (*ei, cg), cg) != independent)
00399       ev.push_back (*ei);
00400   return ev.size();
00401 }
00402 
00403 int eliminatable_edges (const c_graph_t& cg,
00404                         std::vector<edge_bool_t>& ev) {
00405   ev.resize(0);
00406   c_graph_t::ei_t      ei, e_end;
00407   for (tie (ei, e_end)= edges (cg); ei != e_end; ++ei) {
00408     // can edge be back-eliminated ?
00409     if (vertex_type (source (*ei, cg), cg) != independent)
00410       ev.push_back (std::pair<c_graph_t::edge_t,bool> (*ei, false)); 
00411     // can edge be front-eliminated ?
00412     if (vertex_type (target (*ei, cg), cg) != dependent)
00413       ev.push_back (std::pair<c_graph_t::edge_t,bool> (*ei, true)); 
00414   }
00415   return ev.size();
00416 }
00417 
00418 int eliminatable_edges (const c_graph_t& cg,
00419                         std::vector<edge_ij_elim_t>& ev) {
00420   ev.resize(0);
00421   c_graph_t::ei_t      ei, e_end;
00422   for (tie (ei, e_end)= edges (cg); ei != e_end; ++ei) {
00423     edge_ij_elim_t ee (source (*ei, cg), target (*ei, cg), false);
00424     // can edge be back-eliminated ?
00425     if (vertex_type (source (*ei, cg), cg) != independent)
00426       ev.push_back (ee); 
00427     // can edge be front-eliminated ?
00428     if (vertex_type (target (*ei, cg), cg) != dependent) {
00429       ee.front= true; ev.push_back (ee); } 
00430   }
00431   return ev.size();
00432 }
00433 
00434 unsigned int eliminatable_edges(const c_graph_t& cg,
00435                                 std::vector<EdgeElim>& ev) {
00436   ev.clear();
00437   c_graph_t::ei_t ei, e_end;
00438   for (tie(ei, e_end) = edges(cg); ei != e_end; ++ei) {
00439     // can edge be back-eliminated ?
00440     if (vertex_type(source(*ei, cg), cg) != independent)
00441       ev.push_back(EdgeElim (*ei, false, cg));
00442     // can edge be front-eliminated ?
00443     if (vertex_type(target(*ei, cg), cg) != dependent)
00444       ev.push_back(EdgeElim (*ei, true, cg));
00445   } // end iterate over all edges
00446   return ev.size();
00447 } // end eliminatable_edges()
00448 
00449 int eliminatable_faces (const line_graph_t& lg, 
00450                         std::vector<line_graph_t::face_t>& fv) {
00451   // in fact it only copies the edges into a vector for better treatment
00452   fv.resize(0);
00453   graph_traits<line_graph_t>::edge_iterator      ei, e_end;
00454   for (tie (ei, e_end)= edges (lg); ei != e_end; ++ei) {
00455     line_graph_t::vertex_descriptor s= source (*ei, lg), t= target (*ei, lg);
00456     if (vertex_type (s, lg) != independent && vertex_type (t, lg) != dependent)
00457       fv.push_back (*ei);
00458   }
00459   return fv.size();
00460 }
00461 
00462 bool convert_elimination_sequence (const vector<c_graph_t::vertex_t>& vv, 
00463                                    const c_graph_t& cg,
00464                                    vector<edge_ij_elim_t>& ev) {
00465   c_graph_t cgc (cg);
00466   ev.resize (0);
00467   for (size_t c= 0; c < vv.size(); c++) {
00468     c_graph_t::iei_t  iei, ie_end;
00469     // cout << "conv_elim_seq: eliminate vertex " << vv[c];
00470     // write_graph ("from graph", cgc);
00471     for (tie (iei, ie_end)= in_edges (vv[c], cgc); iei != ie_end; ++iei) {
00472       edge_ij_elim_t ee (source (*iei, cgc), target (*iei, cgc), true);
00473       // cout << "new edge " << ee;
00474       ev.push_back (ee); }
00475     // cout << endl;
00476     vertex_elimination (vv[c], cgc); }
00477   return true;
00478 }
00479 
00480 bool convert_elimination_sequence (const vector<edge_ij_elim_t>& ev, 
00481                                    const line_graph_t& lg,
00482                                    vector<triplet_t>& tv) {
00483   line_graph_t lgc (lg);
00484   tv.resize (0);
00485   for (size_t c= 0; c < ev.size(); c++) {
00486     edge_ij_elim_t ee = ev[c];
00487     vector<line_graph_t::edge_t> lev;
00488     // cout << "conv_elim_seq: eliminate edge " << ee;
00489     // write_graph ("from graph", lgc);
00490     // line_graph_t::evn_t            evn= get(vertex_name, lgc);
00491     // write_vertex_property (cout, "vertices of this edge graph", evn, lgc);
00492     // std::cout << "dealing with edge elim: " << ee.i << " to " << ee.j << std::endl; 
00493     line_graph_t::edge_t ledge;
00494 
00495 #ifndef NDEBUG
00496     cout << endl;
00497     cout << "convert_elimination_sequence: eliminate edge " << ee;
00498     write_graph ("from line graph: ", lgc);
00499     line_graph_t::evn_t evn = get(vertex_name, lgc);
00500     write_vertex_property (cout, "Labels of vertices in this line graph: ", evn, lgc);
00501 #endif
00502 
00503     bool found = find_edge (ee.i, ee.j, lgc, lev);
00504     THROW_EXCEPT_MACRO (!found || lev.empty(), consistency_exception, "LCG edge has no corresponding line graph node");
00505 
00506     if (lev.size() == 1) { ledge = lev[0]; }
00507     else { // if lev.size() != 1
00508       cout << lev.size() << " line graph nodes correspond to LCG edge (" << ee.i << ", " << ee.j << ")."
00509                          << "  Determining the correct one...";
00510       vector<line_graph_t::edge_t> candidates;
00511       // iterate through corresponding line graph vertices to ensure only one of them isn't isolated
00512       for (size_t l = 0; l < lev.size(); l++) {
00513         if (in_degree(lev[l], lgc) > 0 || out_degree(lev[l], lgc) > 0) candidates.push_back(lev[l]);
00514       }
00515       THROW_EXCEPT_MACRO (candidates.empty(), consistency_exception, "all corresponding line graph nodes are isolated");
00516       THROW_EXCEPT_MACRO (candidates.size() > 1, consistency_exception, "multiple non-isolated corresponding line graph nodes");
00517 
00518       cout << " Unique correlation found!\n";
00519       ledge = candidates[0];
00520     } // end lev.size() != 1
00521 
00522     if (ee.front) {
00523       line_graph_t::ofi_t oi, oend;
00524       for (boost::tie (oi, oend) = out_edges (ledge, lgc); oi != oend; ++oi) {
00525         triplet_t t (ledge, target (*oi, lgc), -1); tv.push_back (t);
00526 #ifndef NDEBUG
00527         cout << "new face " << t << endl;
00528 #endif
00529       }
00530       front_edge_elimination (ee.i, ee.j, lgc);
00531     } else {
00532       line_graph_t::ifi_t ii, iend;
00533       for (boost::tie (ii, iend) = in_edges (ledge, lgc); ii != iend; ++ii) {
00534         triplet_t t (source (*ii, lgc), ledge, -1); tv.push_back (t);
00535 #ifndef NDEBUG
00536         cout << "new face " << t << endl;
00537 #endif
00538       }
00539       back_edge_elimination (ee.i, ee.j, lgc); }
00540   } // end all edge eliminations
00541   return true;
00542 } // end convert_elimination_sequence()
00543 
00544 #ifdef USEXAIFBOOSTER
00545 //############################################################################################################
00546 // DIRECT ELIMINATIONS
00547 
00548 EdgeRefType_E getRefType (const c_graph_t::edge_t e, const c_graph_t& angelLCG, const list<EdgeRef_t>& edge_ref_list) {
00549   c_graph_t::const_eind_t eind = get(edge_index, angelLCG);
00550   for (list<EdgeRef_t>::const_iterator ref_it = edge_ref_list.begin(); ref_it != edge_ref_list.end(); ref_it++)
00551     if (source (e, angelLCG) == source (ref_it->my_angelLCGedge, angelLCG) &&
00552         target (e, angelLCG) == target (ref_it->my_angelLCGedge, angelLCG)) {
00553       THROW_EXCEPT_MACRO (ref_it->my_type == UNDEFINED, consistency_exception, "requested edge reference type is UNDEFINED");
00554       return ref_it->my_type;
00555     }
00556   THROW_EXCEPT_MACRO (true, consistency_exception, "can't return reference type - no reference entry could be found for edge");
00557 } // end getRef_type ()
00558 
00559 const xaifBoosterCrossCountryInterface::LinearizedComputationalGraphEdge* getLCG_p (const c_graph_t::edge_t e,
00560                                                   const c_graph_t& angelLCG,
00561                                                   const list<EdgeRef_t>& edge_ref_list) {
00562   c_graph_t::const_eind_t eind = get(edge_index, angelLCG);
00563   for (list<EdgeRef_t>::const_iterator ref_it = edge_ref_list.begin(); ref_it != edge_ref_list.end(); ref_it++)
00564     if (source (e, angelLCG) == source (ref_it->my_angelLCGedge, angelLCG) &&
00565         target (e, angelLCG) == target (ref_it->my_angelLCGedge, angelLCG)) {
00566       THROW_EXCEPT_MACRO (ref_it->my_LCG_edge_p == NULL, consistency_exception, "requested LCG edge pointer is NULL");
00567       return ref_it->my_LCG_edge_p;
00568     }
00569   THROW_EXCEPT_MACRO (true, consistency_exception, "can't return LCG_p - no reference entry could be found for edge");
00570 } // end getLCG_p ()
00571 
00572 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex* getJAE_p (const c_graph_t::edge_t e,
00573                                                                                   const c_graph_t& angelLCG,
00574                                                                                   const list<EdgeRef_t>& edge_ref_list) {
00575   c_graph_t::const_eind_t eind = get(edge_index, angelLCG);
00576   for (list<EdgeRef_t>::const_iterator ref_it = edge_ref_list.begin(); ref_it != edge_ref_list.end(); ref_it++)
00577     if (source (e, angelLCG) == source (ref_it->my_angelLCGedge, angelLCG) &&
00578         target (e, angelLCG) == target (ref_it->my_angelLCGedge, angelLCG)) {
00579       THROW_EXCEPT_MACRO (ref_it->my_JAE_vertex_p == NULL, consistency_exception, "requested JAE vertex pointer is NULL");
00580       return ref_it->my_JAE_vertex_p;
00581     }
00582   THROW_EXCEPT_MACRO (true, consistency_exception, "can't return JAE_p - no reference entry could be found for edge");
00583 } // end getJAE_p ()
00584 
00585 void setJaevRef (const c_graph_t::edge_t e,
00586                  xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex& jaev,
00587                  const c_graph_t& angelLCG,
00588                  const list<EdgeRef_t>& edge_ref_list) {
00589   EdgeRefType_E e_ref_type = getRefType (e, angelLCG, edge_ref_list);
00590   if (e_ref_type == LCG_EDGE) {
00591     const xaifBoosterCrossCountryInterface::LinearizedComputationalGraphEdge* LCG_p = getLCG_p (e, angelLCG, edge_ref_list);
00592     jaev.setExternalReference (*LCG_p);
00593   }
00594   else if (e_ref_type == JAE_VERT) {
00595     xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex* JAE_p = getJAE_p (e, angelLCG, edge_ref_list);
00596     jaev.setInternalReference (*JAE_p);
00597   }
00598   else THROW_EXCEPT_MACRO (true, consistency_exception, "cannot set JAE vertex ref because edge reference type is UNDEFINED");
00599 } // end setJaevRef ()
00600 
00601 void removeRef (const c_graph_t::edge_t e,
00602                 const c_graph_t& angelLCG,
00603                 list<EdgeRef_t>& edge_ref_list) {
00604   for (list<EdgeRef_t>::iterator ref_it = edge_ref_list.begin(); ref_it != edge_ref_list.end(); ref_it++)
00605     if (source (e, angelLCG) == source (ref_it->my_angelLCGedge, angelLCG) &&
00606         target (e, angelLCG) == target (ref_it->my_angelLCGedge, angelLCG)) {
00607       edge_ref_list.erase(ref_it);
00608       return;
00609     }
00610   THROW_EXCEPT_MACRO (true, consistency_exception, "couldn't find edge reference in order to remove it");
00611 } // end removeRef()
00612 
00613 // Creates a new JAE corresponding to multiplying edges e1 and e2
00614 // where e1 comes before e2
00615 unsigned int multiply_edge_pair_directly (const c_graph_t::edge_t e1,
00616                                           const c_graph_t::edge_t e2,
00617                                           c_graph_t& angelLCG,
00618                                           list<EdgeRef_t>& edge_ref_list,
00619                                           xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionList& jae_list) {
00620 
00621   // Create JAE with vertices for multiply and for the two edges being multiplied
00622   xaifBoosterCrossCountryInterface::JacobianAccumulationExpression& new_jae = jae_list.addExpression();
00623   xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex& jaev_mult = new_jae.addVertex();
00624   jaev_mult.setOperation (xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex::MULT_OP);
00625   xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex& jaev_e1 = new_jae.addVertex();
00626   xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex& jaev_e2 = new_jae.addVertex();
00627   setJaevRef (e1, jaev_e1, angelLCG, edge_ref_list);
00628   setJaevRef (e2, jaev_e2, angelLCG, edge_ref_list);
00629   new_jae.addEdge(jaev_e1, jaev_mult);
00630   new_jae.addEdge(jaev_e2, jaev_mult);
00631 
00632   boost::property_map<c_graph_t, EdgeType>::type eType = get (EdgeType(), angelLCG);
00633 
00634   //test for absorption
00635   c_graph_t::edge_t fill_or_absorb_e;
00636   bool found_absorb_e;
00637   tie (fill_or_absorb_e, found_absorb_e) = edge (source (e1, angelLCG), target (e2, angelLCG), angelLCG);
00638   if (found_absorb_e) { // absorption
00639     //create add vertex and absorb vertex, connect them up
00640     xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex& jaev_add = new_jae.addVertex();
00641     jaev_add.setOperation (xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex::ADD_OP);
00642     xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex& jaev_absorb_e = new_jae.addVertex();
00643     setJaevRef (fill_or_absorb_e, jaev_absorb_e, angelLCG, edge_ref_list);
00644     new_jae.addEdge(jaev_absorb_e, jaev_add);
00645     new_jae.addEdge(jaev_mult, jaev_add);
00646 
00647     // reset reference for the absorb edge
00648     removeRef (fill_or_absorb_e, angelLCG, edge_ref_list);
00649     EdgeRef_t absorb_e_ref (fill_or_absorb_e, &jaev_add);
00650     edge_ref_list.push_back(absorb_e_ref);
00651 
00652     // set edge type for absorption edge
00653     if (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE)       eType[fill_or_absorb_e] = VARIABLE_EDGE;
00654     else if (eType[fill_or_absorb_e] != VARIABLE_EDGE)                  eType[fill_or_absorb_e] = CONSTANT_EDGE;
00655   }
00656   else { // fill-in
00657     tie (fill_or_absorb_e, found_absorb_e) = add_edge (source (e1, angelLCG), target (e2, angelLCG), angelLCG.next_edge_number++, angelLCG);
00658     EdgeRef_t fill_e_ref (fill_or_absorb_e, &jaev_mult);
00659     edge_ref_list.push_back(fill_e_ref); //point the fill-in edge at the top of the new JAE
00660 
00661     // set edge type for new fill-in edge
00662     if (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE)       eType[fill_or_absorb_e] = VARIABLE_EDGE;
00663     else if (eType[e1] == UNIT_EDGE && eType[e2] == UNIT_EDGE)          eType[fill_or_absorb_e] = UNIT_EDGE;
00664     else                                                                eType[fill_or_absorb_e] = CONSTANT_EDGE;
00665   }
00666   
00667   if (eType[e1] == UNIT_EDGE || eType[e2] == UNIT_EDGE)
00668     return 0;
00669   else
00670     return 1;
00671 } // end multiply_edge_pair_directly
00672 
00673 unsigned int front_eliminate_edge_directly (c_graph_t::edge_t e,
00674                                             c_graph_t& angelLCG,
00675                                             list<EdgeRef_t>& edge_ref_list,
00676                                             xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionList& jae_list) {
00677 #ifndef NDEBUG
00678   cout << "front eliminating edge " << e << endl;
00679 #endif
00680 
00681   unsigned int cost = 0;
00682   c_graph_t::vertex_t tgt = target (e, angelLCG);
00683   vector<c_graph_t::edge_t> tgtOutEdges;
00684   c_graph_t::oei_t oei, oe_end;
00685 
00686   // save out-edges of tgt in a vector, as pointers become invalidated
00687   for (tie (oei, oe_end) = out_edges (tgt, angelLCG); oei != oe_end; ++oei)
00688     tgtOutEdges.push_back(*oei);
00689 
00690   // multiply all edge pairs
00691   for (size_t i = 0; i < tgtOutEdges.size(); i++)
00692     cost += multiply_edge_pair_directly (e, tgtOutEdges[i], angelLCG, edge_ref_list, jae_list);
00693 
00694   // remove tgt of e and incident edges if it becomes isolated
00695   if (in_degree (tgt, angelLCG) == 1)
00696     for (size_t i = 0; i < tgtOutEdges.size(); i++) {
00697       removeRef (tgtOutEdges[i], angelLCG, edge_ref_list);
00698       remove_edge (tgtOutEdges[i], angelLCG);
00699     }
00700 
00701   removeRef (e, angelLCG, edge_ref_list);
00702   remove_edge (e, angelLCG);
00703   return cost;
00704 } // end front_eliminate_edge_directly()
00705 
00706 unsigned int back_eliminate_edge_directly (c_graph_t::edge_t e,
00707                                            c_graph_t& angelLCG,
00708                                            list<EdgeRef_t>& edge_ref_list,
00709                                            xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionList& jae_list) {
00710 #ifndef NDEBUG
00711   cout << "back eliminating edge " << e << endl;
00712 #endif
00713 
00714   unsigned int cost = 0;
00715   c_graph_t::vertex_t src = source (e, angelLCG);
00716   vector<c_graph_t::edge_t> srcInEdges;
00717   c_graph_t::iei_t iei, ie_end;  
00718 
00719   // save in-edges of src in a vector, as pointers become invalidated
00720   for (tie (iei, ie_end) = in_edges (src, angelLCG); iei != ie_end; ++iei)
00721       srcInEdges.push_back(*iei);
00722 
00723   // multiply all edge pairs
00724   for (size_t i = 0; i < srcInEdges.size(); i++)
00725     cost += multiply_edge_pair_directly (srcInEdges[i], e, angelLCG, edge_ref_list, jae_list);
00726 
00727   // remove src of e and incident edges if it becomes isolated and isn't a dependent
00728   if (out_degree (src, angelLCG) == 1 && vertex_type (src, angelLCG) != dependent)
00729     for (size_t i = 0; i < srcInEdges.size(); i++) {
00730       removeRef (srcInEdges[i], angelLCG, edge_ref_list);
00731       remove_edge (srcInEdges[i], angelLCG);
00732     }
00733 
00734   removeRef (e, angelLCG, edge_ref_list);
00735   remove_edge (e, angelLCG);
00736   return cost;
00737 } // end back_eliminate_edge_directly()
00738 
00739 unsigned int pair_elim (c_graph_t::edge_t e1,
00740                         c_graph_t::edge_t e2,
00741                         c_graph_t& angelLCG,
00742                         const elimSeq_cost_t& currentElimSeq,
00743                         refillDependenceMap_t& refillDependences) {
00744   boost::property_map<c_graph_t, EdgeType>::type eType = get (EdgeType(), angelLCG);
00745   c_graph_t::edge_t fill_or_absorb_e;
00746   bool found_absorb_e;
00747 
00748   // determine whether absorption edge is present
00749   tie (fill_or_absorb_e, found_absorb_e) = edge (source (e1, angelLCG), target (e2, angelLCG), angelLCG);
00750   if (found_absorb_e) { // absorption - all we have to do is set the edge type for the absorption edge
00751     if (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE)       eType[fill_or_absorb_e] = VARIABLE_EDGE;
00752     else if (eType[fill_or_absorb_e] != VARIABLE_EDGE)                  eType[fill_or_absorb_e] = CONSTANT_EDGE;
00753   }
00754   else { // fill-in
00755     
00756     // check for refill.  If found, add tgt to dependence vertex set for respective edge (from src to succ of tgt)
00757     for (size_t c = 0; c < currentElimSeq.edgeElimVector.size(); c++) {
00758       unsigned int i = currentElimSeq.edgeElimVector[c].getSource();
00759       unsigned int j = currentElimSeq.edgeElimVector[c].getTarget();
00760       if (source (e1, angelLCG) == i && target (e2, angelLCG) == j) {
00761 #ifndef NDEBUG
00762         cout << endl << "refilledge (" << i << "," << j << "), adding this information to the refillDependences map..." << endl << endl;
00763 #endif
00764         // add vertex to the refill dependence set for the refilled edge
00765         refillDependenceMap_t::iterator depMap_i = refillDependences.find(make_pair(i, j));
00766         if (depMap_i == refillDependences.end()) {
00767 #ifndef NDEBUG
00768           cout << "the edge was not found as a map key.  Creating new map key and empty set..." << endl;
00769 #endif
00770           // add the edge to the map if it isnt there
00771           depMap_i = refillDependences.insert( std::make_pair(make_pair(i, j), vertex_set_t()) ).first;
00772           currentElimSeq.revealedNewDependence = true;
00773         }
00774         bool wasntPresent = (depMap_i->second).insert(target (e1, angelLCG)).second; // add the vertex to the depSet for the current edge
00775         if (wasntPresent) currentElimSeq.revealedNewDependence = true;
00776         // refill has already been found for this edge, so break
00777         break;
00778       } // end if fill edge is found to have been previously eliminated (refill)
00779     } // end all previous elims in current sequence
00780 
00781     // create the fill-in edge and set it's edge type
00782     tie (fill_or_absorb_e, found_absorb_e) = add_edge (source (e1, angelLCG), target (e2, angelLCG), angelLCG.next_edge_number++, angelLCG);
00783     if (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE)       eType[fill_or_absorb_e] = VARIABLE_EDGE;
00784     else if (eType[e1] == UNIT_EDGE && eType[e2] == UNIT_EDGE)          eType[fill_or_absorb_e] = UNIT_EDGE;
00785     else                                                                eType[fill_or_absorb_e] = CONSTANT_EDGE;
00786   } // end fill-in
00787 
00788   if (eType[e1] == UNIT_EDGE || eType[e2] == UNIT_EDGE)
00789     return 0;
00790   else
00791     return 1;
00792 } // end pair_elim()
00793 
00794 unsigned int front_elim (c_graph_t::edge_t e,
00795                          c_graph_t& angelLCG,
00796                          const elimSeq_cost_t& currentElimSeq,
00797                          refillDependenceMap_t& refillDependences) {
00798 #ifndef NDEBUG
00799   cout << "front eliminating edge " << e << endl;
00800 #endif
00801 
00802   unsigned int cost = 0;
00803   c_graph_t::oei_t oei, oe_end;
00804   vector<c_graph_t::edge_t> tgtOutEdges;
00805 
00806   // save out-edges of tgt in a vector, as pointers become invalidated
00807   for (tie (oei, oe_end) = out_edges (target (e, angelLCG), angelLCG); oei != oe_end; ++oei)
00808     tgtOutEdges.push_back(*oei);
00809 
00810   for (size_t i = 0; i < tgtOutEdges.size(); i++)
00811     cost += pair_elim (e, tgtOutEdges[i], angelLCG, currentElimSeq, refillDependences);
00812  
00813   // if elimination isolates the target, remove vertex and incident edges
00814   if (in_degree (target (e, angelLCG), angelLCG) == 1)
00815     for (size_t i = 0; i < tgtOutEdges.size(); i++)
00816       remove_edge (tgtOutEdges[i], angelLCG);
00817 
00818   remove_edge (e, angelLCG);
00819   return cost;
00820 } // end front_elim() 
00821 
00822 unsigned int back_elim (c_graph_t::edge_t e,
00823                         c_graph_t& angelLCG,
00824                         const elimSeq_cost_t& currentElimSeq,
00825                         refillDependenceMap_t& refillDependences) {
00826 #ifndef NDEBUG
00827   cout << "back eliminating edge " << e << endl;
00828 #endif
00829 
00830   unsigned int cost = 0;
00831   c_graph_t::iei_t iei, ie_end;
00832   vector<c_graph_t::edge_t> srcInEdges;
00833 
00834   // save in-edges of src in a vector, as pointers become invalidated
00835   for (tie (iei, ie_end) = in_edges (source (e, angelLCG), angelLCG); iei != ie_end; ++iei)
00836     srcInEdges.push_back(*iei);
00837 
00838   for (size_t i = 0; i < srcInEdges.size(); i++)
00839     cost += pair_elim (srcInEdges[i], e, angelLCG, currentElimSeq, refillDependences);
00840 
00841   // remove src of e and incident edges if it becomes isolated and isn't a dependent
00842   if (out_degree (source (e, angelLCG), angelLCG) == 1 && vertex_type (source (e, angelLCG), angelLCG) != dependent)
00843     for (size_t i = 0; i < srcInEdges.size(); i++)
00844       remove_edge (srcInEdges[i], angelLCG);
00845 
00846   remove_edge (e, angelLCG);
00847   return cost;
00848 } // end back_elim()
00849 
00850 unsigned int pairElim_noJAE (c_graph_t::edge_t e1,
00851                              c_graph_t::edge_t e2,
00852                              c_graph_t& angelLCG,
00853                              const transformationSeq_cost_t* currentTransformationSequence,
00854                              refillDependenceMap_t& refillDependences) {
00855   boost::property_map<c_graph_t, EdgeType>::type eType = get (EdgeType(), angelLCG);
00856   c_graph_t::edge_t fill_or_absorb_e;
00857   bool found_absorb_e;
00858 
00859   // check for refill.  If found, add tgt to dependence vertex set for respective edge (from src to succ of tgt)
00860   for (size_t c = 0; c < currentTransformationSequence->transformationVector.size(); c++) {
00861     if (currentTransformationSequence->transformationVector[c].isRerouting())
00862       continue; // ignore reroutings
00863 
00864     unsigned int i = currentTransformationSequence->transformationVector[c].getEdgeElim().getSource();
00865     unsigned int j = currentTransformationSequence->transformationVector[c].getEdgeElim().getTarget();
00866 
00867     // the fill/absorb edge was previously eliminated
00868     if (source (e1, angelLCG) == i && target (e2, angelLCG) == j) {
00869 #ifndef NDEBUG
00870       cout << endl << "refilledge (" << i << "," << j << "), adding this information to the refillDependences map..." << endl << endl;
00871 #endif
00872       // add vertex to the refill dependence set for the refilled edge
00873       refillDependenceMap_t::iterator depMap_i = refillDependences.find(make_pair(i, j));
00874       if (depMap_i == refillDependences.end()) { // map doesn't contain a key for the refilled edge
00875 #ifndef NDEBUG
00876         cout << "the edge was not found as a map key.  Creating new map key with empty vertex set..." << endl;
00877 #endif
00878         // add the edge to the map if it isnt there
00879         depMap_i = refillDependences.insert( std::make_pair(make_pair(i, j), vertex_set_t()) ).first;
00880         currentTransformationSequence->revealedNewDependence = true; // edge newly added as map key
00881       }
00882 
00883       // add the vertex to the depSet for the current edge
00884       if ((depMap_i->second).insert(target (e1, angelLCG)).second)
00885         currentTransformationSequence->revealedNewDependence = true; // vertex newly added to dependence set for edge
00886 
00887       break; // refill has already been found for this edge, so break
00888     } // end if fill/absorb edge is found to have been previously eliminated (refill)
00889   } // end all previous elims in current sequence
00890 
00891   // determine whether absorption edge is present
00892   tie (fill_or_absorb_e, found_absorb_e) = edge (source (e1, angelLCG), target (e2, angelLCG), angelLCG);
00893   if (found_absorb_e) { // absorption: all we have to do is set the edge type for the absorption edge
00894     if (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE)       eType[fill_or_absorb_e] = VARIABLE_EDGE;
00895     else if (eType[fill_or_absorb_e] != VARIABLE_EDGE)                  eType[fill_or_absorb_e] = CONSTANT_EDGE;
00896   } // end absorption
00897   else { // fill-in: create new edge and set it's edge type
00898     tie (fill_or_absorb_e, found_absorb_e) = add_edge (source (e1, angelLCG), target (e2, angelLCG), angelLCG.next_edge_number++, angelLCG);
00899     if (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE)       eType[fill_or_absorb_e] = VARIABLE_EDGE;
00900     else if (eType[e1] == UNIT_EDGE && eType[e2] == UNIT_EDGE)          eType[fill_or_absorb_e] = UNIT_EDGE;
00901     else                                                                eType[fill_or_absorb_e] = CONSTANT_EDGE;
00902   } // end fill-in
00903 
00904   if (eType[e1] == UNIT_EDGE || eType[e2] == UNIT_EDGE)
00905     return 0;
00906   else return 1;
00907 } // end pairElim_noJAE()
00908 
00909 unsigned int frontEdgeElimination_noJAE (c_graph_t::edge_t e,
00910                                          c_graph_t& angelLCG,
00911                                          const transformationSeq_cost_t* currentTransformationSequence,
00912                                          refillDependenceMap_t& refillDependences) {
00913 #ifndef NDEBUG
00914   cout << "front eliminating edge " << e << "\t(without creating any JAEs)" << endl;
00915 #endif
00916 
00917   unsigned int cost = 0;
00918   c_graph_t::oei_t oei, oe_end;
00919   vector<c_graph_t::edge_t> tgtOutEdges;
00920 
00921   // save out-edges of tgt in a vector, as pointers become invalidated
00922   for (tie (oei, oe_end) = out_edges (target (e, angelLCG), angelLCG); oei != oe_end; ++oei)
00923     tgtOutEdges.push_back(*oei);
00924 
00925   for (size_t i = 0; i < tgtOutEdges.size(); i++)
00926     cost += pairElim_noJAE (e, tgtOutEdges[i], angelLCG, currentTransformationSequence, refillDependences);
00927  
00928   // if elimination isolates the target, remove vertex and incident edges
00929   if (in_degree (target (e, angelLCG), angelLCG) == 1)
00930     for (size_t i = 0; i < tgtOutEdges.size(); i++)
00931       remove_edge (tgtOutEdges[i], angelLCG);
00932 
00933   remove_edge (e, angelLCG);
00934   return cost;
00935 } // end frontEdgeElimination_noJAE()
00936 
00937 unsigned int backEdgeElimination_noJAE (c_graph_t::edge_t e,
00938                                          c_graph_t& angelLCG,
00939                                          const transformationSeq_cost_t* currentTransformationSequence,
00940                                          refillDependenceMap_t& refillDependences) {
00941 #ifndef NDEBUG
00942   cout << "back eliminating edge " << e << "\t(without creating any JAEs)" << endl;
00943 #endif
00944 
00945   unsigned int cost = 0;
00946   c_graph_t::iei_t iei, ie_end;
00947   vector<c_graph_t::edge_t> srcInEdges;
00948 
00949   // save in-edges of src in a vector, as pointers become invalidated
00950   for (tie (iei, ie_end) = in_edges (source (e, angelLCG), angelLCG); iei != ie_end; ++iei)
00951     srcInEdges.push_back(*iei);
00952 
00953   for (size_t i = 0; i < srcInEdges.size(); i++)
00954     cost += pairElim_noJAE (srcInEdges[i], e, angelLCG, currentTransformationSequence, refillDependences);
00955 
00956   // remove src of e and incident edges if it becomes isolated and isn't a dependent
00957   if (out_degree (source (e, angelLCG), angelLCG) == 1 && vertex_type (source (e, angelLCG), angelLCG) != dependent)
00958     for (size_t i = 0; i < srcInEdges.size(); i++)
00959       remove_edge (srcInEdges[i], angelLCG);
00960 
00961   remove_edge (e, angelLCG);
00962   return cost;
00963 } // end backEdgeElimination_noJAE()
00964 
00965 #endif // USEXAIFBOOSTER
00966 
00967 } // namespace angel
00968 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines