angel  mercurial changeset:
src/angel_types.cpp
Go to the documentation of this file.
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 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines