eliminations.hpp

Go to the documentation of this file.

/*
#############################################################
# This file is part of angel released under the BSD license #
# The full COPYRIGHT notice can be found in the top #
# level directory of the angel distribution #
#############################################################
*/

#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_