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