angel_types.hpp

Go to the documentation of this file.

// $Id: angel_types.hpp,v 1.26 2008/02/28 16:21:08 gottschling Exp $ 
#ifndef         _angel_types_include_
#define         _angel_types_include_

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <sstream>

#include "boost/graph/adjacency_list.hpp"
#include "boost/graph/graph_traits.hpp"
#include "boost/property_map.hpp"

#ifdef USEXAIFBOOSTER
#include <map>
#include <set>
#include "xaifBooster/algorithms/CrossCountryInterface/inc/LinearizedComputationalGraph.hpp"
#include "xaifBooster/algorithms/CrossCountryInterface/inc/JacobianAccumulationExpressionList.hpp"
#include "xaifBooster/algorithms/CrossCountryInterface/inc/GraphCorrelations.hpp"
#endif // USEXAIFBOOSTER

#include "angel_exceptions.hpp"

// =====================================================
// c-graph
// =====================================================

namespace angel {

enum vertex_type_t {independent,   
                    intermediate,  
                    dependent,     
                    dead_vertex,   
                    undefined_vertex 
};

enum Edge_Type_E { VARIABLE_EDGE,
                   UNIT_EDGE,
                   CONSTANT_EDGE };

struct EdgeType { 
  enum { num = 129 };
  typedef boost::edge_property_tag kind;
}; // end struct

// edge properties
typedef boost::property<boost::edge_weight_t, int>                      edge_weight_property;
typedef boost::property<boost::edge_index_t, int, edge_weight_property> edge_index_weight_property;
typedef boost::property<EdgeType, int, edge_index_weight_property>      edge_type_index_weight_property;

//typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, 
//                      boost::no_property, edge_type_index_weight_property> pure_c_graph_t;

struct VertexVisited { 
  //enum { num = 128 };
  typedef boost::vertex_property_tag kind;
}; // end struct

// vertex visited property (for reachability queries)
typedef boost::property<VertexVisited, bool>                            vertex_visited_property;

typedef boost::adjacency_list<boost::vecS,                      // OutEdgeList
                              boost::vecS,                      // VertexList
                              boost::bidirectionalS,            // Directed
                              vertex_visited_property,          // VertexProperties
                              edge_type_index_weight_property>  // EdgeProperties
  pure_c_graph_t;

// some forward declarations
class graph_package_t; 
class accu_graph_t; 
class edge_address_t; 

class c_graph_t: public pure_c_graph_t  {
private:
    int           X;   // number of independent variables
public:
  typedef pure_c_graph_t                                                  pure_graph_t;
  typedef pure_c_graph_t::vertex_descriptor                               vertex_t;
  typedef pure_c_graph_t::edge_descriptor                                 edge_t;
  typedef boost::graph_traits<pure_c_graph_t>::vertex_iterator            vi_t;
  typedef boost::graph_traits<pure_c_graph_t>::edge_iterator              ei_t;
  typedef boost::graph_traits<pure_c_graph_t>::in_edge_iterator           iei_t;
  typedef boost::graph_traits<pure_c_graph_t>::out_edge_iterator          oei_t;
  typedef boost::property_map<pure_c_graph_t, boost::edge_weight_t>::const_type const_ew_t;
  typedef boost::property_map<pure_c_graph_t, boost::edge_weight_t>::type       ew_t;
  typedef boost::property_map<pure_c_graph_t, boost::edge_index_t>::const_type  const_eind_t;
  typedef boost::property_map<pure_c_graph_t, boost::edge_index_t>::type        eind_t;
  typedef boost::property_map<pure_c_graph_t, EdgeType>::const_type             const_etype_t;
  typedef boost::property_map<pure_c_graph_t, EdgeType>::type                   etype_t;

  int          next_edge_number;   

  std::vector<vertex_t>   dependents;   

  c_graph_t () : 
    pure_c_graph_t (), X (0), next_edge_number (0) {}

  c_graph_t (int V_, int X_, const std::vector<vertex_t>& deps) :
      pure_c_graph_t (V_), X (X_), next_edge_number (0), dependents (deps) {
    // rem. in basic blocks vertex may be both dependent and independent
    #ifndef NDEBUG
      // assert (X >= 0 && X < V_); // X==0 is usefull in graph construction
      THROW_EXCEPT_MACRO (X < 0 && X > V_, consistency_exception, "X inconsistent");
      for (size_t c= 0; c < dependents.size(); c++)
        // assert (dependents[c] < (vertex_t) V_);
        THROW_EXCEPT_MACRO (dependents[c] >= (vertex_t) V_, consistency_exception, "dependents inconsistent");
    #endif
  }

  c_graph_t (int X_, int Z_, int Y_) : 
       pure_c_graph_t (X_+Y_+Z_), X (X_), next_edge_number (0) {
    // last Y vertices are dependent if nothing else is specified
    vi_t      vi, v_end;
    tie(vi, v_end)= vertices(*this);
    for (int c= 0; c < X_+Z_; c++, ++vi);
    for (; vi != v_end; ++vi)
      dependents.push_back (*vi);
  }

  c_graph_t (const c_graph_t& _g) : 
    pure_c_graph_t (_g), X (_g.X), 
    next_edge_number (_g.next_edge_number), dependents (_g.dependents) {}
  
  c_graph_t& operator= (const c_graph_t& _g) { 
    clear_edges ();
    pure_c_graph_t::operator= (_g); X= _g.X;
    next_edge_number= _g.next_edge_number;
    dependents= _g.dependents;
    return *this; }

  void swap (c_graph_t& _g) {
    pure_c_graph_t::swap (_g);
    std::swap (X, _g.X); 
    std::swap (next_edge_number, _g.next_edge_number); dependents.swap (_g.dependents); }

  int x () const {return X;}                           
  void x (int x) { X=x;}                               
  int y () const {return (int) dependents.size();}     
  int v () const {return (int) num_vertices(*this);}   
  int z () const {return v()-x()-y();}                 

  enum vertex_type_t vertex_type (vertex_t ve) const {
    if (int (ve) >= v()) return undefined_vertex;
    if (ve < (vertex_t) X) return independent;
    if (std::find (dependents.begin(), dependents.end(), ve) != dependents.end()) return dependent;
    return in_degree (ve, *this) == 0 && out_degree (ve, *this) == 0 ? dead_vertex : intermediate; }

  bool check () const;
  bool check_initial () const;
  void remove_dependents_with_successors ();

  void clear_edges () {
    vi_t vi, v_end;
    for (tie (vi, v_end)= vertices (*this); vi != v_end; ++vi)
      clear_vertex (*vi, *this); }

  void clear_graph ();

  friend int read_graph_eliad (const std::string& file_name, c_graph_t& cg, bool retry);
  friend void stats2block (int inputs, int outputs, const std::vector<c_graph_t>& stats, 
                           c_graph_t& block);
  friend void block2loop (const c_graph_t& block, int loops,
                          c_graph_t& loop);
  friend void unpack_graph (const graph_package_t& gp, c_graph_t& cg);

#ifdef USEXAIFBOOSTER
  friend void read_graph_xaif_booster (const xaifBoosterCrossCountryInterface::LinearizedComputationalGraph& xg, 
                                       c_graph_t& cg,
                                       std::vector<const xaifBoosterCrossCountryInterface::LinearizedComputationalGraphVertex*>& av,
                                       std::vector<edge_address_t>& ev);

#endif // USEXAIFBOOSTER

};

bool operator== (const c_graph_t& g1, const c_graph_t& g2);

inline bool operator!= (const c_graph_t& g1, const c_graph_t& g2) {
  return !(g1 == g2); }

int overall_markowitz_degree (const c_graph_t& cg);

  inline bool vertex_eliminatable (const c_graph_t& cg) {
    for (size_t c= 0; c < cg.dependents.size(); c++)
      if (out_degree (cg.dependents[c], cg) > 0) return false;
    return true;
  }

typedef std::pair<c_graph_t::edge_t,bool> edge_bool_t;

// =====================================================
// line graph
// =====================================================


typedef std::pair<int, int>                                  ad_edge_t;
typedef boost::property<boost::vertex_degree_t, int>                              vertex_degree_property;
typedef boost::property<boost::vertex_name_t, ad_edge_t, vertex_degree_property>  vertex_name_degree_property;

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, 
                       vertex_name_degree_property, // edges from c-graph and their label
                       boost::no_property> pure_line_graph_t; 

class line_graph_t: public pure_line_graph_t {
private:
  int X;        // number of edges (X-, X)
  bool cons_ok; // is consistent enumeration up to date
public:
  typedef pure_line_graph_t                                            pure_graph_t;
  typedef pure_line_graph_t::vertex_descriptor                         edge_t;
  typedef pure_line_graph_t::edge_descriptor                           face_t;
  typedef boost::graph_traits<pure_line_graph_t>::vertex_iterator             ei_t;
  typedef boost::graph_traits<pure_line_graph_t>::edge_iterator               fi_t;
  typedef boost::graph_traits<pure_line_graph_t>::in_edge_iterator            ifi_t;
  typedef boost::graph_traits<pure_line_graph_t>::out_edge_iterator           ofi_t;
  typedef boost::property_map<pure_line_graph_t, boost::vertex_degree_t>::const_type const_ed_t;
  typedef boost::property_map<pure_line_graph_t, boost::vertex_degree_t>::type       ed_t;
  typedef boost::property_map<pure_line_graph_t, boost::vertex_name_t>::const_type   const_evn_t;
  typedef boost::property_map<pure_line_graph_t, boost::vertex_name_t>::type         evn_t;

  std::vector<edge_t>   dependents;   

  int x () const {return X;}                   
  int y () const {return dependents.size();}   
  int v () const {return (int) num_vertices(*this);}  
  int z () const {return v()-x()-y();}         

  const c_graph_t*  cgp;   

  line_graph_t () : X (0), cons_ok (false), cgp (0) {}

  line_graph_t (int V_, int X_, const std::vector<edge_t>& deps) :
      pure_line_graph_t (V_), X (X_), cons_ok (false), dependents (deps), cgp (0) {
    // rem. in basic blocks vertex may be both dependent and independent
    #ifndef NDEBUG
      // assert (X >= 0 && X < V_); // X==0 is usefull in graph construction
      THROW_EXCEPT_MACRO (X < 0 && X > V_, consistency_exception, "X inconsistent");
      for (size_t c= 0; c < dependents.size(); c++)
        // assert (dependents[c] < (edge_t) V_);
        THROW_EXCEPT_MACRO (dependents[c] >= (edge_t) V_, consistency_exception, "dependents inconsistent");
    #endif
  }

  line_graph_t (const c_graph_t& cg); 

  line_graph_t (const line_graph_t& _g) : 
    pure_line_graph_t (_g), X (_g.X), cons_ok (_g.cons_ok),
    dependents (_g.dependents), cgp (_g.cgp) {}

  ~line_graph_t () {clear_edges ();}

  line_graph_t& operator= (const line_graph_t& _g) { 
    clear_edges ();
    pure_line_graph_t::operator= (_g); X= _g.X; cons_ok= _g.cons_ok; cgp= _g.cgp; 
    dependents= _g.dependents; // copy_properties (_g); 
    return *this; }
   
  void swap (line_graph_t& _g) {
    pure_line_graph_t::swap (_g);
    std::swap (X, _g.X); std::swap (cons_ok, _g.cons_ok); std::swap (cgp, _g.cgp); 
    dependents.swap (_g.dependents); }

  // assumes that graph is okay, use check to verify
  enum vertex_type_t vertex_type (edge_t e) const {
    if (int (e) >= v()) return undefined_vertex;
    return in_degree (e, *this) == 0 ? (out_degree (e, *this) == 0 ? dead_vertex : independent)
      : (out_degree (e, *this) == 0 ? dependent : intermediate); }
 
  void copy_properties (const line_graph_t& _g);
    
  void clear_edges () {
    ei_t ei, e_end;
    for (tie (ei, e_end)= vertices (*this); ei != e_end; ++ei)
      clear_vertex (*ei, *this); }

  void clear_graph ();

  bool check () const;

  bool is_tripartite () const;

