angel  mercurial changeset:
src/reroutings.cpp
Go to the documentation of this file.
00001 /*
00002 #############################################################
00003 # This file is part of angel released under the BSD license #
00004 # The full COPYRIGHT notice can be found in the top         #
00005 # level directory of the angel distribution                 #
00006 #############################################################
00007 */
00008 #ifdef USEXAIFBOOSTER
00009 
00010 #include "angel/include/angel_tools.hpp"
00011 #include "angel/include/eliminations.hpp"
00012 #include "angel/include/reroutings.hpp"
00013 
00014 using namespace std;
00015 using namespace boost;
00016 using namespace xaifBoosterCrossCountryInterface;
00017 
00018 namespace angel {
00019 
00020 void reroutable_edges (c_graph_t& angelLCG,
00021                        vector<edge_reroute_t>& erv) {
00022   erv.clear();
00023   set<c_graph_t::vertex_t> downset, upset;
00024   c_graph_t::edge_t decrement_e;
00025   bool found_decrement_e;
00026   c_graph_t::ei_t ei, e_end;
00027   c_graph_t::iei_t iei, ie_end;
00028   c_graph_t::oei_t oei, oe_end;
00029   property_map<pure_c_graph_t, VertexVisited>::type visited = get(VertexVisited(), angelLCG);
00030   c_graph_t::vi_t cleari, clear_end;
00031 
00032   // iterate over all edges; consider each to be pre-routed and post-routed
00033   for (tie (ei, e_end) = edges (angelLCG); ei != e_end; ++ei) {
00034     c_graph_t::edge_t e = *ei;
00035 
00036     // check for preroutability
00037     if (in_degree (target (e, angelLCG), angelLCG) > 1) {
00038       // iterate over possible pivots (inedges of tgt(e))
00039       for (tie (iei, ie_end) = in_edges (target (*ei, angelLCG), angelLCG); iei != ie_end; ++iei) {
00040         c_graph_t::edge_t pivot_e = *iei;
00041         // skip the edge we're considering for rerouting
00042         if (source (pivot_e, angelLCG) == source (e, angelLCG)) continue;
00043         // the source of the pivot edge can't be an independent (we add an edge into it)
00044         if (in_degree (source (pivot_e, angelLCG), angelLCG) == 0) continue;
00045         // ensure that no decrement fill-in is created
00046         for (tie(oei, oe_end) = out_edges(source(pivot_e, angelLCG), angelLCG); oei != oe_end; ++oei) {
00047           if (*oei == pivot_e) continue; // skip the pivot edge
00048           tie(decrement_e, found_decrement_e) = edge(source(e, angelLCG), target(*oei, angelLCG), angelLCG);
00049           if (!found_decrement_e) break; // decrement fill-in has been found (not allowed)
00050         }
00051         if (oei != oe_end) continue; // this will be true iff some decrement fill is detected
00052 
00053         // ensure that we cant reach src(e) from src(pivot_e) (would create cycle)
00054         // first clear visited list
00055         for (tie(cleari, clear_end) = vertices(angelLCG); cleari != clear_end; ++cleari) visited[*cleari] = false;
00056         if (reachable (source(pivot_e, angelLCG), source(e, angelLCG), angelLCG)) continue;
00057         erv.push_back (edge_reroute_t (e, pivot_e, true));
00058 
00059       } // end all pivot candidates
00060     } // end check for pre-routability
00061 
00062     // check for postroutability
00063     if (out_degree (source (e, angelLCG), angelLCG) > 1) {
00064       // iterate over possible pivots (outedges of src(e))
00065       for (tie (oei, oe_end) = out_edges (source (e, angelLCG), angelLCG); oei != oe_end; ++oei) {
00066         c_graph_t::edge_t pivot_e = *oei;
00067         // skip the edge we're considering for rerouting
00068         if (target (pivot_e, angelLCG) == target (e, angelLCG)) continue;
00069         // tgt(pivot_e) can't be a dependent vertex (we add an edge out of it)
00070         if (out_degree (target (pivot_e, angelLCG), angelLCG) == 0) continue;
00071         // ensure that no decrement fill-in is created
00072         for (tie(iei, ie_end) = in_edges(target(pivot_e, angelLCG), angelLCG); iei != ie_end; ++iei) {
00073           if (*iei == pivot_e) continue; // skip the pivot edge
00074           tie(decrement_e, found_decrement_e) = edge(source(*iei, angelLCG), target(e, angelLCG), angelLCG);
00075           if (!found_decrement_e) break; // decrement fill-in has been found (not allowed)
00076         }
00077         if (iei != ie_end) continue; // this will be true iff some decrement fill is detected
00078 
00079         // ensure that we cant reach tgt(pivot_e) from tgt(e) (would create cycle)
00080         // first clear visited list
00081         for (tie(cleari, clear_end) = vertices(angelLCG); cleari != clear_end; ++cleari) visited[*cleari] = false;
00082         if (reachable (target(e, angelLCG), target(pivot_e, angelLCG), angelLCG)) continue;
00083         erv.push_back (edge_reroute_t (e, pivot_e, false));
00084 
00085       } // end all pivot candidates
00086     } // end check for postroutability
00087     
00088   } // end all edges in angelLCG
00089 
00090 #ifndef NDEBUG
00091   cout << "     There are " << erv.size() << " reroutings in G" << endl;
00092 #endif
00093   
00094 } // end reroutable_edges()
00095 
00096 unsigned int reroutable_edges(c_graph_t& angelLCG,
00097                               vector<Rerouting>& allReroutingsV) {
00098   allReroutingsV.clear();
00099   vector <edge_reroute_t> tempRerouteTV;
00100   reroutable_edges(angelLCG, tempRerouteTV);
00101   if (tempRerouteTV.empty())
00102     return 0;
00103 
00104   for (size_t i = 0; i < tempRerouteTV.size(); i++)
00105    allReroutingsV.push_back(Rerouting (tempRerouteTV[i], angelLCG));
00106   return allReroutingsV.size();
00107 } // end reroutable_edges()
00108 
00109 int reroute_effect (const edge_reroute_t er,
00110                     const c_graph_t& angelLCG,
00111                     const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
00112                     bool& incrementIsTrivial) {
00113 
00114   c_graph_t::edge_t e = er.e;
00115   c_graph_t::edge_t pe = er.pivot_e;
00116   c_graph_t::iei_t iei, ie_end;
00117   c_graph_t::oei_t oei, oe_end;
00118   boost::property_map<c_graph_t, EdgeType>::const_type eType = get(EdgeType(), angelLCG);
00119   c_graph_t::edge_t increment_e, decrement_e;
00120   bool found_increment_e, found_decrement_e;
00121 
00122   int nontrivial_edge_change = 0;
00123 
00124   // consider the loss of the rerouted edge
00125   if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS
00126   || (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[e] != UNIT_EDGE)
00127   || (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[e] == VARIABLE_EDGE)) nontrivial_edge_change--;
00128 
00129   if (er.isPre) { // pre-routing
00130     // DECREMENT EDGES: No fill-in, but we allow when a decrement edge goes from trivial to nontrivial
00131     for (tie(oei, oe_end) = out_edges(source(pe, angelLCG), angelLCG); oei != oe_end; ++oei) {
00132       if (*oei == pe) continue; // skip the pivot edge
00133       tie (decrement_e, found_decrement_e) = edge(source(e, angelLCG), target(*oei, angelLCG), angelLCG);
00134       THROW_EXCEPT_MACRO (!found_decrement_e, consistency_exception, "Pre-routing passed to filter causes decrement fill-in");  
00135       // no awareness: no effect
00136       // unit awareness:
00137       if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[decrement_e] == UNIT_EDGE) nontrivial_edge_change++;
00138       // constant awareness:
00139       else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[decrement_e] != VARIABLE_EDGE)
00140         if (eType[e] == VARIABLE_EDGE || eType[pe] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE) nontrivial_edge_change++;
00141     } // end all outedges of src(pivot_e)
00142 
00143     // INCREMENT EDGE: change occurs only when increment edge was nontrivial to begin with
00144     tie(increment_e, found_increment_e) = edge(target(pe, angelLCG), target(e, angelLCG), angelLCG);
00145     if (found_increment_e) { // increment absorption
00146       if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) incrementIsTrivial = false;
00147       else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS) {
00148         incrementIsTrivial = false; // because of absorption (addition) it will be nontrivial no matter what
00149         if (eType[increment_e] == UNIT_EDGE) nontrivial_edge_change++;
00150       } // end unit awareness
00151       else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS) {
00152         // if ANY involved edge is variable, then increment edge is nontrivial
00153         if (eType[increment_e] == VARIABLE_EDGE || eType[e] == VARIABLE_EDGE || eType[pe] == VARIABLE_EDGE) incrementIsTrivial = false;
00154         else incrementIsTrivial = true;
00155         // if the result is nontrivial, but the increment edge WAS trivial to begin with, our nontriv count goes up
00156         if (eType[increment_e] != VARIABLE_EDGE && !incrementIsTrivial) nontrivial_edge_change++;
00157       } // end constant awareness
00158     } // end increment absorption
00159     else { // increment fill-in
00160       if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) {
00161         nontrivial_edge_change++;
00162         incrementIsTrivial = false;
00163       } // end no awareness
00164       else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS) {
00165         if (eType[e] != UNIT_EDGE || eType[pe] != UNIT_EDGE) {
00166           nontrivial_edge_change++;
00167           incrementIsTrivial = false;
00168         }
00169         else incrementIsTrivial = true;
00170       } // end unit awareness
00171       else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS) {
00172         if (eType[e] == VARIABLE_EDGE || eType[pe] == VARIABLE_EDGE) {
00173           nontrivial_edge_change++;
00174           incrementIsTrivial = false;
00175         }
00176         else incrementIsTrivial = true;
00177       } // end constant awareness
00178     } // end increment fill-in
00179 
00180   } // end pre-routing
00181   else { // post-routing
00182 
00183     // DECREMENT EDGES: No fill-in, but we allow when a decrement edge goes from trivial to nontrivial
00184     for (tie(iei, ie_end) = in_edges(target(pe, angelLCG), angelLCG); iei != ie_end; ++iei) {
00185       if (*iei == pe) continue; // skip the pivot edge
00186       tie (decrement_e, found_decrement_e) = edge (source(*iei, angelLCG), target(e, angelLCG), angelLCG);
00187       THROW_EXCEPT_MACRO (!found_decrement_e, consistency_exception, "Post-routing passed to filter causes decrement fill-in"); 
00188       // no awareness: no effect
00189       // unit awareness:
00190       if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[decrement_e] == UNIT_EDGE) nontrivial_edge_change++;
00191       // constant awareness:
00192       else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[decrement_e] != VARIABLE_EDGE)
00193         if (eType[e] == VARIABLE_EDGE || eType[pe] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE) nontrivial_edge_change++;
00194     } // end all outedges of src(pivot_e)
00195 
00196     // INCREMENT EDGE: change occurs only when increment edge was nontrivial to begin with
00197     tie(increment_e, found_increment_e) = edge(target(pe, angelLCG), target(e, angelLCG), angelLCG);
00198     if (found_increment_e) { // increment absorption
00199       if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) incrementIsTrivial = false;
00200       else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS) { // increase iff edge was trivial to begin with
00201         incrementIsTrivial = false; // because of absorption (addition) it will be nontrivial no matter what
00202         if (eType[increment_e] == UNIT_EDGE) nontrivial_edge_change++;
00203       } // end unit awareness
00204       else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS) { // if ANY involved edge is variable, then increment edge is nontrivial
00205         if (eType[increment_e] == VARIABLE_EDGE || eType[e] == VARIABLE_EDGE || eType[pe] == VARIABLE_EDGE) incrementIsTrivial = false;
00206         else incrementIsTrivial = true;
00207         if (eType[increment_e] != VARIABLE_EDGE && !incrementIsTrivial) nontrivial_edge_change++;
00208       } // end constant awareness
00209     } // end increment absorption
00210     else { // increment fill-in
00211       if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS) {
00212         nontrivial_edge_change++;
00213         incrementIsTrivial = false;
00214       } // end no awareness
00215       else if (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS) {
00216         if (eType[e] != UNIT_EDGE || eType[pe] != UNIT_EDGE) {
00217           nontrivial_edge_change++;
00218           incrementIsTrivial = false;
00219         }
00220         else incrementIsTrivial = true;
00221       } // end unit awareness
00222       else if (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS) {
00223         if (eType[e] == VARIABLE_EDGE || eType[pe] == VARIABLE_EDGE) {
00224           nontrivial_edge_change++;
00225           incrementIsTrivial = false;
00226         }
00227         else incrementIsTrivial = true;
00228       } // end constant awareness
00229     } // end increment fill-in
00230 
00231   } // end post-routing
00232 
00233   return nontrivial_edge_change;
00234 } // end reroute_effect()
00235 
00236 // pre-/post-routing an edge cannot isolate a vertex
00237 unsigned int preroute_edge_directly (edge_reroute_t er,
00238                                      c_graph_t& angelLCG,
00239                                      list<EdgeRef_t>& edge_ref_list,
00240                                      JacobianAccumulationExpressionList& jae_list) {
00241   #ifndef NDEBUG
00242     cout << "prerouting edge " << er.e << " about pivot edge " << er.pivot_e << "\t(and creating the corresponding JAEs)" << endl;
00243   #endif
00244 
00245   unsigned int cost = 0;
00246   boost::property_map<c_graph_t, EdgeType>::type eType = get(EdgeType(), angelLCG);
00247   c_graph_t::iei_t iei, ie_end; 
00248   c_graph_t::oei_t oei, oe_end; 
00249 
00250   JacobianAccumulationExpression& new_jae = jae_list.addExpression();
00251   // Increment the edge from the source of e to to v by the quotient e/pivot_e (create it if it doesnt exist)
00252   JacobianAccumulationExpressionVertex& jaev_divide = new_jae.addVertex();
00253   //jaev_divide.setOperation (JacobianAccumulationExpressionVertex::DIVIDE_OP);
00254   jaev_divide.setOperation (JacobianAccumulationExpressionVertex::ADD_OP);
00255   JacobianAccumulationExpressionVertex& jaev_e = new_jae.addVertex();
00256   JacobianAccumulationExpressionVertex& jaev_pivot_e = new_jae.addVertex();
00257   setJaevRef (er.e, jaev_e, angelLCG, edge_ref_list);
00258   setJaevRef (er.pivot_e, jaev_pivot_e, angelLCG, edge_ref_list);
00259   new_jae.addEdge(jaev_e, jaev_divide);
00260   new_jae.addEdge(jaev_pivot_e, jaev_divide);
00261 
00262   // INCREMENT EDGE
00263   bool found_increment_e;
00264   c_graph_t::edge_t increment_e;
00265   tie (increment_e, found_increment_e) = edge (source (er.e, angelLCG), source (er.pivot_e, angelLCG), angelLCG);
00266   if (found_increment_e) { // increment absorption
00267     JacobianAccumulationExpressionVertex& jaev_increment_e = new_jae.addVertex();
00268     setJaevRef (increment_e, jaev_increment_e, angelLCG, edge_ref_list);
00269     JacobianAccumulationExpressionVertex& jaev_add = new_jae.addVertex();
00270     jaev_add.setOperation (JacobianAccumulationExpressionVertex::ADD_OP);
00271     new_jae.addEdge(jaev_increment_e, jaev_add);
00272     new_jae.addEdge(jaev_divide, jaev_add);
00273 
00274     //point increment_e at the top of the new JAE
00275     removeRef (increment_e, angelLCG, edge_ref_list);
00276     EdgeRef_t new_increment_e_ref (increment_e, &jaev_add);
00277     edge_ref_list.push_back(new_increment_e_ref);
00278 
00279     //set edge type for absorption increment edge
00280     if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE)     eType[increment_e] = VARIABLE_EDGE;
00281     else if (eType[increment_e] != VARIABLE_EDGE)                               eType[increment_e] = CONSTANT_EDGE;
00282   } // end increment absorption
00283   else { //no increment edge was already present (fill-in)
00284     tie (increment_e, found_increment_e) = add_edge (source (er.e, angelLCG), source (er.pivot_e, angelLCG), angelLCG.next_edge_number++, angelLCG);
00285 
00286     // point the new edge at the divide operation in the new JAE
00287     EdgeRef_t new_increment_e_ref (increment_e, &jaev_divide);
00288     edge_ref_list.push_back(new_increment_e_ref);
00289 
00290     //set edge type for fill-in increment edge
00291     if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE)     eType[increment_e] = VARIABLE_EDGE;
00292     else if (eType[er.e] == UNIT_EDGE && eType[er.pivot_e] == UNIT_EDGE)        eType[increment_e] = UNIT_EDGE;
00293     else                                                                        eType[increment_e] = CONSTANT_EDGE;
00294   }
00295 
00296   // determine cost of creating increment edge (we divide e/pivot_e, so trivial iff pivot_e is unit)
00297   if (eType[er.pivot_e] != UNIT_EDGE)
00298     cost++;
00299 
00300   // DECREMENT OPERATIONS
00301 
00302   // for all successors of v (except the target of e), perform decrement operations on edges from src_of_e to 
00303   for (tie (oei, oe_end) = out_edges (source (er.pivot_e, angelLCG), angelLCG); oei != oe_end; oei++) {
00304     if (target (*oei, angelLCG) == target (er.e, angelLCG)) continue;
00305     JacobianAccumulationExpression& new_jae = jae_list.addExpression();
00306     JacobianAccumulationExpressionVertex& jaev_divide = new_jae.addVertex();
00307     //jaev_divide.setOperation (JacobianAccumulationExpressionVertex::DIVIDE_OP);
00308     jaev_divide.setOperation (JacobianAccumulationExpressionVertex::MULT_OP);
00309     JacobianAccumulationExpressionVertex& jaev_e = new_jae.addVertex();
00310     JacobianAccumulationExpressionVertex& jaev_pivot_e = new_jae.addVertex();
00311     setJaevRef (er.e, jaev_e, angelLCG, edge_ref_list);
00312     setJaevRef (er.pivot_e, jaev_pivot_e, angelLCG, edge_ref_list);
00313     new_jae.addEdge(jaev_e, jaev_divide);
00314     new_jae.addEdge(jaev_pivot_e, jaev_divide);
00315     // create mult vertex and connect it up
00316     JacobianAccumulationExpressionVertex& jaev_mult = new_jae.addVertex();
00317     jaev_mult.setOperation (JacobianAccumulationExpressionVertex::MULT_OP);
00318     new_jae.addEdge(jaev_divide, jaev_mult);
00319     JacobianAccumulationExpressionVertex& jaev_vout_e = new_jae.addVertex();
00320     setJaevRef (*oei, jaev_vout_e, angelLCG, edge_ref_list);
00321     new_jae.addEdge(jaev_vout_e, jaev_mult);
00322 
00323     bool found_decrement_e;
00324     c_graph_t::edge_t decrement_e;
00325     tie (decrement_e, found_decrement_e) = edge (source (er.e, angelLCG), target (*oei, angelLCG), angelLCG);
00326 
00327     if (found_decrement_e) { // decrement absorption
00328       JacobianAccumulationExpressionVertex& jaev_decrement_e = new_jae.addVertex();
00329       JacobianAccumulationExpressionVertex& jaev_subtract = new_jae.addVertex();
00330       //jaev_subtract.setOperation (JacobianAccumulationExpressionVertex::SUBTRACT_OP);
00331       jaev_subtract.setOperation (JacobianAccumulationExpressionVertex::ADD_OP);
00332       new_jae.addEdge(jaev_mult, jaev_subtract);
00333       new_jae.addEdge(jaev_decrement_e, jaev_subtract);
00334 
00335       // point the decrement edge at the divide operation in the new JAE
00336       removeRef (decrement_e, angelLCG, edge_ref_list);
00337       EdgeRef_t new_decrement_e_ref (decrement_e, &jaev_subtract);
00338       edge_ref_list.push_back(new_decrement_e_ref);
00339 
00340       //set edge type for absorption decrement edge
00341       if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE)
00342         eType[decrement_e] = VARIABLE_EDGE;
00343       else if (eType[decrement_e] != VARIABLE_EDGE)
00344         eType[decrement_e] = CONSTANT_EDGE;
00345     } // end decrement absorption
00346     else { // decrement fill-in
00347       tie (decrement_e, found_decrement_e) = add_edge (source (er.e, angelLCG), target (*oei, angelLCG), angelLCG.next_edge_number++, angelLCG);
00348 
00349       // point the new edge at the divide operation in the new JAE
00350       EdgeRef_t new_decrement_e_ref (decrement_e, &jaev_divide);
00351       edge_ref_list.push_back(new_decrement_e_ref);
00352 
00353       //set edge type for fill-in decrement edge
00354       if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE)
00355         eType[decrement_e] = VARIABLE_EDGE;
00356       else if (eType[er.e] == UNIT_EDGE && eType[er.pivot_e] == UNIT_EDGE && eType[*oei] == UNIT_EDGE)
00357         eType[decrement_e] = UNIT_EDGE;
00358       else
00359         eType[decrement_e] = CONSTANT_EDGE;
00360     }
00361 
00362     // eval cost for decrements: trivial if both e and pivot_e are unit or if decrement is unit
00363     if (!((eType[er.e] == UNIT_EDGE && eType[er.pivot_e] == UNIT_EDGE) || eType[*oei] == UNIT_EDGE))
00364       cost++;
00365   } // end all decrements
00366 
00367   remove_edge (er.e, angelLCG);
00368 
00369   return cost;
00370 } // end preroute_edge_directly()
00371 
00372 unsigned int postroute_edge_directly (edge_reroute_t er,
00373                                       c_graph_t& angelLCG,
00374                                       list<EdgeRef_t>& edge_ref_list,
00375                                       JacobianAccumulationExpressionList& jae_list) {
00376   #ifndef NDEBUG
00377     cout << "postrouting edge " << er.e << " about pivot edge " << er.pivot_e << "\t(and creating the corresponding JAEs)" << endl;
00378   #endif
00379 
00380   unsigned int cost = 0;
00381   boost::property_map<c_graph_t, EdgeType>::type eType = get(EdgeType(), angelLCG);
00382   c_graph_t::iei_t iei, ie_end; 
00383   c_graph_t::oei_t oei, oe_end; 
00384 
00385   // Increment the edge from the source of e to to v by the quotient e/pivot_e (create it if it doesnt exist)
00386   JacobianAccumulationExpression& new_jae = jae_list.addExpression();
00387   JacobianAccumulationExpressionVertex& jaev_divide = new_jae.addVertex();
00388   //jaev_divide.setOperation (JacobianAccumulationExpressionVertex::DIVIDE_OP);
00389   jaev_divide.setOperation (JacobianAccumulationExpressionVertex::ADD_OP);
00390   JacobianAccumulationExpressionVertex& jaev_e = new_jae.addVertex();
00391   JacobianAccumulationExpressionVertex& jaev_pivot_e = new_jae.addVertex();
00392   setJaevRef (er.e, jaev_e, angelLCG, edge_ref_list);
00393   setJaevRef (er.pivot_e, jaev_pivot_e, angelLCG, edge_ref_list);
00394   new_jae.addEdge(jaev_e, jaev_divide);
00395   new_jae.addEdge(jaev_pivot_e, jaev_divide);
00396 
00397   // INCREMENT EDGE
00398   bool found_increment_e;
00399   c_graph_t::edge_t increment_e;
00400   tie (increment_e, found_increment_e) = edge (target (er.pivot_e, angelLCG), target (er.e, angelLCG), angelLCG);
00401   if (found_increment_e) { // increment absorption
00402     JacobianAccumulationExpressionVertex& jaev_increment_e = new_jae.addVertex();
00403     setJaevRef (increment_e, jaev_increment_e, angelLCG, edge_ref_list);
00404     JacobianAccumulationExpressionVertex& jaev_add = new_jae.addVertex();
00405     jaev_add.setOperation (JacobianAccumulationExpressionVertex::ADD_OP);
00406     new_jae.addEdge(jaev_increment_e, jaev_add);
00407     new_jae.addEdge(jaev_divide, jaev_add);
00408 
00409     //point increment_e at the top of the new JAE
00410     removeRef (increment_e, angelLCG, edge_ref_list);
00411     EdgeRef_t new_increment_e_ref (increment_e, &jaev_add);
00412     edge_ref_list.push_back(new_increment_e_ref);
00413 
00414     //set edge type for absorption increment edge
00415     if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE)     eType[increment_e] = VARIABLE_EDGE;
00416     else if (eType[increment_e] != VARIABLE_EDGE)                               eType[increment_e] = CONSTANT_EDGE;
00417   } // end increment absorption
00418   else { //no increment edge was already present (fill-in)
00419     tie (increment_e, found_increment_e) = add_edge (target (er.pivot_e, angelLCG), target (er.e, angelLCG), angelLCG.next_edge_number++, angelLCG);
00420 
00421     // point the new edge at the divide operation in the new JAE
00422     EdgeRef_t new_increment_e_ref (increment_e, &jaev_divide);
00423     edge_ref_list.push_back(new_increment_e_ref);
00424 
00425     //set edge type for fill-in increment edge
00426     if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE)     eType[increment_e] = VARIABLE_EDGE;
00427     else if (eType[er.e] == UNIT_EDGE && eType[er.pivot_e] == UNIT_EDGE)        eType[increment_e] = UNIT_EDGE;
00428     else                                                                        eType[increment_e] = CONSTANT_EDGE;
00429   }
00430 
00431   // determine cost of creating increment edge (we divide e/pivot_e, so trivial iff pivot_e is unit)
00432   if (eType[er.pivot_e] != UNIT_EDGE)
00433     cost++;
00434 
00435   // DECREMENT OPERATIONS
00436 
00437   // for all predecessors of tgt(pivot_e) (except src(e)), perform decrement operations on edges to tgt(e) 
00438   for (tie (iei, ie_end) = in_edges (target (er.pivot_e, angelLCG), angelLCG); iei != ie_end; iei++) {
00439     if (source (*iei, angelLCG) == source (er.pivot_e, angelLCG)) continue;
00440     JacobianAccumulationExpression& new_jae = jae_list.addExpression(); 
00441     JacobianAccumulationExpressionVertex& jaev_divide = new_jae.addVertex();
00442     //jaev_divide.setOperation (JacobianAccumulationExpressionVertex::DIVIDE_OP);
00443     jaev_divide.setOperation(JacobianAccumulationExpressionVertex::MULT_OP);
00444     JacobianAccumulationExpressionVertex& jaev_e = new_jae.addVertex();
00445     JacobianAccumulationExpressionVertex& jaev_pivot_e = new_jae.addVertex();
00446     setJaevRef (er.e, jaev_e, angelLCG, edge_ref_list);
00447     setJaevRef (er.pivot_e, jaev_pivot_e, angelLCG, edge_ref_list);
00448     new_jae.addEdge(jaev_e, jaev_divide);
00449     new_jae.addEdge(jaev_pivot_e, jaev_divide);
00450     // create mult vertex and connect it up
00451     JacobianAccumulationExpressionVertex& jaev_mult = new_jae.addVertex();
00452     jaev_mult.setOperation (JacobianAccumulationExpressionVertex::MULT_OP);
00453     new_jae.addEdge(jaev_divide, jaev_mult);
00454     JacobianAccumulationExpressionVertex& jaev_vin_e = new_jae.addVertex();
00455     setJaevRef (*iei, jaev_vin_e, angelLCG, edge_ref_list);
00456     new_jae.addEdge(jaev_vin_e, jaev_mult);
00457 
00458     bool found_decrement_e;
00459     c_graph_t::edge_t decrement_e;
00460     tie (decrement_e, found_decrement_e) = edge (source (*iei, angelLCG), target (er.e, angelLCG), angelLCG);
00461     if (found_decrement_e) { // decrement absorption
00462       JacobianAccumulationExpressionVertex& jaev_decrement_e = new_jae.addVertex();
00463       JacobianAccumulationExpressionVertex& jaev_subtract = new_jae.addVertex();
00464       //jaev_subtract.setOperation (JacobianAccumulationExpressionVertex::SUBTRACT_OP);
00465       jaev_subtract.setOperation(JacobianAccumulationExpressionVertex::ADD_OP);
00466       new_jae.addEdge(jaev_mult, jaev_subtract);
00467       new_jae.addEdge(jaev_decrement_e, jaev_subtract);
00468 
00469       // point the decrement edge at the divide operation in the new JAE
00470       removeRef (decrement_e, angelLCG, edge_ref_list);
00471       EdgeRef_t new_decrement_e_ref (decrement_e, &jaev_subtract);
00472       edge_ref_list.push_back(new_decrement_e_ref);
00473 
00474       //set edge type for absorption decrement edge
00475       if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)
00476         eType[decrement_e] = VARIABLE_EDGE;
00477       else if (eType[decrement_e] != VARIABLE_EDGE)
00478         eType[decrement_e] = CONSTANT_EDGE;
00479     } // end decrement absorption
00480     else { // decrement fill-in
00481       tie (decrement_e, found_decrement_e) = add_edge (source (*iei, angelLCG), target (er.e, angelLCG), angelLCG.next_edge_number++, angelLCG);
00482 
00483       // point the new edge at the divide operation in the new JAE
00484       EdgeRef_t new_decrement_e_ref (decrement_e, &jaev_divide);
00485       edge_ref_list.push_back(new_decrement_e_ref);
00486 
00487       //set edge type for fill-in decrement edge
00488       if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)
00489         eType[decrement_e] = VARIABLE_EDGE;
00490       else if (eType[er.e] == UNIT_EDGE && eType[er.pivot_e] == UNIT_EDGE && eType[*iei] == UNIT_EDGE)
00491         eType[decrement_e] = UNIT_EDGE;
00492       else
00493         eType[decrement_e] = CONSTANT_EDGE;
00494     }
00495 
00496     // eval cost for decrements: trivial if both e and pivot_e are unit or if decrement is unit
00497     if (!((eType[er.e] == UNIT_EDGE && eType[er.pivot_e] == UNIT_EDGE) || eType[*iei] == UNIT_EDGE))
00498       cost++;
00499   } // end all decrements
00500 
00501   remove_edge (er.e, angelLCG);
00502 
00503   return cost;
00504 } // end postroute_edge_directly()
00505 
00506 unsigned int prerouteEdge_noJAE (edge_reroute_t er,
00507                                  c_graph_t& angelLCG) {
00508   #ifndef NDEBUG
00509     cout << "prerouting edge " << er.e << " about pivot edge " << er.pivot_e << "\t(without creating any JAEs)" << endl;
00510   #endif
00511 
00512   unsigned int cost = 0;
00513   boost::property_map<c_graph_t, EdgeType>::type eType = get(EdgeType(), angelLCG);
00514   c_graph_t::iei_t iei, ie_end; 
00515   c_graph_t::oei_t oei, oe_end; 
00516 
00517   // INCREMENT EDGE
00518   bool found_increment_e;
00519   c_graph_t::edge_t increment_e;
00520   tie (increment_e, found_increment_e) = edge (source (er.e, angelLCG), source (er.pivot_e, angelLCG), angelLCG);
00521   if (found_increment_e) { // increment absorption
00522     //set edge type for absorption increment edge
00523     if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE)     eType[increment_e] = VARIABLE_EDGE;
00524     else if (eType[increment_e] != VARIABLE_EDGE)                               eType[increment_e] = CONSTANT_EDGE;
00525   } // end increment absorption
00526   else { //no increment edge was already present (fill-in)
00527     tie (increment_e, found_increment_e) = add_edge (source (er.e, angelLCG), source (er.pivot_e, angelLCG), angelLCG.next_edge_number++, angelLCG);
00528     //set edge type for fill-in increment edge
00529     if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE)     eType[increment_e] = VARIABLE_EDGE;
00530     else if (eType[er.e] == UNIT_EDGE && eType[er.pivot_e] == UNIT_EDGE)        eType[increment_e] = UNIT_EDGE;
00531     else                                                                        eType[increment_e] = CONSTANT_EDGE;
00532   }
00533   // determine cost of creating increment edge (we divide e/pivot_e, so trivial iff pivot_e is unit)
00534   if (eType[er.pivot_e] != UNIT_EDGE)
00535     cost++;
00536 
00537   // DECREMENT EDGES
00538   for (tie (oei, oe_end) = out_edges (source (er.pivot_e, angelLCG), angelLCG); oei != oe_end; oei++) {
00539     if (target (*oei, angelLCG) == target (er.e, angelLCG)) continue;
00540     bool found_decrement_e;
00541     c_graph_t::edge_t decrement_e;
00542     tie (decrement_e, found_decrement_e) = edge (source (er.e, angelLCG), target (*oei, angelLCG), angelLCG);
00543     if (found_decrement_e) { // decrement absorption
00544       //set edge type for absorption decrement edge
00545       if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE)   eType[decrement_e] = VARIABLE_EDGE;
00546       else if (eType[decrement_e] != VARIABLE_EDGE)                                                             eType[decrement_e] = CONSTANT_EDGE;
00547     } // end decrement absorption
00548     else { // decrement fill-in
00549       tie (decrement_e, found_decrement_e) = add_edge (source (er.e, angelLCG), target (*oei, angelLCG), angelLCG.next_edge_number++, angelLCG);
00550       //set edge type for fill-in decrement edge
00551       if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE || eType[*oei] == VARIABLE_EDGE)   eType[decrement_e] = VARIABLE_EDGE;
00552       else if (eType[er.e] == UNIT_EDGE && eType[er.pivot_e] == UNIT_EDGE && eType[*oei] == UNIT_EDGE)          eType[decrement_e] = UNIT_EDGE;
00553       else                                                                                                      eType[decrement_e] = CONSTANT_EDGE;
00554     }
00555     // eval cost for decrements: trivial if both e and pivot_e are unit or if decrement is unit
00556     if (!((eType[er.e] == UNIT_EDGE && eType[er.pivot_e] == UNIT_EDGE) || eType[*iei] == UNIT_EDGE))
00557       cost++;
00558   } // end all decrements
00559   remove_edge (er.e, angelLCG);
00560   return cost;
00561 } // end prerouteEdge_noJAE()
00562 
00563 unsigned int postrouteEdge_noJAE (edge_reroute_t er,
00564                                   c_graph_t& angelLCG) {
00565   #ifndef NDEBUG
00566     cout << "postrouting edge " << er.e << " about pivot edge " << er.pivot_e << "\t(without creating any JAEs)" << endl;
00567   #endif
00568 
00569   unsigned int cost = 0;
00570   boost::property_map<c_graph_t, EdgeType>::type eType = get(EdgeType(), angelLCG);
00571   c_graph_t::iei_t iei, ie_end; 
00572   c_graph_t::oei_t oei, oe_end; 
00573 
00574   // INCREMENT EDGE
00575   bool found_increment_e;
00576   c_graph_t::edge_t increment_e;
00577   tie (increment_e, found_increment_e) = edge (target (er.pivot_e, angelLCG), target (er.e, angelLCG), angelLCG);
00578   if (found_increment_e) { // increment absorption
00579     //set edge type for absorption increment edge
00580     if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE)     eType[increment_e] = VARIABLE_EDGE;
00581     else if (eType[increment_e] != VARIABLE_EDGE)                               eType[increment_e] = CONSTANT_EDGE;
00582   } // end increment absorption
00583   else { //no increment edge was already present (fill-in)
00584     tie (increment_e, found_increment_e) = add_edge (target (er.pivot_e, angelLCG), target (er.e, angelLCG), angelLCG.next_edge_number++, angelLCG);
00585     //set edge type for fill-in increment edge
00586     if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE)     eType[increment_e] = VARIABLE_EDGE;
00587     else if (eType[er.e] == UNIT_EDGE && eType[er.pivot_e] == UNIT_EDGE)        eType[increment_e] = UNIT_EDGE;
00588     else                                                                        eType[increment_e] = CONSTANT_EDGE;
00589   }
00590   // determine cost of creating increment edge (we divide e/pivot_e, so trivial iff pivot_e is unit)
00591   if (eType[er.pivot_e] != UNIT_EDGE)
00592     cost++;
00593 
00594   // DECREMENT EDGES
00595   for (tie (iei, ie_end) = in_edges (target (er.pivot_e, angelLCG), angelLCG); iei != ie_end; iei++) {
00596     if (source (*iei, angelLCG) == source (er.pivot_e, angelLCG)) continue;
00597     bool found_decrement_e;
00598     c_graph_t::edge_t decrement_e;
00599     tie (decrement_e, found_decrement_e) = edge (source (*iei, angelLCG), target (er.e, angelLCG), angelLCG);
00600     if (found_decrement_e) { // decrement absorption
00601       //set edge type for absorption decrement edge
00602       if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)   eType[decrement_e] = VARIABLE_EDGE;
00603       else if (eType[decrement_e] != VARIABLE_EDGE)                                                             eType[decrement_e] = CONSTANT_EDGE;
00604     } // end decrement absorption
00605     else { // decrement fill-in
00606       tie (decrement_e, found_decrement_e) = add_edge (source (*iei, angelLCG), target (er.e, angelLCG), angelLCG.next_edge_number++, angelLCG);
00607       //set edge type for fill-in decrement edge
00608       if (eType[er.e] == VARIABLE_EDGE || eType[er.pivot_e] == VARIABLE_EDGE || eType[*iei] == VARIABLE_EDGE)   eType[decrement_e] = VARIABLE_EDGE;
00609       else if (eType[er.e] == UNIT_EDGE && eType[er.pivot_e] == UNIT_EDGE && eType[*iei] == UNIT_EDGE)          eType[decrement_e] = UNIT_EDGE;
00610       else                                                                                                      eType[decrement_e] = CONSTANT_EDGE;
00611     }
00612     // eval cost for decrements: trivial if both e and pivot_e are unit or if decrement is unit
00613     if (!((eType[er.e] == UNIT_EDGE && eType[er.pivot_e] == UNIT_EDGE) || eType[*iei] == UNIT_EDGE))
00614       cost++;
00615   } // end all decrements
00616   remove_edge (er.e, angelLCG);
00617   return cost;
00618 } // end postrouteEdge_noJAE()
00619 
00620 } // namespace angel
00621 
00622 #endif // USEXAIFBOOSTER
00623 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines