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