  friend int face_elimination (face_t face, int kr, line_graph_t& lg, accu_graph_t& ac);
  friend void unpack_graph (const graph_package_t& gp, line_graph_t& lg);
};

template <typename Ad_graph_t>
std::pair<typename Ad_graph_t::edge_descriptor, bool> inline
edge (typename Ad_graph_t::vertex_descriptor u, typename Ad_graph_t::vertex_descriptor v, 
      const Ad_graph_t& g) {
  if (u < num_vertices (g) && v < num_vertices (g))
    return boost::edge (u, v, (const Ad_graph_t&) g);
  else {
    typename Ad_graph_t::edge_descriptor e; return std::make_pair (e, false); }
}

inline void edge_vertex_name (line_graph_t::edge_t e, const line_graph_t& lg,
                              int& i, int& j) {
  line_graph_t::const_evn_t evn= get(boost::vertex_name, lg); 
  i= evn[e].first; j= evn[e].second;
}
// edge name was already declared

inline void face_vertex_name (line_graph_t::face_t f, const line_graph_t& lg,
                              int& i, int& j, int& k) {
  line_graph_t::const_evn_t evn= get(boost::vertex_name, lg); 
  line_graph_t::edge_t   ij= source (f, lg), jk= target (f, lg);
  i= evn[ij].first, j= evn[ij].second, k= evn[jk].second;
  THROW_DEBUG_EXCEPT_MACRO (j != evn[jk].first, consistency_exception,
                         "Adjacency corrupted in line graph"); 
}

bool operator== (const line_graph_t& g1, const line_graph_t& g2);

inline bool operator!= (const line_graph_t& g1, const line_graph_t& g2) {
  return !(g1 == g2); }

int overall_markowitz_degree (const line_graph_t& lg);

int markowitz_degree (int j, const line_graph_t& lg);


// =====================================================
// triplet type
// =====================================================

struct triplet_t {
  int  i, j, k;
  triplet_t (int _i, int _j, int _k): i (_i), j (_j), k (_k) {}
  triplet_t (): i (-1), j (-1), k (-1) {}
};

inline std::ostream& operator<< (std::ostream& stream, const triplet_t& t) {
  return stream << "(" << t.i << ", " << t.j << ", " << t.k << ")"; }


// =====================================================
// predecessor and successor type
// =====================================================

template <typename Ad_graph_t>
class predecessor_t {
public:
  typedef typename Ad_graph_t::vertex_descriptor                        vd_t;
  typedef typename Ad_graph_t::edge_descriptor                          ed_t;
  typedef typename boost::graph_traits<Ad_graph_t>::vertex_iterator     vi_t;
  typedef typename boost::graph_traits<Ad_graph_t>::edge_iterator       gei_t;
  typedef typename boost::graph_traits<Ad_graph_t>::in_edge_iterator    ei_t;
  typedef typename boost::graph_traits<Ad_graph_t>::out_edge_iterator   rei_t;
  typedef typename boost::graph_traits<Ad_graph_t>::degree_size_type    ds_t;
private:
  std::vector<vd_t> independents;
public:
  const Ad_graph_t& adg;

  predecessor_t (const Ad_graph_t& _adg) : adg (_adg) {
    vi_t      vi, v_end;
    tie (vi, v_end)= vertices (adg);
    for (int c= 0; c < adg.x(); c++, vi++)
      independents.push_back(*vi);
  }

  ds_t degree (vd_t v) const {return in_degree (v, adg); }

  std::pair<ei_t, ei_t> edges (vd_t v) const {return in_edges (v, adg); }

  vd_t neighbor (ed_t e) const {return source (e, adg); }

  vd_t neighbor (ei_t ei) const {return source (*ei, adg); }

  ds_t rdegree (vd_t v) const {return out_degree (v, adg); }

  std::pair<rei_t, rei_t> redges (vd_t v) const {return out_edges (v, adg); }

  vd_t rneighbor (ed_t e) const {return target (e, adg); }

  vd_t rneighbor (rei_t rei) const {return target (*rei, adg); }

  const std::vector<vd_t>& first () const {return adg.dependents; }

  const std::vector<vd_t>& last () const {return independents; }

  void clear_vertices (const std::vector<vd_t>& vv) {
    for (size_t c= 0; c < vv.size(); c++) 
      clear_vertex (vv[c], (Ad_graph_t&) adg); }
};


template <typename Ad_graph_t>
class successor_t {
public:
  typedef typename Ad_graph_t::vertex_descriptor                        vd_t;
  typedef typename Ad_graph_t::edge_descriptor                          ed_t;
  typedef typename boost::graph_traits<Ad_graph_t>::vertex_iterator     vi_t;
  typedef typename boost::graph_traits<Ad_graph_t>::edge_iterator       gei_t;
  typedef typename boost::graph_traits<Ad_graph_t>::out_edge_iterator   ei_t;
  typedef typename boost::graph_traits<Ad_graph_t>::in_edge_iterator    rei_t;
  typedef typename boost::graph_traits<Ad_graph_t>::degree_size_type    ds_t;
private:
  std::vector<vd_t> independents;
public:
  const Ad_graph_t& adg;

  successor_t (const Ad_graph_t& _adg) : adg (_adg) {
    vi_t      vi, v_end;
    tie (vi, v_end)= vertices (adg);
    for (int c= 0; c < adg.x(); c++, vi++)
      independents.push_back(*vi);
  }

  ds_t degree (vd_t v) const {return out_degree (v, adg); }

  std::pair<ei_t, ei_t> edges (vd_t v) const {return out_edges (v, adg); }

  vd_t neighbor (ed_t e) const {return target (e, adg); }

  vd_t neighbor (ei_t ei) const {return target (*ei, adg); }

  ds_t rdegree (vd_t v) const {return in_degree (v, adg); }

  std::pair<rei_t, rei_t> redges (vd_t v) const {return in_edges (v, adg); }

  vd_t rneighbor (ed_t e) const {return source (e, adg); }

  vd_t rneighbor (rei_t rei) const {return source (*rei, adg); }

  const std::vector<vd_t>& first () const {return independents; }

  const std::vector<vd_t>& last () const {return adg.dependents; }

  void clear_vertices (const std::vector<vd_t>& vv) {
    for (size_t c= 0; c < vv.size(); c++) 
      clear_vertex (vv[c], (Ad_graph_t&) adg); }
};


// -------------------------------------------------------------------------
// elimination sequences of edges in compute graph
// -------------------------------------------------------------------------

// additional data structures
// --------------------------

struct edge_elim_t {
  c_graph_t::edge_t    edge;
  bool                 front;
};

struct edge_pair_elim_t {
  c_graph_t::vertex_t  i, j;
  bool                 front;
};

inline std::ostream& operator<< (std::ostream& stream, const edge_pair_elim_t& ee) {
  return stream << "((" << ee.i << ", " << ee.j << "), " << ee.front << ")"; }

struct edge_ij_elim_t {
  int                           i, j;
  bool                          front;
  edge_ij_elim_t (int _i, int _j, bool _front) : i(_i), j(_j), front(_front) {}
  edge_ij_elim_t () : i(0), j(0), front(false) {} // only for STL
};

inline std::ostream& operator<< (std::ostream& stream, const edge_ij_elim_t& ee) {
  return stream << "((" << ee.i << ", " << ee.j << "), " << ee.front << ")"; }

typedef std::vector<edge_elim_t>       edge_elim_seq_t;

typedef std::vector<edge_pair_elim_t>  edge_pair_elim_seq_t;

typedef std::vector<edge_ij_elim_t>    edge_ij_elim_seq_t;

// enum accu_op_t {accu_noop, accu_add, accu_mult};

struct accu_exp_t {
  enum ref_kind_t {nothing, exp, lgn, isop};
  enum op_t {add, mult};
  union ref_t {
    line_graph_t::edge_t   node;
    int                    exp_nr;
    op_t                   op; };

  ref_t ref;
  ref_kind_t ref_kind;

  void set_exp (int _exp_nr) {ref_kind= exp; ref.exp_nr= _exp_nr; }
  void set_node (line_graph_t::edge_t _node) {ref_kind= lgn; ref.node= _node; }
  void set_op (op_t _op) {ref_kind= isop; ref.op= _op; }
  // accu_exp_t::ref_kind_t get_ref_kind () const {return ref_kind; }
  // accu_exp_t () : line_graph_node (0), exp_nr (0), op (accu_noop) {} // to sedate STL
  // accu_exp_t (line_graph_t::edge_t l, int e, accu_op_t o) : 
  //                      line_graph_node (l), exp_nr (e), op (o) {}
};

inline std::ostream& operator<< (std::ostream& stream, const accu_exp_t& exp) {
  switch (exp.ref_kind) {
  case accu_exp_t::nothing: stream << "nothing"; break;
  case accu_exp_t::exp:     stream << "expression #" << exp.ref.exp_nr; break;
  case accu_exp_t::lgn:     stream << "line_graph_node #" << exp.ref.node; break;
  case accu_exp_t::isop:    stream << "op " << (exp.ref.op == accu_exp_t::add ? "add" : "mult"); }
  return stream; }

typedef boost::property<boost::vertex_name_t, accu_exp_t>     accu_exp_property;

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, 
                       accu_exp_property, // edges from c-graph and operation
                       boost::no_property> pure_accu_exp_graph_t; 

class accu_exp_graph_t : public pure_accu_exp_graph_t {
  int X;
public:
  void set_graph (line_graph_t::edge_t e_out, line_graph_t::edge_t e1,
                    line_graph_t::edge_t e2, std::vector<int> exp_nr); 
  void set_graph (accu_exp_t::op_t op, line_graph_t::edge_t e1, line_graph_t::edge_t e2,
                    std::vector<int> exp_nr);
  void set_graph (line_graph_t::edge_t edge);
  std::vector<pure_accu_exp_graph_t::vertex_descriptor>  dependents;
  int x () const {return X; }
  int y () const {return int (dependents.size()); }
  int v () const {return (int) num_vertices(*this);}
  int z () const {return v()-x()-y();}         
};

struct accu_graph_t {
  const c_graph_t&                                            cg;
  const line_graph_t&                                         lg;
  std::vector<accu_exp_graph_t>                               accu_exp;
  std::vector<ad_edge_t>                                      jacobi_entries;
  std::vector<int>                                            exp_nr;

