angel
mercurial changeset:
|
00001 // $Id: angel_types.hpp,v 1.26 2008/02/28 16:21:08 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 #ifndef _angel_types_include_ 00011 #define _angel_types_include_ 00012 00013 #include <vector> 00014 #include <string> 00015 #include <algorithm> 00016 #include <iostream> 00017 #include <sstream> 00018 00019 #define BOOST_NO_HASH // gets rid of hash_set deprecation warnings until boost fixes its code 00020 #include "boost/graph/adjacency_list.hpp" 00021 #include "boost/graph/graph_traits.hpp" 00022 #include "boost/property_map/property_map.hpp" 00023 00024 #include <map> 00025 #include <set> 00026 #ifdef USEXAIFBOOSTER 00027 #include "xaifBooster/algorithms/CrossCountryInterface/inc/LinearizedComputationalGraph.hpp" 00028 #include "xaifBooster/algorithms/CrossCountryInterface/inc/JacobianAccumulationExpressionList.hpp" 00029 #include "xaifBooster/algorithms/CrossCountryInterface/inc/GraphCorrelations.hpp" 00030 #endif // USEXAIFBOOSTER 00031 00032 #include "angel_exceptions.hpp" 00033 00034 // ===================================================== 00035 // c-graph 00036 // ===================================================== 00037 00038 namespace angel { 00039 00040 using boost::tie; 00041 00043 enum vertex_type_t {independent, 00044 intermediate, 00045 dependent, 00046 dead_vertex, 00047 undefined_vertex 00048 }; 00049 00050 enum Edge_Type_E { VARIABLE_EDGE, 00051 UNIT_EDGE, 00052 CONSTANT_EDGE }; 00053 00054 struct EdgeType { 00055 enum { num = 129 }; 00056 typedef boost::edge_property_tag kind; 00057 }; // end struct 00058 00059 // edge properties 00060 typedef boost::property<boost::edge_weight_t, int> edge_weight_property; 00061 typedef boost::property<boost::edge_index_t, int, edge_weight_property> edge_index_weight_property; 00062 typedef boost::property<EdgeType, int, edge_index_weight_property> edge_type_index_weight_property; 00063 00065 //typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, 00066 // boost::no_property, edge_type_index_weight_property> pure_c_graph_t; 00067 00068 struct VertexVisited { 00069 //enum { num = 128 }; 00070 typedef boost::vertex_property_tag kind; 00071 }; // end struct 00072 00073 // vertex visited property (for reachability queries) 00074 typedef boost::property<VertexVisited, bool> vertex_visited_property; 00075 00077 typedef boost::adjacency_list<boost::vecS, // OutEdgeList 00078 boost::vecS, // VertexList 00079 boost::bidirectionalS, // Directed 00080 vertex_visited_property, // VertexProperties 00081 edge_type_index_weight_property> // EdgeProperties 00082 pure_c_graph_t; 00083 00084 // some forward declarations 00085 class graph_package_t; 00086 class accu_graph_t; 00087 class edge_address_t; 00088 00090 class c_graph_t: public pure_c_graph_t { 00091 private: 00092 int X; // number of independent variables 00093 public: 00095 typedef pure_c_graph_t pure_graph_t; 00097 typedef pure_c_graph_t::vertex_descriptor vertex_t; 00099 typedef pure_c_graph_t::edge_descriptor edge_t; 00101 typedef boost::graph_traits<pure_c_graph_t>::vertex_iterator vi_t; 00103 typedef boost::graph_traits<pure_c_graph_t>::edge_iterator ei_t; 00105 typedef boost::graph_traits<pure_c_graph_t>::in_edge_iterator iei_t; 00107 typedef boost::graph_traits<pure_c_graph_t>::out_edge_iterator oei_t; 00109 typedef boost::property_map<pure_c_graph_t, boost::edge_weight_t>::const_type const_ew_t; 00111 typedef boost::property_map<pure_c_graph_t, boost::edge_weight_t>::type ew_t; 00113 typedef boost::property_map<pure_c_graph_t, boost::edge_index_t>::const_type const_eind_t; 00115 typedef boost::property_map<pure_c_graph_t, boost::edge_index_t>::type eind_t; 00117 typedef boost::property_map<pure_c_graph_t, EdgeType>::const_type const_etype_t; 00119 typedef boost::property_map<pure_c_graph_t, EdgeType>::type etype_t; 00120 00121 int next_edge_number; 00122 00123 std::vector<vertex_t> dependents; 00124 00126 c_graph_t () : 00127 pure_c_graph_t (), X (0), next_edge_number (0) {} 00128 00134 c_graph_t (int V_, int X_, const std::vector<vertex_t>& deps) : 00135 pure_c_graph_t (V_), X (X_), next_edge_number (0), dependents (deps) { 00136 // rem. in basic blocks vertex may be both dependent and independent 00137 #ifndef NDEBUG 00138 // assert (X >= 0 && X < V_); // X==0 is usefull in graph construction 00139 THROW_EXCEPT_MACRO (X < 0 && X > V_, consistency_exception, "X inconsistent"); 00140 for (size_t c= 0; c < dependents.size(); c++) 00141 // assert (dependents[c] < (vertex_t) V_); 00142 THROW_EXCEPT_MACRO (dependents[c] >= (vertex_t) V_, consistency_exception, "dependents inconsistent"); 00143 #endif 00144 } 00145 00151 c_graph_t (int X_, int Z_, int Y_) : 00152 pure_c_graph_t (X_+Y_+Z_), X (X_), next_edge_number (0) { 00153 // last Y vertices are dependent if nothing else is specified 00154 vi_t vi, v_end; 00155 tie(vi, v_end)= vertices(*this); 00156 for (int c= 0; c < X_+Z_; c++, ++vi); 00157 for (; vi != v_end; ++vi) 00158 dependents.push_back (*vi); 00159 } 00160 00162 c_graph_t (const c_graph_t& _g) : 00163 pure_c_graph_t (_g), X (_g.X), 00164 next_edge_number (_g.next_edge_number), dependents (_g.dependents) {} 00165 00167 c_graph_t& operator= (const c_graph_t& _g) { 00168 clear_edges (); 00169 pure_c_graph_t::operator= (_g); X= _g.X; 00170 next_edge_number= _g.next_edge_number; 00171 dependents= _g.dependents; 00172 return *this; } 00173 00175 void swap (c_graph_t& _g) { 00176 pure_c_graph_t::swap (_g); 00177 std::swap (X, _g.X); 00178 std::swap (next_edge_number, _g.next_edge_number); dependents.swap (_g.dependents); } 00179 00180 int x () const {return X;} 00181 void x (int x) { X=x;} 00182 int y () const {return (int) dependents.size();} 00183 int v () const {return (int) num_vertices(*this);} 00184 int z () const {return v()-x()-y();} 00185 00187 enum vertex_type_t vertex_type (vertex_t ve) const { 00188 if (int (ve) >= v()) return undefined_vertex; 00189 if (ve < (vertex_t) X) return independent; 00190 if (std::find (dependents.begin(), dependents.end(), ve) != dependents.end()) return dependent; 00191 return in_degree (ve, *this) == 0 && out_degree (ve, *this) == 0 ? dead_vertex : intermediate; } 00192 00194 bool check () const; 00196 bool check_initial () const; 00198 void remove_dependents_with_successors (); 00199 00203 void clear_edges () { 00204 vi_t vi, v_end; 00205 for (tie (vi, v_end)= vertices (*this); vi != v_end; ++vi) 00206 clear_vertex (*vi, *this); } 00207 00209 void clear_graph (); 00210 00211 friend int read_graph_eliad (const std::string& file_name, c_graph_t& cg, bool retry); 00212 friend void stats2block (int inputs, int outputs, const std::vector<c_graph_t>& stats, 00213 c_graph_t& block); 00214 friend void block2loop (const c_graph_t& block, int loops, 00215 c_graph_t& loop); 00216 friend void unpack_graph (const graph_package_t& gp, c_graph_t& cg); 00217 00218 #ifdef USEXAIFBOOSTER 00219 friend void read_graph_xaif_booster (const xaifBoosterCrossCountryInterface::LinearizedComputationalGraph& xg, 00220 c_graph_t& cg, 00221 std::vector<const xaifBoosterCrossCountryInterface::LinearizedComputationalGraphVertex*>& av, 00222 std::vector<edge_address_t>& ev); 00223 00224 #endif // USEXAIFBOOSTER 00225 00226 }; 00227 00229 bool operator== (const c_graph_t& g1, const c_graph_t& g2); 00230 00232 inline bool operator!= (const c_graph_t& g1, const c_graph_t& g2) { 00233 return !(g1 == g2); } 00234 00236 int overall_markowitz_degree (const c_graph_t& cg); 00237 00239 inline bool vertex_eliminatable (const c_graph_t& cg) { 00240 for (size_t c= 0; c < cg.dependents.size(); c++) 00241 if (out_degree (cg.dependents[c], cg) > 0) return false; 00242 return true; 00243 } 00244 00246 typedef std::pair<c_graph_t::edge_t,bool> edge_bool_t; 00247 00248 // ===================================================== 00249 // line graph 00250 // ===================================================== 00251 00252 00253 typedef std::pair<int, int> ad_edge_t; 00254 typedef boost::property<boost::vertex_degree_t, int> vertex_degree_property; 00255 typedef boost::property<boost::vertex_name_t, ad_edge_t, vertex_degree_property> vertex_name_degree_property; 00256 00258 typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, 00259 vertex_name_degree_property, // edges from c-graph and their label 00260 boost::no_property> pure_line_graph_t; 00261 00268 class line_graph_t: public pure_line_graph_t { 00269 private: 00270 int X; // number of edges (X-, X) 00271 bool cons_ok; // is consistent enumeration up to date 00272 public: 00274 typedef pure_line_graph_t pure_graph_t; 00276 typedef pure_line_graph_t::vertex_descriptor edge_t; 00278 typedef pure_line_graph_t::edge_descriptor face_t; 00280 typedef boost::graph_traits<pure_line_graph_t>::vertex_iterator ei_t; 00282 typedef boost::graph_traits<pure_line_graph_t>::edge_iterator fi_t; 00284 typedef boost::graph_traits<pure_line_graph_t>::in_edge_iterator ifi_t; 00286 typedef boost::graph_traits<pure_line_graph_t>::out_edge_iterator ofi_t; 00288 typedef boost::property_map<pure_line_graph_t, boost::vertex_degree_t>::const_type const_ed_t; 00290 typedef boost::property_map<pure_line_graph_t, boost::vertex_degree_t>::type ed_t; 00296 typedef boost::property_map<pure_line_graph_t, boost::vertex_name_t>::const_type const_evn_t; 00302 typedef boost::property_map<pure_line_graph_t, boost::vertex_name_t>::type evn_t; 00303 00304 std::vector<edge_t> dependents; 00305 00306 int x () const {return X;} 00307 int y () const {return dependents.size();} 00308 int v () const {return (int) num_vertices(*this);} 00309 int z () const {return v()-x()-y();} 00310 00311 const c_graph_t* cgp; 00312 00314 line_graph_t () : X (0), cons_ok (false), cgp (0) {} 00315 00321 line_graph_t (int V_, int X_, const std::vector<edge_t>& deps) : 00322 pure_line_graph_t (V_), X (X_), cons_ok (false), dependents (deps), cgp (0) { 00323 // rem. in basic blocks vertex may be both dependent and independent 00324 #ifndef NDEBUG 00325 // assert (X >= 0 && X < V_); // X==0 is usefull in graph construction 00326 THROW_EXCEPT_MACRO (X < 0 && X > V_, consistency_exception, "X inconsistent"); 00327 for (size_t c= 0; c < dependents.size(); c++) 00328 // assert (dependents[c] < (edge_t) V_); 00329 THROW_EXCEPT_MACRO (dependents[c] >= (edge_t) V_, consistency_exception, "dependents inconsistent"); 00330 #endif 00331 } 00332 00334 line_graph_t (const c_graph_t& cg); 00335 00337 line_graph_t (const line_graph_t& _g) : 00338 pure_line_graph_t (_g), X (_g.X), cons_ok (_g.cons_ok), 00339 dependents (_g.dependents), cgp (_g.cgp) {} 00340 00342 ~line_graph_t () {clear_edges ();} 00343 00345 line_graph_t& operator= (const line_graph_t& _g) { 00346 clear_edges (); 00347 pure_line_graph_t::operator= (_g); X= _g.X; cons_ok= _g.cons_ok; cgp= _g.cgp; 00348 dependents= _g.dependents; // copy_properties (_g); 00349 return *this; } 00350 00354 void swap (line_graph_t& _g) { 00355 pure_line_graph_t::swap (_g); 00356 std::swap (X, _g.X); std::swap (cons_ok, _g.cons_ok); std::swap (cgp, _g.cgp); 00357 dependents.swap (_g.dependents); } 00358 00359 // assumes that graph is okay, use check to verify 00361 enum vertex_type_t vertex_type (edge_t e) const { 00362 if (int (e) >= v()) return undefined_vertex; 00363 return in_degree (e, *this) == 0 ? (out_degree (e, *this) == 0 ? dead_vertex : independent) 00364 : (out_degree (e, *this) == 0 ? dependent : intermediate); } 00365 00367 void copy_properties (const line_graph_t& _g); 00368 00372 void clear_edges () { 00373 ei_t ei, e_end; 00374 for (tie (ei, e_end)= vertices (*this); ei != e_end; ++ei) 00375 clear_vertex (*ei, *this); } 00376 00378 void clear_graph (); 00379 00381 bool check () const; 00382 00384 bool is_tripartite () const; 00385 00386 friend int face_elimination (face_t face, int kr, line_graph_t& lg, accu_graph_t& ac); 00387 friend void unpack_graph (const graph_package_t& gp, line_graph_t& lg); 00388 }; 00389 00397 template <typename Ad_graph_t> 00398 std::pair<typename Ad_graph_t::edge_descriptor, bool> inline 00399 edge (typename Ad_graph_t::vertex_descriptor u, typename Ad_graph_t::vertex_descriptor v, 00400 const Ad_graph_t& g) { 00401 if (u < num_vertices (g) && v < num_vertices (g)) 00402 return boost::edge (u, v, (const Ad_graph_t&) g); 00403 else { 00404 typename Ad_graph_t::edge_descriptor e; return std::make_pair (e, false); } 00405 } 00406 00413 inline void edge_vertex_name (line_graph_t::edge_t e, const line_graph_t& lg, 00414 int& i, int& j) { 00415 line_graph_t::const_evn_t evn= get(boost::vertex_name, lg); 00416 i= evn[e].first; j= evn[e].second; 00417 } 00418 // edge name was already declared 00419 00427 inline void face_vertex_name (line_graph_t::face_t f, const line_graph_t& lg, 00428 int& i, int& j, int& k) { 00429 line_graph_t::const_evn_t evn= get(boost::vertex_name, lg); 00430 line_graph_t::edge_t ij= source (f, lg), jk= target (f, lg); 00431 i= evn[ij].first, j= evn[ij].second, k= evn[jk].second; 00432 THROW_DEBUG_EXCEPT_MACRO (j != evn[jk].first, consistency_exception, 00433 "Adjacency corrupted in line graph"); 00434 } 00435 00437 bool operator== (const line_graph_t& g1, const line_graph_t& g2); 00438 00440 inline bool operator!= (const line_graph_t& g1, const line_graph_t& g2) { 00441 return !(g1 == g2); } 00442 00444 int overall_markowitz_degree (const line_graph_t& lg); 00445 00451 int markowitz_degree (int j, const line_graph_t& lg); 00452 00453 00454 // ===================================================== 00455 // triplet type 00456 // ===================================================== 00457 00459 struct triplet_t { 00460 int i, j, k; 00461 triplet_t (int _i, int _j, int _k): i (_i), j (_j), k (_k) {} 00462 triplet_t (): i (-1), j (-1), k (-1) {} 00463 }; 00464 00466 inline std::ostream& operator<< (std::ostream& stream, const triplet_t& t) { 00467 return stream << "(" << t.i << ", " << t.j << ", " << t.k << ")"; } 00468 00469 00470 // ===================================================== 00471 // predecessor and successor type 00472 // ===================================================== 00473 00474 template <typename Ad_graph_t> 00475 class predecessor_t { 00476 public: 00477 typedef typename Ad_graph_t::vertex_descriptor vd_t; 00478 typedef typename Ad_graph_t::edge_descriptor ed_t; 00479 typedef typename boost::graph_traits<Ad_graph_t>::vertex_iterator vi_t; 00480 typedef typename boost::graph_traits<Ad_graph_t>::edge_iterator gei_t; 00481 typedef typename boost::graph_traits<Ad_graph_t>::in_edge_iterator ei_t; 00482 typedef typename boost::graph_traits<Ad_graph_t>::out_edge_iterator rei_t; 00483 typedef typename boost::graph_traits<Ad_graph_t>::degree_size_type ds_t; 00484 private: 00485 std::vector<vd_t> independents; 00486 public: 00487 const Ad_graph_t& adg; 00488 00489 predecessor_t (const Ad_graph_t& _adg) : adg (_adg) { 00490 vi_t vi, v_end; 00491 tie (vi, v_end)= vertices (adg); 00492 for (int c= 0; c < adg.x(); c++, vi++) 00493 independents.push_back(*vi); 00494 } 00495 00496 ds_t degree (vd_t v) const {return in_degree (v, adg); } 00497 00498 std::pair<ei_t, ei_t> edges (vd_t v) const {return in_edges (v, adg); } 00499 00500 vd_t neighbor (ed_t e) const {return source (e, adg); } 00501 00502 vd_t neighbor (ei_t ei) const {return source (*ei, adg); } 00503 00504 ds_t rdegree (vd_t v) const {return out_degree (v, adg); } 00505 00506 std::pair<rei_t, rei_t> redges (vd_t v) const {return out_edges (v, adg); } 00507 00508 vd_t rneighbor (ed_t e) const {return target (e, adg); } 00509 00510 vd_t rneighbor (rei_t rei) const {return target (*rei, adg); } 00511 00512 const std::vector<vd_t>& first () const {return adg.dependents; } 00513 00514 const std::vector<vd_t>& last () const {return independents; } 00515 00516 void clear_vertices (const std::vector<vd_t>& vv) { 00517 for (size_t c= 0; c < vv.size(); c++) 00518 clear_vertex (vv[c], (Ad_graph_t&) adg); } 00519 }; 00520 00521 00522 template <typename Ad_graph_t> 00523 class successor_t { 00524 public: 00525 typedef typename Ad_graph_t::vertex_descriptor vd_t; 00526 typedef typename Ad_graph_t::edge_descriptor ed_t; 00527 typedef typename boost::graph_traits<Ad_graph_t>::vertex_iterator vi_t; 00528 typedef typename boost::graph_traits<Ad_graph_t>::edge_iterator gei_t; 00529 typedef typename boost::graph_traits<Ad_graph_t>::out_edge_iterator ei_t; 00530 typedef typename boost::graph_traits<Ad_graph_t>::in_edge_iterator rei_t; 00531 typedef typename boost::graph_traits<Ad_graph_t>::degree_size_type ds_t; 00532 private: 00533 std::vector<vd_t> independents; 00534 public: 00535 const Ad_graph_t& adg; 00536 00537 successor_t (const Ad_graph_t& _adg) : adg (_adg) { 00538 vi_t vi, v_end; 00539 tie (vi, v_end)= vertices (adg); 00540 for (int c= 0; c < adg.x(); c++, vi++) 00541 independents.push_back(*vi); 00542 } 00543 00544 ds_t degree (vd_t v) const {return out_degree (v, adg); } 00545 00546 std::pair<ei_t, ei_t> edges (vd_t v) const {return out_edges (v, adg); } 00547 00548 vd_t neighbor (ed_t e) const {return target (e, adg); } 00549 00550 vd_t neighbor (ei_t ei) const {return target (*ei, adg); } 00551 00552 ds_t rdegree (vd_t v) const {return in_degree (v, adg); } 00553 00554 std::pair<rei_t, rei_t> redges (vd_t v) const {return in_edges (v, adg); } 00555 00556 vd_t rneighbor (ed_t e) const {return source (e, adg); } 00557 00558 vd_t rneighbor (rei_t rei) const {return source (*rei, adg); } 00559 00560 const std::vector<vd_t>& first () const {return independents; } 00561 00562 const std::vector<vd_t>& last () const {return adg.dependents; } 00563 00564 void clear_vertices (const std::vector<vd_t>& vv) { 00565 for (size_t c= 0; c < vv.size(); c++) 00566 clear_vertex (vv[c], (Ad_graph_t&) adg); } 00567 }; 00568 00569 00570 // ------------------------------------------------------------------------- 00571 // elimination sequences of edges in compute graph 00572 // ------------------------------------------------------------------------- 00573 00574 // additional data structures 00575 // -------------------------- 00576 00578 struct edge_elim_t { 00579 c_graph_t::edge_t edge; 00580 bool front; 00581 }; 00582 00585 struct edge_pair_elim_t { 00586 c_graph_t::vertex_t i, j; 00587 bool front; 00588 }; 00589 00591 inline std::ostream& operator<< (std::ostream& stream, const edge_pair_elim_t& ee) { 00592 return stream << "((" << ee.i << ", " << ee.j << "), " << ee.front << ")"; } 00593 00596 struct edge_ij_elim_t { 00597 int i, j; 00598 bool front; 00599 edge_ij_elim_t (int _i, int _j, bool _front) : i(_i), j(_j), front(_front) {} 00600 edge_ij_elim_t () : i(0), j(0), front(false) {} // only for STL 00601 }; 00602 00604 inline std::ostream& operator<< (std::ostream& stream, const edge_ij_elim_t& ee) { 00605 return stream << "((" << ee.i << ", " << ee.j << "), " << ee.front << ")"; } 00606 00609 typedef std::vector<edge_elim_t> edge_elim_seq_t; 00610 00613 typedef std::vector<edge_pair_elim_t> edge_pair_elim_seq_t; 00614 00617 typedef std::vector<edge_ij_elim_t> edge_ij_elim_seq_t; 00618 00619 // enum accu_op_t {accu_noop, accu_add, accu_mult}; 00620 00621 struct accu_exp_t { 00622 enum ref_kind_t {nothing, exp, lgn, isop}; 00623 enum op_t {add, mult}; 00624 union ref_t { 00625 line_graph_t::edge_t node; 00626 int exp_nr; 00627 op_t op; }; 00628 00629 ref_t ref; 00630 ref_kind_t ref_kind; 00631 00632 void set_exp (int _exp_nr) {ref_kind= exp; ref.exp_nr= _exp_nr; } 00633 void set_node (line_graph_t::edge_t _node) {ref_kind= lgn; ref.node= _node; } 00634 void set_op (op_t _op) {ref_kind= isop; ref.op= _op; } 00635 // accu_exp_t::ref_kind_t get_ref_kind () const {return ref_kind; } 00636 // accu_exp_t () : line_graph_node (0), exp_nr (0), op (accu_noop) {} // to sedate STL 00637 // accu_exp_t (line_graph_t::edge_t l, int e, accu_op_t o) : 00638 // line_graph_node (l), exp_nr (e), op (o) {} 00639 }; 00640 00641 inline std::ostream& operator<< (std::ostream& stream, const accu_exp_t& exp) { 00642 switch (exp.ref_kind) { 00643 case accu_exp_t::nothing: stream << "nothing"; break; 00644 case accu_exp_t::exp: stream << "expression #" << exp.ref.exp_nr; break; 00645 case accu_exp_t::lgn: stream << "line_graph_node #" << exp.ref.node; break; 00646 case accu_exp_t::isop: stream << "op " << (exp.ref.op == accu_exp_t::add ? "add" : "mult"); } 00647 return stream; } 00648 00649 typedef boost::property<boost::vertex_name_t, accu_exp_t> accu_exp_property; 00650 00651 typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, 00652 accu_exp_property, // edges from c-graph and operation 00653 boost::no_property> pure_accu_exp_graph_t; 00654 00655 class accu_exp_graph_t : public pure_accu_exp_graph_t { 00656 int X; 00657 public: 00658 void set_graph (line_graph_t::edge_t e_out, line_graph_t::edge_t e1, 00659 line_graph_t::edge_t e2, std::vector<int> exp_nr); 00660 void set_graph (accu_exp_t::op_t op, line_graph_t::edge_t e1, line_graph_t::edge_t e2, 00661 std::vector<int> exp_nr); 00662 void set_graph (line_graph_t::edge_t edge); 00663 std::vector<pure_accu_exp_graph_t::vertex_descriptor> dependents; 00664 int x () const {return X; } 00665 int y () const {return int (dependents.size()); } 00666 int v () const {return (int) num_vertices(*this);} 00667 int z () const {return v()-x()-y();} 00668 }; 00669 00670 struct accu_graph_t { 00671 const c_graph_t& cg; 00672 const line_graph_t& lg; 00673 std::vector<accu_exp_graph_t> accu_exp; 00674 std::vector<ad_edge_t> jacobi_entries; 00675 std::vector<int> exp_nr; 00676 00677 accu_graph_t (const c_graph_t& _cg, const line_graph_t& _lg) : cg (_cg), lg (_lg), 00678 exp_nr (lg.v(), -1) {} 00679 // accu_graph_t (const c_graph_t& _cg) : cg (_cg), lg (_cg), exp_nr (lg.v(), -1) {} 00680 void set_jacobi_entries (); 00681 }; 00682 00683 #ifdef USEXAIFBOOSTER 00684 enum EdgeRefType_E {LCG_EDGE, 00685 JAE_VERT, 00686 UNDEFINED}; 00687 00688 struct EdgeRef_t { 00689 c_graph_t::edge_t my_angelLCGedge; 00690 EdgeRefType_E my_type; 00691 const xaifBoosterCrossCountryInterface::LinearizedComputationalGraphEdge* my_LCG_edge_p; 00692 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex* my_JAE_vertex_p; 00693 00694 EdgeRef_t (c_graph_t::edge_t _e, 00695 const xaifBoosterCrossCountryInterface::LinearizedComputationalGraphEdge* _LCGedge_p) : 00696 my_angelLCGedge(_e), 00697 my_type(LCG_EDGE), 00698 my_LCG_edge_p(_LCGedge_p), 00699 my_JAE_vertex_p(NULL) {} 00700 00701 EdgeRef_t (c_graph_t::edge_t _e, 00702 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex* _JAEvert_p) : 00703 my_angelLCGedge(_e), 00704 my_type(JAE_VERT), 00705 my_LCG_edge_p(NULL), 00706 my_JAE_vertex_p(_JAEvert_p) {} 00707 }; 00708 00709 #endif // USEXAIFBOOSTER 00710 00711 struct edge_reroute_t { 00712 c_graph_t::edge_t e; 00713 c_graph_t::edge_t pivot_e; 00714 bool isPre; 00715 00716 mutable bool pivot_eliminatable; 00717 mutable bool increment_eliminatable; 00718 00719 mutable std::vector<c_graph_t::vertex_t> type3EdgeElimVector; 00720 00721 edge_reroute_t () {}; 00722 00723 edge_reroute_t (const c_graph_t::edge_t _e, 00724 const c_graph_t::edge_t _pivot_e, 00725 bool _isPre) : 00726 e (_e), 00727 pivot_e (_pivot_e), 00728 isPre (_isPre), 00729 pivot_eliminatable (0), 00730 increment_eliminatable (0) { type3EdgeElimVector.clear(); } 00731 }; // end struct edge_reroute_t 00732 00734 00738 class EdgeElim { 00739 public: 00740 00741 EdgeElim(); 00742 00743 EdgeElim(const c_graph_t::edge_t& e, 00744 bool isFront, 00745 const c_graph_t& angelLCG); 00746 00747 EdgeElim(const edge_bool_t& be, 00748 const c_graph_t& angelLCG); 00749 00750 EdgeElim(const edge_ij_elim_t& eij); 00751 00752 std::string debug() const; 00753 00754 bool isFront() const; 00755 00756 unsigned int getSource() const; 00757 00758 unsigned int getTarget() const; 00759 00760 c_graph_t::edge_t getE(const c_graph_t& angelLCG) const; 00761 00762 edge_bool_t getBool(const c_graph_t& angelLCG) const; 00763 00765 unsigned int getCost(const c_graph_t& angelLCG) const; 00766 00767 private: 00768 00769 bool myIsFrontFlag; 00770 unsigned int mySource; 00771 unsigned int myTarget; 00772 00773 }; // end class EdgeElim 00774 00776 00780 class Rerouting { 00781 public: 00782 00783 Rerouting(); 00784 00785 Rerouting(const c_graph_t::edge_t e, 00786 const c_graph_t::edge_t pivot_e, 00787 bool isPre, 00788 const c_graph_t& angelLCG); 00789 00790 Rerouting(const edge_reroute_t& er, 00791 const c_graph_t& angelLCG); 00792 00793 std::string debug() const; 00794 00795 bool isPre() const; 00796 00797 c_graph_t::edge_t getE(const c_graph_t& angelLCG) const; 00798 00799 c_graph_t::edge_t getPivotE(const c_graph_t& angelLCG) const; 00800 00801 edge_reroute_t getER(const c_graph_t& angelLCG) const; 00802 00803 unsigned int getI() const; 00804 unsigned int getJ() const; 00805 unsigned int getK() const; 00806 00807 bool operator==(const Rerouting& anotherRerouting) const; 00808 00809 private: 00810 00811 void init(const c_graph_t::edge_t& e, 00812 const c_graph_t::edge_t& pivot_e, 00813 bool isPre, 00814 const c_graph_t& angelLCG); 00815 00816 unsigned int i, j, k; 00817 bool pre; 00818 00819 }; // end class Rerouting 00820 00822 00826 class Transformation { 00827 public: 00828 00829 Transformation(const EdgeElim& anEdgeElim); 00830 00831 Transformation(const edge_bool_t& be, 00832 const c_graph_t& angelLCG); 00833 00834 Transformation(const edge_ij_elim_t& an_ij_elim); 00835 00836 Transformation(const Rerouting& aRerouting); 00837 00838 Transformation(const edge_reroute_t& aRerouteElim, 00839 const c_graph_t& angelLCG); 00840 00841 std::string debug() const; 00842 00844 bool isRerouting() const; 00845 00846 const EdgeElim& getEdgeElim() const; 00847 const Rerouting& getRerouting() const; 00848 00849 private: 00850 00851 Transformation(); 00852 00853 bool myIsReroutingFlag; 00854 00855 Rerouting myRerouting; 00856 EdgeElim myEdgeElim; 00857 00858 }; // end class Transformation 00859 00860 struct elimSeq_cost_t { 00861 std::vector<EdgeElim> edgeElimVector; 00862 unsigned int bestNumNontrivialEdges; 00863 unsigned int cost; 00864 unsigned int costAtBestEdgecount; 00865 unsigned int numIntermediatesAtBestEdgecount; 00866 unsigned int numIntermediatesWithoutUnitEdgeAtBestEdgecount; 00867 size_t lastDesiredElim; // unused for now 00868 mutable bool revealedNewDependence; 00869 00870 elimSeq_cost_t (unsigned int _bestNumNontrivialEdges, 00871 unsigned int _cost, 00872 unsigned int _costAtBestEdgecount, 00873 unsigned int _numIntermediatesAtBestEdgecount, 00874 unsigned int _numIntermediatesWithoutUnitEdgeAtBestEdgecount, 00875 size_t _lastDesiredElim) : 00876 bestNumNontrivialEdges (_bestNumNontrivialEdges), 00877 cost (_cost), 00878 costAtBestEdgecount (_costAtBestEdgecount), 00879 numIntermediatesAtBestEdgecount (_numIntermediatesAtBestEdgecount), 00880 numIntermediatesWithoutUnitEdgeAtBestEdgecount (_numIntermediatesWithoutUnitEdgeAtBestEdgecount), 00881 lastDesiredElim (_lastDesiredElim), 00882 revealedNewDependence (false) {} 00883 }; 00884 00885 struct transformationSeq_cost_t { 00886 std::vector<Transformation> transformationVector; 00887 unsigned int bestNumNontrivialEdges; 00888 unsigned int cost; 00889 unsigned int costAtBestEdgecount; 00890 unsigned int numIntermediatesAtBestEdgecount; 00891 unsigned int numIntermediatesWithoutUnitEdgeAtBestEdgecount; 00892 size_t lastDesiredTransformation; // unused for now 00893 mutable bool revealedNewDependence; 00894 00895 transformationSeq_cost_t (unsigned int _bestNumNontrivialEdges, 00896 unsigned int _cost, 00897 unsigned int _costAtBestEdgecount, 00898 unsigned int _numIntermediatesAtBestEdgecount, 00899 unsigned int _numIntermediatesWithoutUnitEdgeAtBestEdgecount, 00900 size_t _lastDesiredTransformation) : 00901 bestNumNontrivialEdges (_bestNumNontrivialEdges), 00902 cost (_cost), 00903 costAtBestEdgecount (_costAtBestEdgecount), 00904 numIntermediatesAtBestEdgecount (_numIntermediatesAtBestEdgecount), 00905 numIntermediatesWithoutUnitEdgeAtBestEdgecount (_numIntermediatesWithoutUnitEdgeAtBestEdgecount), 00906 lastDesiredTransformation (_lastDesiredTransformation), 00907 revealedNewDependence (false) {} 00908 }; 00909 00910 00911 typedef std::pair<unsigned int,unsigned int> uint_pair_t; 00912 typedef std::set<c_graph_t::vertex_t> vertex_set_t; 00913 typedef std::map< uint_pair_t, vertex_set_t > refillDependenceMap_t; 00914 00915 00916 } // namespace angel 00917 00918 00925 #endif // _angel_types_include_ 00926