eliminations.hpp

Go to the documentation of this file.

#ifndef         _eliminations_include_
#define         _eliminations_include_

#include "angel_types.hpp"
#include "angel_io.hpp"

#ifdef USEXAIFBOOSTER
  #include "xaifBooster/algorithms/CrossCountryInterface/inc/AwarenessLevel.hpp"
  using std::list;
#endif

  namespace angel {

  using std::vector;
  using std::cout;
  using boost::tie;

// =========================================================================
// eliminations in c-graph
// =========================================================================

// -------------------------------------------------------------------------
// elimination of a single vertex in compute graph
// -------------------------------------------------------------------------

int vertex_elimination (c_graph_t::vertex_t v, c_graph_t& cg);  

inline int vertex_elimination (int j, c_graph_t& cg) {
  return vertex_elimination (vertex (j, cg), cg); }

// -------------------------------------------------------------------------
// elimination of a single edge in compute graph
// -------------------------------------------------------------------------

int front_edge_elimination (c_graph_t::edge_t e,
                            c_graph_t& cg);

inline int front_edge_elimination (c_graph_t::vertex_t i,
                                   c_graph_t::vertex_t j,
                                   c_graph_t& cg) {
  bool                          found_ij;
  c_graph_t::edge_t   edge_ij;
  tie (edge_ij, found_ij)= edge (i, j, cg);
  return found_ij ? front_edge_elimination (edge_ij, cg) : 0;
}

inline int front_edge_elimination (int i, int j, c_graph_t& cg) {
  return front_edge_elimination (vertex (i, cg), vertex (j, cg), cg); }


int back_edge_elimination (c_graph_t::edge_t e,
                           c_graph_t& cg);

inline int back_edge_elimination (c_graph_t::vertex_t i, 
                                  c_graph_t::vertex_t j,
                                  c_graph_t& cg) {
  bool                          found_ij;
  c_graph_t::edge_t   edge_ij;
  tie (edge_ij, found_ij)= edge (i, j, cg);
  return found_ij ? back_edge_elimination (edge_ij, cg) : 0;
}

inline int back_edge_elimination (int i, int j, c_graph_t& cg) {
  return back_edge_elimination (vertex (i, cg), vertex (j, cg), cg); }

inline int edge_elimination (c_graph_t::edge_t e, bool front,
                             c_graph_t& cg) {
  return front ? front_edge_elimination (e, cg)
               : back_edge_elimination (e, cg);
}

inline int edge_elimination (edge_bool_t e, c_graph_t& cg) {
  return e.second ? front_edge_elimination (e.first, cg)
                  : back_edge_elimination (e.first, cg);
}

inline int edge_elimination (c_graph_t::vertex_t i,
                             c_graph_t::vertex_t j,
                             bool front, c_graph_t& cg) {
  return front ? front_edge_elimination (i, j, cg)
               : back_edge_elimination (i, j, cg);
}

inline int edge_elimination (int i, int j, bool front, c_graph_t& cg) {
  return front ? front_edge_elimination (i, j, cg)
               : back_edge_elimination (i, j, cg);
}

inline int edge_elimination (edge_ij_elim_t ee, c_graph_t& cg) {
  return edge_elimination (ee.i, ee.j, ee.front, cg); }

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

int vertex_elimination (const vector<int>& seq, c_graph_t& cg);


inline int edge_elimination (const edge_elim_seq_t& seq, c_graph_t& cg) {
  int costs= 0;
  for (size_t i= 0; i < seq.size(); i++)
    costs+= edge_elimination (seq[i].edge, seq[i].front, cg);
  return costs;
}
  
inline int edge_elimination (const edge_pair_elim_seq_t& seq, c_graph_t& cg) {
  int costs= 0;
  for (size_t k= 0; k < seq.size(); k++)
    costs+= edge_elimination (seq[k].i, seq[k].j, seq[k].front, cg);
  return costs;
}
  
inline int edge_elimination (const edge_ij_elim_seq_t& seq, c_graph_t& cg) {
  int costs= 0;
  for (size_t k= 0; k < seq.size(); k++)
    costs+= edge_elimination (seq[k].i, seq[k].j, seq[k].front, cg);
  return costs;
}
  
// =========================================================================
// eliminations in line graph
// =========================================================================

// -------------------------------------------------------------------------
// elimination of a single vertex in line graph
// -------------------------------------------------------------------------

int vertex_elimination (int j, line_graph_t& lg);

// -------------------------------------------------------------------------
// elimination of a single edge in line graph
// -------------------------------------------------------------------------

int front_edge_elimination (int i, int j, line_graph_t& lg);

int front_edge_elimination (line_graph_t::edge_t vij, line_graph_t& lg);

int back_edge_elimination (int i, int j, line_graph_t& lg);

int back_edge_elimination (line_graph_t::edge_t vij, line_graph_t& lg);

inline int edge_elimination (int i, int j, bool front, line_graph_t& lg) {
  return front ? front_edge_elimination (i, j, lg)
               : back_edge_elimination (i, j, lg);
}

inline int edge_elimination (line_graph_t::edge_t vij,
                             bool front, line_graph_t& lg) {
  return front ? front_edge_elimination (vij, lg)
               : back_edge_elimination (vij, lg);
}

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

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

struct edge_vertex_elim_t {
  line_graph_t::edge_t    edge;
  bool                    front;
};

typedef vector<edge_vertex_elim_t>       edge_vertex_elim_seq_t;

inline int edge_elimination (const edge_vertex_elim_seq_t& seq, line_graph_t& lg) {
  int costs= 0;
  for (size_t k= 0; k < seq.size(); k++)
    costs+= edge_elimination (seq[k].edge, seq[k].front, lg);
  return costs;
}

// -------------------------------------------------------------------------
// elimination of a single face in line graph
// -------------------------------------------------------------------------

int face_elimination (line_graph_t::face_t f, int kr, line_graph_t& lg, accu_graph_t& ac);

inline int face_elimination (line_graph_t::face_t f, int kr, line_graph_t& lg) {
  accu_graph_t dummy (*lg.cgp, lg);
  return face_elimination (f, kr, lg, dummy); }

inline int face_elimination (line_graph_t::face_t f, line_graph_t& lg) {
  return face_elimination (f, -1, lg); }

inline int face_elimination (int i, int j, line_graph_t& lg) {
  line_graph_t::face_t f; bool found;
  tie (f, found)= edge (i, j, lg);
  return found ? face_elimination (f, lg) : -1;
}

inline int face_elimination (int i, int j, int kr, line_graph_t& lg) {
  line_graph_t::face_t f; bool found;
  tie (f, found)= edge (i, j, lg);
  return found ? face_elimination (f, kr, lg) : -1;
}

inline int face_elimination (int i, int j, int kr, line_graph_t& lg, accu_graph_t& ac) {
  line_graph_t::face_t f; bool found;
  tie (f, found)= edge (i, j, lg);
  return found ? face_elimination (f, kr, lg, ac) : -1;
}

inline int face_elimination (triplet_t& t, line_graph_t& lg) {
  int k= face_elimination (t.i, t.j, t.k, lg);
  if (k != -1) t.k= k; return k != -1;
}

inline int face_elimination (triplet_t& t, line_graph_t& lg, accu_graph_t& ac) {
  int k= face_elimination (t.i, t.j, t.k, lg, ac);
  if (k != -1) t.k= k; return k != -1;
}

inline int was_non_trivial_elimination (int i, int j, int k, const line_graph_t& lg) {
  line_graph_t::const_ed_t   el= get(boost::vertex_degree, lg);  // edge label
  return ((k != -1 && el[i] != 1 && el[j] != 1) || k < lg.v()-1); // absorption -> a+= b in accumulation
}

inline int was_non_trivial_elimination (line_graph_t::face_t f, int k, const line_graph_t& lg) {
  line_graph_t::edge_t  i= source (f, lg), j= target (f, lg);
  return was_non_trivial_elimination (i, j, k, lg);
}

// -------------------------------------------------------------------------
// elimination sequences of faces
// -------------------------------------------------------------------------


// =========================================================================
// overloaded elimination functions for templates
// =========================================================================

inline int eliminate (c_graph_t::vertex_t v, c_graph_t& cg) {
  return vertex_elimination (v, cg); }

inline int eliminate (int j, c_graph_t& cg) {
  return vertex_elimination (j, cg); }

inline int eliminate (int j, line_graph_t& lg) {
  return vertex_elimination (j, lg); }

inline int eliminate (edge_bool_t e, c_graph_t& cg) {
  return edge_elimination (e, cg);
}

inline int eliminate (edge_ij_elim_t ee, c_graph_t& cg) {
  return edge_elimination (ee, cg);
}

inline int eliminate (line_graph_t::face_t f, line_graph_t& lg) {
  int k= face_elimination (f, -1, lg); 
  return was_non_trivial_elimination (f, k, lg);
}

inline int eliminate (triplet_t& t, line_graph_t& lg) {
  return face_elimination (t, lg);
}

// =========================================================================
// which vertices, edges or faces can be eliminated
// =========================================================================

int eliminatable_vertices (const c_graph_t& cg, 
                           vector<c_graph_t::vertex_t>& vv);

int semi_eliminatable_vertices (const c_graph_t& cg, vector<c_graph_t::vertex_t>& vv);

int eliminatable_edges (const c_graph_t& cg, 
                        vector<c_graph_t::edge_t>& ev);

int front_eliminatable_edges (const c_graph_t& cg, 
                              vector<c_graph_t::edge_t>& ev);

int back_eliminatable_edges (const c_graph_t& cg, 
                             vector<c_graph_t::edge_t>& ev);

int eliminatable_edges (const c_graph_t& cg,
                        vector<edge_bool_t>& ev);

int eliminatable_edges (const c_graph_t& cg,
                        vector<edge_ij_elim_t>& ev);

unsigned int eliminatable_edges(const c_graph_t& cg, 
                                vector<EdgeElim>& ev);

int eliminatable_faces (const line_graph_t& lg, 
                        vector<line_graph_t::face_t>& fv);

inline int eliminatable_triplets (const line_graph_t& lg, vector<triplet_t>& tv) {
  vector<line_graph_t::face_t> fv;
  eliminatable_faces (lg, fv);
  tv.resize (0);
  for (size_t c= 0; c < fv.size(); c++) {
    int s= source (fv[c], lg), t= target (fv[c], lg);
    triplet_t tr (s, t, -1); tv.push_back (tr); }
  return tv.size();
}

// =========================================================================
// which vertices, edges or faces can be eliminated (overloaded versions)
// =========================================================================

inline int eliminatable_objects (const c_graph_t& cg, 
                                 vector<c_graph_t::vertex_t>& vv) {
  return eliminatable_vertices (cg, vv);
}

inline int eliminatable_objects (const c_graph_t& cg, 
                                 vector<c_graph_t::edge_t>& ev) {
  return eliminatable_edges (cg, ev);
}

inline int eliminatable_objects (const c_graph_t& cg,
                                 vector<edge_bool_t>& ev) {
  return eliminatable_edges (cg, ev);
}

inline int eliminatable_objects (const c_graph_t& cg,
                                 vector<edge_ij_elim_t>& ev) {
  return eliminatable_edges (cg, ev);
}

inline int eliminatable_objects (const line_graph_t& lg, 
                                 vector<line_graph_t::face_t>& fv) {
  return eliminatable_faces (lg, fv);
}

inline int eliminatable_objects (const line_graph_t& lg, 
                                 vector<triplet_t>& tv) {
  return eliminatable_triplets (lg, tv);
}



template <typename Ad_graph_t,
          typename El_spec_t>
class elimination_history_t {
private:

public:
  const Ad_graph_t             og;     
  vector<El_spec_t>       seq;    
  Ad_graph_t                   cg;     
  int                          ccosts; 

  typedef Ad_graph_t  ad_graph_t;
  typedef El_spec_t   el_spec_t;

  elimination_history_t () : og () {}

  elimination_history_t (const Ad_graph_t& _cg) : 
    og (_cg), cg (_cg), ccosts (0) {
    THROW_EXCEPT_MACRO (!check (), consistency_exception, "Inconsistent input graph");}

  elimination_history_t (const Ad_graph_t& _og, const vector<El_spec_t>& _seq,
                         const Ad_graph_t& _cg, int _ccosts= 0) :
    og (_og), seq (_seq), cg (_cg), ccosts (_ccosts) {
    THROW_EXCEPT_MACRO (!check (), consistency_exception, "Inconsistent input graphs");}

  elimination_history_t (const Ad_graph_t& _og, const vector<El_spec_t>& _seq) :
    og (_og), seq (_seq) {
    THROW_EXCEPT_MACRO (!og.check (), consistency_exception, "Inconsistent input graph");
    bool seq_ok= rebuild_graph (); 
    THROW_EXCEPT_MACRO (!seq_ok, consistency_exception, "Inconsistent elimination sequence");
  }

  elimination_history_t (const elimination_history_t& eh) :
    og (eh.og), seq (eh.seq), cg (eh.cg), ccosts (eh.ccosts) {
    THROW_EXCEPT_MACRO (!og.check (), consistency_exception, "Inconsistent start graph");
    THROW_EXCEPT_MACRO (!cg.check (), consistency_exception, "Inconsistent current graph");
    THROW_EXCEPT_MACRO (!check_sequence(), consistency_exception, "Inconsistent elimination sequence");
  }

  elimination_history_t& operator= (const elimination_history_t& eh) {
    (Ad_graph_t&) og= eh.og; seq= eh.seq; cg= eh.cg; ccosts= eh.ccosts; 
    THROW_DEBUG_EXCEPT_MACRO (!check (), consistency_exception, "Inconsistent graphs after assignment");
    return *this; }

  void swap (elimination_history_t& eh) {
    ((Ad_graph_t&) og).swap ((Ad_graph_t&) eh.og); 
    seq.swap (eh.seq); cg.swap (eh.cg); std::swap (ccosts, eh.ccosts); 
    THROW_DEBUG_EXCEPT_MACRO (!check (), consistency_exception, "Inconsistent graphs after swapping");}

  int elimination (El_spec_t el) {
    int costs= eliminate (el, cg); 
    if (costs > 0) {seq.push_back (el); ccosts+= costs; }
    return costs; }

  bool check_sequence () const {
    Ad_graph_t og_copy (og);
    int costs= 0;
    for (size_t c= 0; c < seq.size(); c++) {
      El_spec_t el= seq[c]; // copied from seq because some eliminations change el
      int el_costs= eliminate (el, og_copy); 
      if (el_costs == 0) {      
        cout << "check_sequence failed";
        write_vector (" with elimination sequence", seq);
        cout << " at " << c << "th entry, which is " << seq[c] << std::endl;
        write_graph ("at this moment the graph is", og_copy);
        cout << "it is " << (og_copy.check() ? "" : "not ") << "consistent\n";
        write_vector ("complete elimination sequence is", seq);
        return false; }
      else costs+= el_costs; }
    if (cg != og_copy) {
      cout << "check_sequence failed because of different resulting graphs.\n";
      write_graph ("current graph is", cg);
      write_graph ("seq applied to og results in", og_copy); 
      write_graph ("original graph was", og);
      write_vector ("elimination sequence is", seq);
      return false; }
    if (ccosts != costs) {
      cout << "check_sequence failed because of different elimination costs.\n";
      cout << "current costs are " << ccosts << std::endl;
      cout << "seq applied to og requires " << costs << std::endl;
      write_graph ("original graph was", og);
      write_vector ("elimination sequence is", seq);
      write_graph ("current graph is", cg);
      return false; }
    return true; 
  }

  bool check () const {
    if (!og.check ()) return false; // original graph inconsistent
    if (!cg.check ()) return false; // current graph inconsistent
    return check_sequence (); }

  bool rebuild_graph () {
    Ad_graph_t og_copy (og);
    int        costs= 0;
    for (size_t c= 0; c < seq.size(); c++) {
      int el_costs= eliminate (seq[c], og_copy);
      if (el_costs == 0) return false; else costs+= el_costs; }
    cg= og_copy; ccosts= costs; return true; }

  template <typename Heuristic_t>
  void complete_sequence (Heuristic_t h) {
    vector<El_spec_t>    v1, v2;
    for (eliminatable_objects (cg, v1); v1.size() > 0; eliminatable_objects (cg, v1)) {
      v2.resize (0); h (v1, cg, v2); elimination (v2[0]); }}
};

typedef elimination_history_t<c_graph_t, c_graph_t::vertex_t> vertex_elimination_history_t;
typedef elimination_history_t<c_graph_t, edge_ij_elim_t>      edge_elimination_history_t;
typedef elimination_history_t<line_graph_t, triplet_t>        face_elimination_history_t;

bool convert_elimination_sequence (const vector<c_graph_t::vertex_t>& vv, 
                                   const c_graph_t& cg,
                                   vector<edge_ij_elim_t>& ev);

bool convert_elimination_sequence (const vector<edge_ij_elim_t>& ev,
                                   const line_graph_t& lg,
                                   vector<triplet_t>& tv);

#ifdef USEXAIFBOOSTER

EdgeRefType_E getRefType (const c_graph_t::edge_t e,
                          const c_graph_t& angelLCG,
                          const list<EdgeRef_t>& edge_ref_list);

const xaifBoosterCrossCountryInterface::LinearizedComputationalGraphEdge* getLCG_p (const c_graph_t::edge_t e,
                                                                                    const c_graph_t& angelLCG,
                                                                                    const list<EdgeRef_t>& edge_ref_list);

xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex* getJAE_p (const c_graph_t::edge_t e,
                                                                                  const c_graph_t& angelLCG,
                                                                                  const list<EdgeRef_t>& edge_ref_list);

void setJaevRef (const c_graph_t::edge_t e,
                 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionVertex& jaev,
                 const c_graph_t& angelLCG,
                 const list<EdgeRef_t>& edge_ref_list);
        
void removeRef (const c_graph_t::edge_t e,
                const c_graph_t& angelLCG,
                list<EdgeRef_t>& edge_ref_list);

unsigned int multiply_edge_pair_directly (const c_graph_t::edge_t e1,
                                          const c_graph_t::edge_t e2,
                                          c_graph_t& angelLCG,
                                          list<EdgeRef_t>& edge_ref_list,
                                          xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionList& jae_list);

unsigned int front_eliminate_edge_directly (c_graph_t::edge_t e,
                                            c_graph_t& angelLCG,
                                            list<EdgeRef_t>& edge_ref_list,
                                            xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionList& jae_list);

unsigned int back_eliminate_edge_directly (c_graph_t::edge_t e,
                                           c_graph_t& angelLCG,
                                           list<EdgeRef_t>& edge_ref_list,
                                           xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionList& jae_list);

unsigned int pair_elim (c_graph_t::edge_t e1,
                        c_graph_t::edge_t e2,
                        c_graph_t& angelLCG,
                        const elimSeq_cost_t& currentElimSeq,
                        refillDependenceMap_t& refillDependences);

unsigned int front_elim (c_graph_t::edge_t e,
                         c_graph_t& angelLCG,
                         const elimSeq_cost_t& currentElimSeq,
                         refillDependenceMap_t& refillDependences);

unsigned int back_elim (c_graph_t::edge_t e,
                        c_graph_t& angelLCG,
                        const elimSeq_cost_t& currentElimSeq,
                        refillDependenceMap_t& refillDependences);

unsigned int pairElim_noJAE (c_graph_t::edge_t e1,
                             c_graph_t::edge_t e2,
                             c_graph_t& angelLCG,
                             const transformationSeq_cost_t* currentTransformationSequence,
                             refillDependenceMap_t& refillDependences);

unsigned int frontEdgeElimination_noJAE (c_graph_t::edge_t e,
                                         c_graph_t& angelLCG,
                                         const transformationSeq_cost_t* currentTransformationSequence,
                                         refillDependenceMap_t& refillDependences);

unsigned int backEdgeElimination_noJAE (c_graph_t::edge_t e,
                                        c_graph_t& angelLCG,
                                        const transformationSeq_cost_t* currentTransformationSequence,
                                        refillDependenceMap_t& refillDependences);

#endif // USEXAIFBOOSTER

} // namespace angel

#endif  // _eliminations_include_

---