  accu_graph_t (const c_graph_t& _cg, const line_graph_t& _lg) : cg (_cg), lg (_lg),
    exp_nr (lg.v(), -1) {}
  // accu_graph_t (const c_graph_t& _cg) : cg (_cg), lg (_cg), exp_nr (lg.v(), -1) {}
  void set_jacobi_entries ();
};

#ifdef USEXAIFBOOSTER
enum EdgeRefType_E {LCG_EDGE,
                    JAE_VERT,
                    UNDEFINED};

struct EdgeRef_t {
  c_graph_t::edge_t my_angelLCGedge;
  EdgeRefType_E my_type;
  const xaifBoosterCrossCountryInterface::LinearizedComputationalGraphEdge* my_LCG_edge_p;
  xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex* my_JAE_vertex_p;

  EdgeRef_t (c_graph_t::edge_t _e,
             const xaifBoosterCrossCountryInterface::LinearizedComputationalGraphEdge* _LCGedge_p) :
    my_angelLCGedge(_e),
    my_type(LCG_EDGE),
    my_LCG_edge_p(_LCGedge_p),
    my_JAE_vertex_p(NULL) {}

  EdgeRef_t (c_graph_t::edge_t _e,
             xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex* _JAEvert_p) :
    my_angelLCGedge(_e),
    my_type(JAE_VERT),
    my_LCG_edge_p(NULL),
    my_JAE_vertex_p(_JAEvert_p) {}
};

struct edge_reroute_t {
  c_graph_t::edge_t e;
  c_graph_t::edge_t pivot_e;
  bool isPre;

  mutable bool pivot_eliminatable;
  mutable bool increment_eliminatable;

  mutable std::vector<c_graph_t::vertex_t> type3EdgeElimVector;

  edge_reroute_t () {};

  edge_reroute_t (const c_graph_t::edge_t _e,
                  const c_graph_t::edge_t _pivot_e,
                  bool _isPre) :
    e (_e),
    pivot_e (_pivot_e),
    isPre (_isPre),
    pivot_eliminatable (0),
    increment_eliminatable (0) { type3EdgeElimVector.clear(); }
}; // end struct edge_reroute_t


  class EdgeElim {
  public:

    EdgeElim();

    EdgeElim(const c_graph_t::edge_t& e,
             bool isFront,
             const c_graph_t& angelLCG);

    EdgeElim(const edge_bool_t& be,
             const c_graph_t& angelLCG);

    EdgeElim(const edge_ij_elim_t& eij);

    std::string debug() const;

    bool isFront() const;

    unsigned int getSource() const;

    unsigned int getTarget() const;

    c_graph_t::edge_t getE(const c_graph_t& angelLCG) const;

    edge_bool_t getBool(const c_graph_t& angelLCG) const;

    unsigned int getCost(const c_graph_t& angelLCG) const;

  private:

    bool myIsFrontFlag;
    unsigned int mySource;
    unsigned int myTarget;

  }; // end class EdgeElim


  class Rerouting {
  public:

    Rerouting();

    Rerouting(const c_graph_t::edge_t e,
              const c_graph_t::edge_t pivot_e,
              bool isPre,
              const c_graph_t& angelLCG);

    Rerouting(const edge_reroute_t& er,
              const c_graph_t& angelLCG);

    std::string debug() const;

    bool isPre() const;

    c_graph_t::edge_t getE(const c_graph_t& angelLCG) const;

    c_graph_t::edge_t getPivotE(const c_graph_t& angelLCG) const;

    edge_reroute_t getER(const c_graph_t& angelLCG) const;

    unsigned int getI() const;
    unsigned int getJ() const;
    unsigned int getK() const;

    bool operator==(const Rerouting& anotherRerouting) const;

  private:

    void init(const c_graph_t::edge_t& e,
              const c_graph_t::edge_t& pivot_e,
              bool isPre,
              const c_graph_t& angelLCG);
       
    unsigned int i, j, k;
    bool pre;

  }; // end class Rerouting


  class Transformation {
  public:

    Transformation(const EdgeElim& anEdgeElim);

    Transformation(const edge_bool_t& be,
                   const c_graph_t& angelLCG);

    Transformation(const edge_ij_elim_t& an_ij_elim);

    Transformation(const Rerouting& aRerouting);

    Transformation(const edge_reroute_t& aRerouteElim,
                   const c_graph_t& angelLCG);

    std::string debug() const;

    bool isRerouting() const;

    const EdgeElim& getEdgeElim() const;
    const Rerouting& getRerouting() const;

  private:

    Transformation();

    bool myIsReroutingFlag;

    Rerouting myRerouting;
    EdgeElim myEdgeElim;

  }; // end class Transformation

struct elimSeq_cost_t {
  std::vector<EdgeElim> edgeElimVector;
  unsigned int bestNumNontrivialEdges;
  unsigned int cost;
  unsigned int costAtBestEdgecount;
  unsigned int numIntermediatesAtBestEdgecount;
  unsigned int numIntermediatesWithoutUnitEdgeAtBestEdgecount;
  size_t lastDesiredElim;               // unused for now
  mutable bool revealedNewDependence;

  elimSeq_cost_t (unsigned int _bestNumNontrivialEdges,
                  unsigned int _cost,
                  unsigned int _costAtBestEdgecount,
                  unsigned int _numIntermediatesAtBestEdgecount,
                  unsigned int _numIntermediatesWithoutUnitEdgeAtBestEdgecount,
                  size_t _lastDesiredElim) :
    bestNumNontrivialEdges (_bestNumNontrivialEdges),
    cost (_cost),
    costAtBestEdgecount (_costAtBestEdgecount),
    numIntermediatesAtBestEdgecount (_numIntermediatesAtBestEdgecount),
    numIntermediatesWithoutUnitEdgeAtBestEdgecount (_numIntermediatesWithoutUnitEdgeAtBestEdgecount),
    lastDesiredElim (_lastDesiredElim),
    revealedNewDependence (false) {}
};

struct transformationSeq_cost_t {
  std::vector<Transformation> transformationVector;
  unsigned int bestNumNontrivialEdges;
  unsigned int cost;
  unsigned int costAtBestEdgecount;
  unsigned int numIntermediatesAtBestEdgecount;
  unsigned int numIntermediatesWithoutUnitEdgeAtBestEdgecount;
  size_t lastDesiredTransformation;     // unused for now
  mutable bool revealedNewDependence;

  transformationSeq_cost_t (unsigned int _bestNumNontrivialEdges,
                            unsigned int _cost,
                            unsigned int _costAtBestEdgecount,
                            unsigned int _numIntermediatesAtBestEdgecount,
                            unsigned int _numIntermediatesWithoutUnitEdgeAtBestEdgecount,
                            size_t _lastDesiredTransformation) :
                              bestNumNontrivialEdges (_bestNumNontrivialEdges),
                              cost (_cost),
                              costAtBestEdgecount (_costAtBestEdgecount),
                              numIntermediatesAtBestEdgecount (_numIntermediatesAtBestEdgecount),
                              numIntermediatesWithoutUnitEdgeAtBestEdgecount (_numIntermediatesWithoutUnitEdgeAtBestEdgecount),
                              lastDesiredTransformation (_lastDesiredTransformation),
                              revealedNewDependence (false) {}
};

typedef std::pair<unsigned int,unsigned int>    uint_pair_t;
typedef std::set<c_graph_t::vertex_t>           vertex_set_t;
typedef std::map< uint_pair_t, vertex_set_t >   refillDependenceMap_t;

#endif // USEXAIFBOOSTER

} // namespace angel


#endif  // _angel_types_include_

---