angel
mercurial changeset:
|
00001 // $Id: angel_types.cpp,v 1.14 2008/02/28 14:57:33 gottschling Exp $ 00002 /* 00003 ############################################################# 00004 # This file is part of angel released under the BSD license # 00005 # The full COPYRIGHT notice can be found in the top # 00006 # level directory of the angel distribution # 00007 ############################################################# 00008 */ 00009 00010 00011 #include "angel/include/angel_types.hpp" 00012 00013 #include <iostream> 00014 #include <string> 00015 #include <string> 00016 00017 #include "angel/include/eliminations.hpp" 00018 #include "angel/include/angel_tools.hpp" 00019 #include "angel/include/angel_io.hpp" 00020 00021 // ===================================================== 00022 // c-graph 00023 // ===================================================== 00024 00025 namespace angel { 00026 00027 using namespace std; 00028 using namespace boost; 00029 00030 bool c_graph_t::check () const { 00031 00032 // inconsistent edges, test not complete, tests only the number 00033 vi_t vi, v_end; 00034 size_t sum_edges= 0; 00035 for (tie (vi, v_end)= vertices (*this); vi != v_end; ++vi) 00036 sum_edges+= out_degree (*vi, *this); 00037 if (sum_edges != num_edges (*this)) { 00038 write_graph ("graph with inconsistent edge number", *this); 00039 cout << "individually counted: " << sum_edges << ", num_edges: " 00040 << num_edges (*this) << std::endl; 00041 return false;} 00042 00043 // test vertex type 00044 for (tie (vi, v_end)= vertices (*this); vi != v_end; ++vi) 00045 switch (vertex_type (*vi)) { 00046 case independent: 00047 if (in_degree (*vi, *this) > 0) { 00048 cout << *vi << " is independent with indegree > 0\n"; return false;} 00049 if (out_degree (*vi, *this) == 0) { 00050 cout << *vi << " is independent with outdegree == 0\n"; return false;} 00051 break; 00052 case dependent: 00053 if (in_degree (*vi, *this) == 0) { 00054 cout << *vi << " is dependent with indegree == 0\n"; return false;} 00055 // (out_degree (*vi, *this) > 0) { 00056 //cout << *vi << " is dependent with outdegree > 0\n"; return false;} 00057 default: ; // not yet used in this graph type 00058 } 00059 00060 return true; 00061 } 00062 00063 bool c_graph_t::check_initial () const { 00064 bool ok= check (); 00065 if (!ok) return false; 00066 00067 // test intermediate vertices 00068 vi_t vi, v_end; 00069 for (tie (vi, v_end)= vertices (*this); vi != v_end; ++vi) 00070 if (vertex_type (*vi) != independent && vertex_type (*vi) != dependent) { 00071 if (in_degree (*vi, *this) == 0) { 00072 cout << *vi << " is intermediate with indegree == 0\n"; return false;} 00073 if (out_degree (*vi, *this) == 0) { 00074 cout << *vi << " is intermediate with outdegree == 0\n"; return false;} } 00075 00076 return true; 00077 } 00078 00079 void c_graph_t::remove_dependents_with_successors () { 00080 00081 std::vector<vertex_t> dep; 00082 for (size_t i= 0; i < dependents.size(); i++) 00083 if (out_degree (dependents[i], *this) == 0) 00084 dep.push_back (dependents[i]); 00085 dependents.swap (dep); 00086 } 00087 00088 void c_graph_t::clear_graph () { 00089 00090 typedef c_graph_t::vertex_t v_t; 00091 typedef vector<v_t>::iterator it_t; 00092 00093 vector<bool> reachV; 00094 reachable_vertices (*this, reachV); 00095 vector<bool> relV; 00096 relevant_vertices (*this, relV); 00097 00098 // better reverse loop since removing vertices invalidates higher indices 00099 for (int i= reachV.size()-1; i >= 0; i--) 00100 if (!reachV[i] || !relV[i]) { 00101 v_t v= vertex (i, *this); 00102 clear_vertex (v, *this); 00103 remove_vertex (v, *this); 00104 00105 if (i < this->X) 00106 this->X--; 00107 else { 00108 it_t it= find (this->dependents.begin(), this->dependents.end(), v); 00109 if (it != this->dependents.end()) { 00110 remove (this->dependents.begin(), this->dependents.end(), v); 00111 this->dependents.resize(this->dependents.size()-1);} 00112 } 00113 for_each (this->dependents.begin(), this->dependents.end(), dec_greater<v_t> (v)); 00114 } 00115 } 00116 00117 00118 00119 00120 bool operator== (const c_graph_t& g1, const c_graph_t& g2) { 00121 00122 typedef c_graph_t::vertex_t vertex_t; 00123 typedef c_graph_t::vi_t vi_t; 00124 typedef c_graph_t::edge_t edge_t; 00125 typedef c_graph_t::oei_t oei_t; 00126 00127 if (g1.v() != g2.v() || g1.x() != g2.x() || g1.y() != g2.y() || g1.z() != g2.z()) 00128 return false; 00129 00130 // compare dependents (as sorted copies) 00131 vector<vertex_t> d1 (g1.dependents), d2 (g2.dependents); 00132 sort (d1.begin(), d1.end()); 00133 sort (d2.begin(), d2.end()); 00134 for (size_t c= 0; c < d1.size(); c++) 00135 if (d1[c] != d2[c]) return false; 00136 00137 // compare the out_edges for each pair of vertices 00138 vi_t vi1, v_end1, vi2, v_end2; 00139 tie (vi1, v_end1)= vertices (g1); 00140 tie (vi2, v_end2)= vertices (g2); 00141 edge_equal_t<c_graph_t> edge_equal (g1, g2); 00142 edge_less_t<c_graph_t> edge_less (g1, g2); 00143 for (; vi1 != v_end1; ++vi1, ++vi2) { 00144 oei_t oei1, oe_end1, oei2, oe_end2; 00145 tie (oei1, oe_end1)= out_edges (*vi1, g1); 00146 vector<edge_t> oe1 (oei1, oe_end1); 00147 sort (oe1.begin(), oe1.end(), edge_less); 00148 00149 tie (oei2, oe_end2)= out_edges (*vi2, g2); 00150 vector<edge_t> oe2 (oei2, oe_end2); 00151 sort (oe2.begin(), oe2.end(), edge_less); 00152 00153 // now we can compare the sorted out_edges 00154 for (size_t c= 0; c < oe1.size(); c++) 00155 if (!edge_equal (oe1[c], oe2[c])) 00156 return false; 00157 } 00158 00159 return true; 00160 } 00161 00162 int overall_markowitz_degree (const c_graph_t& cg) { 00163 00164 int degree= 0; 00165 c_graph_t::vi_t vi, v_end; 00166 for (boost::tie (vi, v_end)= vertices (cg); vi != v_end; ++vi) 00167 degree+= in_degree (*vi, cg) * out_degree (*vi, cg); 00168 00169 return degree; 00170 } 00171 00172 00173 // ===================================================== 00174 // line graph 00175 // ===================================================== 00176 00177 00178 line_graph_t::line_graph_t (const c_graph_t& cg) { 00179 00180 const int X1= cg.x(), X2= X1, Y1= cg.y(), Y2= Y1, Z2= num_edges (cg); 00181 // V2= X2+Y2+Z2; 00182 00183 pure_line_graph_t gtmp (X2+Y2+Z2); 00184 pure_line_graph_t::swap (gtmp); 00185 X= X2; cons_ok= false; 00186 00187 ed_t ew= get(vertex_degree, *this); // edge weights in line graph 00188 evn_t evn= get(vertex_name, *this); 00189 for (int i= 0; i < X2; i++) 00190 evn[i]= make_pair (i, i), ew[i]= 0; 00191 00192 // edge weights in c-graph 00193 property_map<c_graph_t, edge_weight_t>::const_type cg_ew= get(edge_weight, cg); 00194 c_graph_t::ei_t ei1, eend1; 00195 00196 tie(ei1, eend1)= edges(cg); 00197 for (int i= X2; i < X2+Z2; ei1++, i++) { 00198 evn[i]= make_pair (source (*ei1, cg), target (*ei1, cg)); 00199 ew[i]= cg_ew[*ei1]; } 00200 00201 for (int i= X2+Z2, di= 0; i < X2+Z2+Y2; di++, i++) { 00202 evn[i]= make_pair (cg.dependents[di], cg.dependents[di]); ew[i]= 0; 00203 dependents.push_back (i); } 00204 00205 // edges must be numbered correctly to avoid quadratic complexity 00206 c_graph_t cg_copy (cg); 00207 renumber_edges (cg_copy); 00208 property_map<c_graph_t, edge_index_t>::type eid1= get(edge_index, cg_copy); 00209 00210 // insert E~2 00211 c_graph_t::vi_t vi1, vend1; 00212 tie(vi1, vend1) = vertices(cg_copy); 00213 for (int i= 0; i < X1; i++, ++vi1) { 00214 c_graph_t::oei_t oei1, oeend1; 00215 for (tie (oei1, oeend1)= out_edges (*vi1, cg_copy); oei1 != oeend1; ++oei1) 00216 add_edge (i, eid1[*oei1]+X1, *this); 00217 } 00218 00219 for (tie(ei1, eend1) = edges(cg_copy); ei1 != eend1; ++ei1) { 00220 int ei1_id= eid1[*ei1]; 00221 c_graph_t::vertex_t vt= target(*ei1, cg_copy); 00222 00223 // look for dependent nodes (may not be on the end) 00224 for (size_t i= 0; i < cg_copy.dependents.size(); i++) 00225 if (vt == cg_copy.dependents[i]) { 00226 add_edge (ei1_id+X1, X2 + Z2 + i, *this); // mapping of Y from cg to lg numbering 00227 break; } 00228 00229 // look for successors (even if vt is dependent) 00230 c_graph_t::oei_t ei1i, eend1i; // incident edges 00231 for (tie (ei1i, eend1i)= out_edges (vt, cg_copy); ei1i != eend1i; ++ei1i) 00232 add_edge (ei1_id+X1, eid1[*ei1i]+X1, *this); 00233 } 00234 00235 THROW_DEBUG_EXCEPT_MACRO (overall_markowitz_degree (cg) != overall_markowitz_degree (*this), 00236 consistency_exception, "Different Markowitz degree in line graph"); 00237 } 00238 00239 00240 bool line_graph_t::check () const { 00241 00242 // inconsistent edges, test not complete, tests only the number 00243 ei_t ei, e_end; 00244 /*size_t sum_faces= 0; 00245 for (tie (ei, e_end)= vertices (*this); ei != e_end; ++ei) 00246 sum_faces+= out_degree (*ei, *this); 00247 if (sum_faces != num_edges (*this)) { 00248 write_graph ("graph with inconsistent edge number", *this); 00249 cout << "individually counted: " << sum_faces << ", num_edges: " 00250 << num_edges (*this) << std::endl; 00251 return false;} */ 00252 00253 vector<size_t> od (v ()); 00254 fi_t fi, f_end; 00255 for (tie (fi, f_end)= edges (*this); fi != f_end; ++fi) 00256 od [source(*fi,*this)]++; 00257 00258 for (tie (ei, e_end)= vertices (*this); ei != e_end; ++ei) 00259 if (out_degree (*ei, *this) != od [*ei]) { 00260 cout << "vertex " << *ei << " has inconsistent edge number (" 00261 << out_degree (*ei, *this) << " != " << od [*ei] << ")\n"; 00262 return false;} 00263 00264 line_graph_t::const_evn_t evn= get(vertex_name, *this); 00265 for (tie (fi, f_end)= edges (*this); fi != f_end; ++fi) { 00266 if (evn[source(*fi,*this)].second != evn[target(*fi,*this)].first) { 00267 cout << "edge label inconsistent\n"; return false; } 00268 if (int (source(*fi,*this)) >= v()) { 00269 cout << "edge with inconsistent source (" 00270 << source(*fi,*this) << " >= " << v() << ")\n"; return false; } 00271 if (int (target (*fi,*this)) >= v()) { 00272 cout << "edge with inconsistent target (" 00273 << target (*fi,*this) << " >= " << v() << ")\n"; return false; } } 00274 00275 for (edge_t e= 0; (int) e < x(); e++) 00276 if (evn[e].first != evn[e].second) { 00277 cout << "edge label of independent edge is inconsistent\n"; return false; } 00278 00279 for (int c= 0; c < y(); c++) { 00280 edge_t e= dependents[c]; 00281 if (evn[e].first != evn[e].second) { 00282 cout << "edge label of dependent edge is inconsistent\n"; return false; } } 00283 00284 return true; 00285 } 00286 00287 bool line_graph_t::is_tripartite () const { 00288 ei_t ei, e_end; 00289 for (tie (ei, e_end)= vertices (*this); ei != e_end; ei++) 00290 if (vertex_type (*ei) == intermediate) { 00291 if (in_degree (*ei, *this) != 1 || out_degree (*ei, *this) != 1) return false; 00292 pair<ifi_t, ifi_t> ifp= in_edges (*ei, *this); 00293 if (vertex_type (source (*ifp.first, *this)) != independent) return false; 00294 pair<ofi_t, ofi_t> ofp= out_edges (*ei, *this); 00295 if (vertex_type (target (*ofp.first, *this)) != dependent) return false; } 00296 return true; 00297 } 00298 00299 void line_graph_t::clear_graph () { 00300 00301 typedef line_graph_t::edge_t v_t; 00302 typedef vector<v_t>::iterator it_t; 00303 00304 vector<bool> reachV; 00305 reachable_vertices (*this, reachV); 00306 vector<bool> relV; 00307 relevant_vertices (*this, relV); 00308 00309 // better reverse loop since removing vertices invalidates higher indices 00310 for (int i= reachV.size()-1; i >= 0; i--) 00311 if (!reachV[i] || !relV[i]) { 00312 v_t v= vertex (i, *this); 00313 clear_vertex (v, *this); 00314 remove_vertex (v, *this); 00315 00316 if (i < this->X) 00317 this->X--; 00318 else { 00319 it_t it= find (this->dependents.begin(), this->dependents.end(), v); 00320 if (it != this->dependents.end()) { 00321 remove (this->dependents.begin(), this->dependents.end(), v); 00322 this->dependents.resize(this->dependents.size()-1);} 00323 } 00324 for_each (this->dependents.begin(), this->dependents.end(), dec_greater<v_t> (v)); 00325 } 00326 } 00327 00328 bool operator== (const line_graph_t& g1, const line_graph_t& g2) { 00329 00330 using namespace std; 00331 typedef line_graph_t::edge_t edge_t; 00332 typedef line_graph_t::ei_t ei_t; 00333 typedef line_graph_t::face_t face_t; 00334 typedef line_graph_t::ofi_t ofi_t; 00335 00336 if (g1.v() != g2.v() || g1.x() != g2.x() || g1.y() != g2.y() || g1.z() != g2.z()) 00337 return false; 00338 00339 // compare dependents (as sorted copies) 00340 vector<edge_t> d1 (g1.dependents), d2 (g2.dependents); 00341 sort (d1.begin(), d1.end()); 00342 sort (d2.begin(), d2.end()); 00343 for (size_t c= 0; c < d1.size(); c++) 00344 if (d1[c] != d2[c]) return false; 00345 00346 // compare the out_edges for each pair of vertices 00347 ei_t vi1, v_end1, vi2, v_end2; 00348 tie (vi1, v_end1)= vertices (g1); 00349 tie (vi2, v_end2)= vertices (g2); 00350 edge_equal_t<line_graph_t> edge_equal (g1, g2); 00351 edge_less_t<line_graph_t> edge_less (g1, g2); 00352 for (; vi1 != v_end1; ++vi1, ++vi2) { 00353 if (out_degree (*vi1, g1) != out_degree (*vi2, g2)) 00354 return false; 00355 00356 ofi_t oei1, oe_end1, oei2, oe_end2; 00357 tie (oei1, oe_end1)= out_edges (*vi1, g1); 00358 vector<face_t> oe1 (oei1, oe_end1); 00359 sort (oe1.begin(), oe1.end(), edge_less); 00360 00361 tie (oei2, oe_end2)= out_edges (*vi2, g2); 00362 vector<face_t> oe2 (oei2, oe_end2); 00363 sort (oe2.begin(), oe2.end(), edge_less); 00364 00365 // now we can compare the sorted out_edges 00366 for (size_t c= 0; c < oe1.size(); c++) 00367 if (!edge_equal (oe1[c], oe2[c])) 00368 return false; 00369 } 00370 00371 return true; 00372 } 00373 00374 int overall_markowitz_degree (const line_graph_t& lg) { 00375 00376 int degree= 0; 00377 line_graph_t::fi_t fi, f_end; 00378 for (boost::tie (fi, f_end)= edges (lg); fi != f_end; ++fi) 00379 degree+= vertex_type (source (*fi, lg), lg) != independent 00380 && vertex_type (target (*fi, lg), lg) != dependent; 00381 00382 return degree; 00383 } 00384 00385 int markowitz_degree (int j, const line_graph_t& lg) { 00386 00387 property_map<pure_line_graph_t, vertex_name_t>::const_type evn= get(vertex_name, lg); 00388 00389 int degree= 0; 00390 00391 line_graph_t::fi_t fi, f_end; 00392 for (boost::tie (fi, f_end)= edges (lg); fi != f_end; ++fi) { 00393 line_graph_t::edge_t ij= source (*fi, lg), jk= target (*fi, lg); 00394 THROW_DEBUG_EXCEPT_MACRO (evn[ij].second != evn[jk].first, consistency_exception, 00395 "Adjacency corrupted in line graph"); 00396 if (vertex_type (ij, lg) == independent 00397 || vertex_type (jk, lg) == dependent) continue; 00398 degree+= evn[ij].second == j; } 00399 00400 return degree; 00401 } 00402 00403 void line_graph_t::copy_properties (const line_graph_t& _g) { 00404 00405 line_graph_t::evn_t evn= get(vertex_name, *this); 00406 line_graph_t::ed_t el= get(vertex_degree, *this); // edge label 00407 00408 line_graph_t::const_evn_t cevn= get(vertex_name, _g); 00409 line_graph_t::const_ed_t cel= get(vertex_degree, _g); // edge label 00410 00411 for (size_t i= 0; i < num_vertices (*this); i++) { 00412 evn[i]= cevn[i]; el[i]= cel[i]; } 00413 } 00414 00415 void accu_exp_graph_t::set_graph (line_graph_t::edge_t e_out, line_graph_t::edge_t e1, 00416 line_graph_t::edge_t e2, std::vector<int> exp_nr) { 00417 for (int c= 0; c < 5; c++) add_vertex (*this); 00418 boost::property_map<pure_accu_exp_graph_t, boost::vertex_name_t>::type vprop= get (vertex_name, *this); 00419 if (exp_nr[e1] == -1) vprop[0].set_node (e1); else vprop[0].set_exp (exp_nr[e1]); 00420 if (exp_nr[e2] == -1) vprop[1].set_node (e2); else vprop[1].set_exp (exp_nr[e2]); 00421 if (exp_nr[e_out] == -1) vprop[2].set_node (e_out); else vprop[2].set_exp (exp_nr[e_out]); 00422 vprop[3].set_op (accu_exp_t::mult); vprop[4].set_op (accu_exp_t::add); 00423 add_edge (0, 3, *this); add_edge (1, 3, *this); add_edge (2, 4, *this); add_edge (3, 4, *this); 00424 X= 3; dependents.push_back (4); 00425 } 00426 00427 void accu_exp_graph_t::set_graph (accu_exp_t::op_t op, line_graph_t::edge_t e1, 00428 line_graph_t::edge_t e2, 00429 std::vector<int> exp_nr) { 00430 for (int c= 0; c < 3; c++) add_vertex (*this); 00431 boost::property_map<pure_accu_exp_graph_t, boost::vertex_name_t>::type vprop= get (vertex_name, *this); 00432 if (exp_nr[e1] == -1) vprop[0].set_node (e1); else vprop[0].set_exp (exp_nr[e1]); 00433 if (exp_nr[e2] == -1) vprop[1].set_node (e2); else vprop[1].set_exp (exp_nr[e2]); 00434 vprop[2].set_op (op); 00435 add_edge (0, 2, *this); add_edge (1, 2, *this); 00436 X= 2; dependents.push_back (2); 00437 } 00438 00439 void accu_exp_graph_t::set_graph (line_graph_t::edge_t edge) { 00440 add_vertex (*this); 00441 boost::property_map<pure_accu_exp_graph_t, boost::vertex_name_t>::type vprop= get (vertex_name, *this); 00442 vprop[0].set_node (edge); X= 1; 00443 } 00444 00445 void accu_graph_t::set_jacobi_entries () { 00446 jacobi_entries.resize (accu_exp.size(), make_pair (0, 0)); 00447 THROW_DEBUG_EXCEPT_MACRO ((int) exp_nr.size() != lg.v(), consistency_exception, 00448 "Array exp_nr has wrong size"); 00449 THROW_DEBUG_EXCEPT_MACRO (!lg.check(), consistency_exception, "Line graph inconsistent"); 00450 THROW_DEBUG_EXCEPT_MACRO (!lg.is_tripartite(), consistency_exception, "Line graph not tripartite"); 00451 line_graph_t::const_evn_t evn= get(vertex_name, lg); 00452 line_graph_t::ei_t ei, e_end; 00453 for (tie (ei, e_end)= vertices (lg); ei != e_end; ei++) { 00454 if (lg.vertex_type (*ei) == intermediate) { 00455 if (exp_nr[*ei] == -1) { 00456 accu_exp.resize (accu_exp.size() + 1); 00457 accu_exp[accu_exp.size()-1].set_graph(*ei); 00458 jacobi_entries.push_back (evn[*ei]); 00459 } else 00460 jacobi_entries[exp_nr[*ei]]= evn[*ei]; 00461 } 00462 } 00463 THROW_DEBUG_EXCEPT_MACRO (accu_exp.size() != jacobi_entries.size(), consistency_exception, 00464 "Wrong number of Jacobi entries"); 00465 } 00466 00467 EdgeElim::EdgeElim() { 00468 } 00469 00470 EdgeElim::EdgeElim(const c_graph_t::edge_t& e, 00471 bool isFront, 00472 const c_graph_t& angelLCG) : 00473 myIsFrontFlag (isFront), 00474 mySource (source(e, angelLCG)), 00475 myTarget (target(e, angelLCG)) { 00476 } 00477 00478 EdgeElim::EdgeElim(const edge_bool_t& be, 00479 const c_graph_t& angelLCG) : 00480 myIsFrontFlag (be.second), 00481 mySource (source(be.first, angelLCG)), 00482 myTarget (target(be.first, angelLCG)) { 00483 } 00484 00485 EdgeElim::EdgeElim(const edge_ij_elim_t& eij) : 00486 myIsFrontFlag (eij.front), 00487 mySource (eij.i), 00488 myTarget (eij.j) { 00489 } 00490 00491 std::string EdgeElim::debug() const { 00492 std::ostringstream out; 00493 myIsFrontFlag ? out << "front" 00494 : out << "back"; 00495 out << "eliminate edge (" << mySource << "," << myTarget << ")" << std::ends; 00496 return out.str(); 00497 } // end EdgeElim::debug() 00498 00499 bool EdgeElim::isFront() const { 00500 return myIsFrontFlag; 00501 } // end EdgeElim::isFront() 00502 00503 unsigned int EdgeElim::getSource() const { 00504 return mySource; 00505 } // end EdgeElim::getSource() 00506 00507 unsigned int EdgeElim::getTarget() const { 00508 return myTarget; 00509 } // end EdgeElim::getTarget() 00510 00511 c_graph_t::edge_t EdgeElim::getE(const c_graph_t& angelLCG) const { 00512 return getEdge(mySource, myTarget, angelLCG); 00513 } // end EdgeElim::getE() 00514 00515 edge_bool_t EdgeElim::getBool(const c_graph_t& angelLCG) const { 00516 return make_pair(getEdge(mySource, myTarget, angelLCG), myIsFrontFlag); 00517 } // end EdgeElim::getBool() 00518 00519 unsigned int EdgeElim::getCost(const c_graph_t& angelLCG) const { 00520 boost::property_map<c_graph_t, EdgeType>::const_type eType = get(EdgeType(), angelLCG); 00521 if (eType[getE(angelLCG)] == UNIT_EDGE) 00522 return 0; 00523 // this edge is nonunit => cost unless the other edge is unit 00524 unsigned int cost = 0; 00525 if (myIsFrontFlag) { // front elimination 00526 c_graph_t::oei_t oei, oe_end; 00527 for (tie(oei, oe_end) = out_edges(myTarget, angelLCG); oei != oe_end; ++oei) 00528 if (eType[*oei] != UNIT_EDGE) 00529 cost++; 00530 } 00531 else { // back elimination 00532 c_graph_t::iei_t iei, ie_end; 00533 for (tie(iei, ie_end) = in_edges(mySource, angelLCG); iei != ie_end; ++iei) 00534 if (eType[*iei] != UNIT_EDGE) 00535 cost++; 00536 } 00537 return cost; 00538 } // end EdgeElim::getCost() 00539 00540 Rerouting::Rerouting() { 00541 } 00542 00543 Rerouting::Rerouting(const c_graph_t::edge_t e, 00544 const c_graph_t::edge_t pivot_e, 00545 bool isPre, 00546 const c_graph_t& angelLCG) { 00547 init(e, pivot_e, isPre, angelLCG); 00548 } 00549 00550 Rerouting::Rerouting(const edge_reroute_t& er, 00551 const c_graph_t& angelLCG) { 00552 init(er.e, er.pivot_e, er.isPre, angelLCG); 00553 } 00554 00555 std::string Rerouting::debug() const { 00556 std::ostringstream out; 00557 pre ? out << "preroute edge (" << i << "," << k << ") about pivot edge (" << j << "," << k << ")" << std::ends 00558 : out << "postroute edge (" << i << "," << k << ") about pivot edge (" << i << "," << j << ")" << std::ends; 00559 return out.str(); 00560 } // end Rerouting::debug() 00561 00562 bool Rerouting::isPre() const { 00563 return pre; 00564 } // end Rerouting::isPre() 00565 00566 c_graph_t::edge_t Rerouting::getE(const c_graph_t& angelLCG) const { 00567 // e goes from i to k, regardless of whether it's a prerouting or a postrouting 00568 return getEdge(i, k, angelLCG); 00569 } // end Rerouting::getE() 00570 00571 c_graph_t::edge_t Rerouting::getPivotE(const c_graph_t& angelLCG) const { 00572 return pre ? getEdge(j, k, angelLCG) 00573 : getEdge(i, j, angelLCG); 00574 } // end Rerouting::getPivotE() 00575 00576 edge_reroute_t Rerouting::getER(const c_graph_t& angelLCG) const { 00577 return edge_reroute_t (getE(angelLCG), getPivotE(angelLCG), pre); 00578 } // end Rerouting::getER() 00579 00580 unsigned int Rerouting::getI() const { 00581 return i; 00582 } // end Rerouting::getI() 00583 00584 unsigned int Rerouting::getJ() const { 00585 return j; 00586 } // end Rerouting::getJ() 00587 00588 unsigned int Rerouting::getK() const { 00589 return k; 00590 } // end Rerouting::getK() 00591 00592 bool Rerouting::operator==(const Rerouting& anotherRerouting) const { 00593 if (this->isPre() == anotherRerouting.isPre() 00594 && this->getI() == anotherRerouting.getI() 00595 && this->getJ() == anotherRerouting.getJ() 00596 && this->getK() == anotherRerouting.getK()) 00597 return true; 00598 else 00599 return false; 00600 } // end Rerouting::operator==() 00601 00602 void Rerouting::init(const c_graph_t::edge_t& e, 00603 const c_graph_t::edge_t& pivot_e, 00604 bool isPre, 00605 const c_graph_t& angelLCG) { 00606 if (isPre) { 00607 THROW_EXCEPT_MACRO(target(e, angelLCG) != target(pivot_e, angelLCG), 00608 consistency_exception, 00609 "edge_ijk_reroute_t: the edge and the pivot edge must have the same target for a prerouting"); 00610 i = source(e, angelLCG); 00611 j = source(pivot_e, angelLCG); 00612 k = target(e, angelLCG); 00613 } 00614 else { 00615 THROW_EXCEPT_MACRO(source(e, angelLCG) != source(pivot_e, angelLCG), 00616 consistency_exception, 00617 "edge_ijk_reroute_t: the edge and the pivot edge must have the same target for a prerouting"); 00618 k = target(e, angelLCG); 00619 j = target(pivot_e, angelLCG); 00620 i = source(e, angelLCG); 00621 } 00622 pre = isPre; 00623 } // end Rerouting::init() 00624 00625 Transformation::Transformation(const EdgeElim& anEdgeElim) : 00626 myIsReroutingFlag (false), 00627 myEdgeElim (anEdgeElim) { 00628 } 00629 00630 Transformation::Transformation(const edge_bool_t& be, 00631 const c_graph_t& angelLCG) : 00632 myIsReroutingFlag (false), 00633 myEdgeElim (be, angelLCG) { 00634 } 00635 00636 Transformation::Transformation(const edge_ij_elim_t& an_ij_elim) : 00637 myIsReroutingFlag (false), 00638 myEdgeElim (an_ij_elim) { 00639 } 00640 00641 Transformation::Transformation(const Rerouting& aRerouting) : 00642 myIsReroutingFlag (true), 00643 myRerouting (aRerouting) { 00644 } 00645 00646 Transformation::Transformation(const edge_reroute_t& aRerouteElim, 00647 const c_graph_t& angelLCG) : 00648 myIsReroutingFlag (true), 00649 myRerouting (aRerouteElim, angelLCG) { 00650 } 00651 00652 std::string Transformation::debug() const { 00653 std::ostringstream out; 00654 myIsReroutingFlag ? out << myRerouting.debug().c_str() 00655 : out << myEdgeElim.debug().c_str(); 00656 return out.str(); 00657 } // end Transformation::debug() 00658 00659 bool Transformation::isRerouting() const { 00660 return myIsReroutingFlag; 00661 } // end Transformation::isRerouting() 00662 00663 const EdgeElim& Transformation::getEdgeElim() const { 00664 return myEdgeElim; 00665 } // end Transformation::getEdgeElim() 00666 00667 const Rerouting& Transformation::getRerouting() const { 00668 return myRerouting; 00669 } // end Transformation::getRerouting() 00670 00671 } // namespace angel 00672 00673 00674 // =========================== doxygen input for whole lib 00675