angel  mercurial changeset:
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 
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 
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines