angel
mercurial changeset:
|
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