heuristics.hpp

Go to the documentation of this file.

#ifndef         _heuristics_include_
#define         _heuristics_include_

#include <vector>

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

#ifdef USE_MPI
#include "gmpi.hpp"
#include "angel_comm.hpp"
#endif // USE_MPI

#ifdef USEXAIFBOOSTER
#include "reroutings.hpp"
#endif // USEXAIFBOOSTER

namespace angel {

  using std::vector;
  
// =====================================================
// Basic class for heuristics
// =====================================================

template <class Objective_t= int>
class base_heuristic_t {
protected:
  Objective_t   my_objective;
  bool          is_set;           // whether my_object is set
  bool          my_maximize;      // if objective value is maximized
public:
  typedef Objective_t    objective_t;
  base_heuristic_t (bool _m) : is_set (false), my_maximize (_m) {}
  Objective_t objective() const {
    THROW_DEBUG_EXCEPT_MACRO (!is_set, consistency_exception, "objective not set"); return my_objective;}
  void set_objective (Objective_t o) {
    is_set= true; my_objective= o; }
  void set_empty_objective () {
    is_set= true; 
    my_objective= my_maximize ? std::numeric_limits<Objective_t>::min() 
                              : std::numeric_limits<Objective_t>::max(); }
  bool to_maximize() const {return my_maximize;}
};

template <class Object_t, class Ad_graph_t, class Op_t, class Objective_t>
int standard_heuristic_op (const vector<Object_t>& v1, const Ad_graph_t& adg,
                           vector<Object_t>& v2, Op_t op, base_heuristic_t<Objective_t>& h);

// =====================================================
// for vertex elimination
// =====================================================

class forward_mode_vertex_t : public base_heuristic_t<int> {
public:
  forward_mode_vertex_t () : base_heuristic_t<int> (false) {}
  int operator() (const vector<c_graph_t::vertex_t>& vv1,
                  const c_graph_t& cg, 
                  vector<c_graph_t::vertex_t>& vv2);
};

extern forward_mode_vertex_t forward_mode_vertex;

// -------------------------------------------------------------------------
// reverse mode
// -------------------------------------------------------------------------

class reverse_mode_vertex_t : public base_heuristic_t<int> {
public:
  reverse_mode_vertex_t () : base_heuristic_t<int> (true) {}
  int operator() (const vector<c_graph_t::vertex_t>& vv1,
                  const c_graph_t& cg, 
                  vector<c_graph_t::vertex_t>& vv2);
};

extern reverse_mode_vertex_t reverse_mode_vertex;

// -------------------------------------------------------------------------
// Lowest Markowitz
// -------------------------------------------------------------------------

class lowest_markowitz_vertex_t : public base_heuristic_t<int> {
public:
  lowest_markowitz_vertex_t () : base_heuristic_t<int> (false) {}
  int operator() (const vector<c_graph_t::vertex_t>& vv1,
                  const c_graph_t& cg, 
                  vector<c_graph_t::vertex_t>& vv2);
};

extern lowest_markowitz_vertex_t lowest_markowitz_vertex;
  
// -------------------------------------------------------------------------
// Lowest relative Markowitz
// -------------------------------------------------------------------------

class lowest_relative_markowitz_vertex_t : public base_heuristic_t<int> {
public:
  lowest_relative_markowitz_vertex_t () : base_heuristic_t<int> (false) {}
  int operator() (const vector<c_graph_t::vertex_t>& vv1,
                  const c_graph_t& cg, 
                  vector<c_graph_t::vertex_t>& vv2);
};

extern lowest_relative_markowitz_vertex_t lowest_relative_markowitz_vertex;

// -------------------------------------------------------------------------
// Lowest fill-in
// -------------------------------------------------------------------------

class lowest_fill_in_vertex_t : public base_heuristic_t<int> {
public:
  lowest_fill_in_vertex_t () : base_heuristic_t<int> (false) {}
  int operator() (const vector<c_graph_t::vertex_t>& vv1,
                  const c_graph_t& cg, 
                  vector<c_graph_t::vertex_t>& vv2);
};

extern lowest_fill_in_vertex_t lowest_fill_in_vertex;

// -------------------------------------------------------------------------
// LMMD
// -------------------------------------------------------------------------

class lmmd_vertex_t : public base_heuristic_t<int> {
  double weight;
public:
  lmmd_vertex_t (double w) : base_heuristic_t<int> (false), weight (w) {}
  int operator() (const vector<c_graph_t::vertex_t>& vv1,
                  const c_graph_t& cg, 
                  vector<c_graph_t::vertex_t>& vv2);
};


extern lmmd_vertex_t lmmd_vertex;

// -------------------------------------------------------------------------
// MOMR
// -------------------------------------------------------------------------

class momr_vertex_t : public base_heuristic_t<int> {
public:
  momr_vertex_t () : base_heuristic_t<int> (true) {}
  int operator() (const vector<c_graph_t::vertex_t>& vv1,
                  const c_graph_t& cg, 
                  vector<c_graph_t::vertex_t>& vv2);
};

extern momr_vertex_t momr_vertex;

// -------------------------------------------------------------------------
// Maximal overall path length reduction
// -------------------------------------------------------------------------

class moplr_vertex_t : public base_heuristic_t<int> {
public:
  moplr_vertex_t () : base_heuristic_t<int> (true) {}
  int operator() (const vector<c_graph_t::vertex_t>& vv1,
                  const c_graph_t& cg, 
                  vector<c_graph_t::vertex_t>& vv2);
};

extern moplr_vertex_t moplr_vertex;

// =====================================================
// for edge elimination (in c-graph)
// =====================================================

int forward_mode_edge_f (const vector<c_graph_t::edge_t>& ev1,
                         bool front,
                         const c_graph_t& cg,
                         vector<c_graph_t::edge_t>& ev2);

inline int forward_mode_edge_front (const vector<c_graph_t::edge_t>& ev1,
                                    const c_graph_t& cg,
                                    vector<c_graph_t::edge_t>& ev2) {
  return forward_mode_edge_f (ev1, true, cg, ev2);
}

inline int forward_mode_edge_back (const vector<c_graph_t::edge_t>& ev1,
                                   const c_graph_t& cg,
                                   vector<c_graph_t::edge_t>& ev2) {
  return forward_mode_edge_f (ev1, false, cg, ev2);
}

class forward_mode_edge_t : public base_heuristic_t<double> {
public:
  forward_mode_edge_t () : base_heuristic_t<double> (false) {}
  int operator() (const vector<edge_bool_t>& ev1,
                  const c_graph_t& cg,
                  vector<edge_bool_t>& ev2);
};

extern forward_mode_edge_t forward_mode_edge;

// -------------------------------------------------------------------------
// reverse mode
// -------------------------------------------------------------------------

int reverse_mode_edge_f (const vector<c_graph_t::edge_t>& ev1,
                         bool front,
                         const c_graph_t& cg,
                         vector<c_graph_t::edge_t>& ev2);

inline int reverse_mode_edge_front (const vector<c_graph_t::edge_t>& ev1,
                                    const c_graph_t& cg,
                                    vector<c_graph_t::edge_t>& ev2) {
  return reverse_mode_edge_f (ev1, true, cg, ev2);
}

inline int reverse_mode_edge_back (const vector<c_graph_t::edge_t>& ev1,
                                   const c_graph_t& cg,
                                   vector<c_graph_t::edge_t>& ev2) {
  return reverse_mode_edge_f (ev1, false, cg, ev2);
}

class reverse_mode_edge_t : public base_heuristic_t<double> {
public:
  reverse_mode_edge_t () : base_heuristic_t<double> (false) {}
  int operator() (const vector<edge_bool_t>& ev1,
                  const c_graph_t& cg,
                  vector<edge_bool_t>& ev2);
};

extern reverse_mode_edge_t reverse_mode_edge;

// -------------------------------------------------------------------------
// Lowest Markowitz
// -------------------------------------------------------------------------

int lowest_markowitz_edge_f (const vector<c_graph_t::edge_t>& ev1,
                             bool front,
                             const c_graph_t& cg,
                             vector<c_graph_t::edge_t>& ev2);


inline int lowest_markowitz_edge_front (const vector<c_graph_t::edge_t>& ev1,
                                        const c_graph_t& cg,
                                        vector<c_graph_t::edge_t>& ev2) {
  return lowest_markowitz_edge_f (ev1, true, cg, ev2);
}


inline int lowest_markowitz_edge_back (const vector<c_graph_t::edge_t>& ev1,
                                       const c_graph_t& cg,
                                       vector<c_graph_t::edge_t>& ev2) {
  return lowest_markowitz_edge_f (ev1, false, cg, ev2);
}

class lowest_markowitz_edge_t : public base_heuristic_t<int> {
public:
  lowest_markowitz_edge_t () : base_heuristic_t<int> (false) {}
  int operator() (const vector<edge_bool_t>& ev1,
                  const c_graph_t& cg,
                  vector<edge_bool_t>& ev2);
};

extern lowest_markowitz_edge_t lowest_markowitz_edge;

// -------------------------------------------------------------------------
// Lowest relative Markowitz
// -------------------------------------------------------------------------

int lowest_relative_markowitz_edge_f (const vector<c_graph_t::edge_t>& ev1,
                                      bool front,
                                      const c_graph_t& cg,
                                      vector<c_graph_t::edge_t>& ev2);

inline int lowest_relative_markowitz_edge_front (const vector<c_graph_t::edge_t>& ev1,
                                                 const c_graph_t& cg,
                                                 vector<c_graph_t::edge_t>& ev2) {
  return lowest_relative_markowitz_edge_f (ev1, true, cg, ev2);
}

inline int lowest_relative_markowitz_edge_back (const vector<c_graph_t::edge_t>& ev1,
                                                const c_graph_t& cg,
                                                vector<c_graph_t::edge_t>& ev2) {
  return lowest_relative_markowitz_edge_f (ev1, false, cg, ev2);
}


class lowest_relative_markowitz_edge_t : public base_heuristic_t<int> {
public:
  lowest_relative_markowitz_edge_t () : base_heuristic_t<int> (false) {}
  int operator() (const vector<edge_bool_t>& ev1,
                  const c_graph_t& cg,
                  vector<edge_bool_t>& ev2);
};

extern lowest_relative_markowitz_edge_t lowest_relative_markowitz_edge;

// -------------------------------------------------------------------------
// Lowest fill-in
// -------------------------------------------------------------------------

int lowest_fill_in_edge_f (const vector<c_graph_t::edge_t>& ev1,
                           bool front,
                           const c_graph_t& cg,
                           vector<c_graph_t::edge_t>& ev2);

inline int lowest_fill_in_edge_front (const vector<c_graph_t::edge_t>& ev1,
                                      const c_graph_t& cg,
                                      vector<c_graph_t::edge_t>& ev2) {
  return lowest_fill_in_edge_f (ev1, true, cg, ev2);
}

inline int lowest_fill_in_edge_back (const vector<c_graph_t::edge_t>& ev1,
                                     const c_graph_t& cg,
                                     vector<c_graph_t::edge_t>& ev2) {
  return lowest_fill_in_edge_f (ev1, false, cg, ev2);
}

// -------------------------------------------------------------------------
// LMMD
// -------------------------------------------------------------------------

// here the class is the basic part
class lmmd_edge_t : public base_heuristic_t<int> {
  double weight;
public:
  lmmd_edge_t (double w) : base_heuristic_t<int> (false), weight (w) {}
  int operator() (const vector<edge_bool_t>& ev1,
                  const c_graph_t& cg,
                  vector<edge_bool_t>& ev2);
};

extern lmmd_edge_t lmmd_edge;

// -------------------------------------------------------------------------
// MOMR
// -------------------------------------------------------------------------

int momr_edge_f (const vector<c_graph_t::edge_t>& ev1,
                 bool front,
                 const c_graph_t& cg,
                 vector<c_graph_t::edge_t>& ev2);

inline int momr_edge_front (const vector<c_graph_t::edge_t>& ev1,
                            const c_graph_t& cg,
                            vector<c_graph_t::edge_t>& ev2) {
  return momr_edge_f (ev1, true, cg, ev2);
}

inline int momr_edge_back (const vector<c_graph_t::edge_t>& ev1,
                           const c_graph_t& cg,
                           vector<c_graph_t::edge_t>& ev2) {
  return momr_edge_f (ev1, false, cg, ev2);
}
  
class momr_edge_t : public base_heuristic_t<int> {
public:
  momr_edge_t () : base_heuristic_t<int> (true) {}
  int operator() (const vector<edge_bool_t>& ev1, const c_graph_t& cg,
                  vector<edge_bool_t>& ev2);
};

extern momr_edge_t momr_edge;

// -------------------------------------------------------------------------
// Minimal distance 
// -------------------------------------------------------------------------

class minimal_distance_edge_t : public base_heuristic_t<int> {
public:
  minimal_distance_edge_t () : base_heuristic_t<int> (false) {}
  int operator() (const vector<edge_bool_t>& ev1, const c_graph_t& cg,
                  vector<edge_bool_t>& ev2);
};

// -------------------------------------------------------------------------
// Maximal overall path length reduction
// -------------------------------------------------------------------------

int moplr_edge (const vector<c_graph_t::edge_t>& ev1,
                bool front,
                const c_graph_t& cg,
                vector<c_graph_t::edge_t>& ev2);

// =====================================================
// for edge elimination (in line graph)
// =====================================================


// =====================================================
// for face elimination
// =====================================================


class forward_mode_face_t : public base_heuristic_t<double> {
public:
  forward_mode_face_t () : base_heuristic_t<double> (false) {}
  int operator() (const vector<line_graph_t::face_t>& fv1,
                  const line_graph_t& lg,
                  vector<line_graph_t::face_t>& fv2);
};
  
extern forward_mode_face_t forward_mode_face;

// -------------------------------------------------------------------------
// reverse mode
// -------------------------------------------------------------------------

class reverse_mode_face_t : public base_heuristic_t<double> {
public:
  reverse_mode_face_t () : base_heuristic_t<double> (true) {}
  int operator() (const vector<line_graph_t::face_t>& fv1,
                  const line_graph_t& lg,
                  vector<line_graph_t::face_t>& fv2);
};

extern reverse_mode_face_t reverse_mode_face;

class reverse_mode_face_whole_vertex_t : base_heuristic_t<int> {
public:
  reverse_mode_face_whole_vertex_t () : base_heuristic_t<int> (false) {}
  int operator() (const vector<line_graph_t::face_t>& fv1,
                  const line_graph_t& lg,
                  vector<line_graph_t::face_t>& fv2);
};
  
extern reverse_mode_face_whole_vertex_t reverse_mode_face_whole_vertex;

// -------------------------------------------------------------------------
// Lowest Markowitz
// -------------------------------------------------------------------------

class lowest_markowitz_face_t : public base_heuristic_t<int> {
public:
  lowest_markowitz_face_t () : base_heuristic_t<int> (false) {}
  int operator() (const vector<line_graph_t::face_t>& fv1,
                const line_graph_t& lg,
                vector<line_graph_t::face_t>& fv2);
};
  
extern lowest_markowitz_face_t lowest_markowitz_face;

// -------------------------------------------------------------------------
// Lowest Markowitz complete elimination
// -------------------------------------------------------------------------

//
// searches for faces where j from the c-graph vertex 
// triplet representation (i,j,k) has minimal Markowitz degree
// 
// from the set of faces a tie-breaker chose a subset that belong 
// to one vertex, e.g. faces (*,j,*) with maximal j -> tie-breaker=reverse mode
//
// vertex j is stored and in following calls of the operator only
// faces (*,j,*) are returned as long as there some
// when no faces are found anymore then a new vertex is searched
//

// declaration needed in next function
void markowitz_on_line_graph (const line_graph_t& lg, vector<int>& mdegree);

template <class Heuristic_t>
class lowest_markowitz_face_complete_t : public base_heuristic_t<int> {
  int lastv; 
  Heuristic_t tiebreaker;
public:
  lowest_markowitz_face_complete_t (Heuristic_t t) : 
    base_heuristic_t<int> (false), lastv (-1), tiebreaker (t) {}
  
  int operator() (const vector<line_graph_t::face_t>& fv1,
                  const line_graph_t& lg,
                  vector<line_graph_t::face_t>& fv2);
};
  
// -------------------------------------------------------------------------
// MOMR
// -------------------------------------------------------------------------

class momr_face_t : public base_heuristic_t<int> {
public:
  momr_face_t () : base_heuristic_t<int> (true) {}
  int operator() (const vector<line_graph_t::face_t>& fv1,
                  const line_graph_t& lg,
                  vector<line_graph_t::face_t>& fv2);
};
  
extern momr_face_t momr_face;

// -------------------------------------------------------------------------
// Minimal distance 
// -------------------------------------------------------------------------

class minimal_distance_face_t : public base_heuristic_t<int> {
public:
  minimal_distance_face_t () : base_heuristic_t<int> (false) {}
  int operator() (const vector<line_graph_t::face_t>& fv1, const line_graph_t& lg,
                  vector<line_graph_t::face_t>& fv2);
};

// =====================================================
// edge_ij_elim_t heuristics (derived from edge elimination heuristics)
// =====================================================

template <class Edge_heuristic_t>
class edge_ij_elim_heuristic_t {
  Edge_heuristic_t  h;
public:
  edge_ij_elim_heuristic_t (Edge_heuristic_t _h) : h (_h) {}
  int operator() (const vector<edge_ij_elim_t>& eev1,
                  const c_graph_t& cg,
                  vector<edge_ij_elim_t>& eev2) {
    vector<edge_bool_t>   ebv1, ebv2;
    for (size_t c= 0; c < eev1.size(); c++) {
      c_graph_t::edge_t edge; bool found;
      tie (edge, found)= angel::edge (eev1[c].i, eev1[c].j, cg);
      if (found) ebv1.push_back (std::make_pair (edge, eev1[c].front)); }
    h (ebv1, cg, ebv2);
    eev2.resize (0);
    for (size_t c= 0; c < ebv2.size(); c++) {
      edge_ij_elim_t ee (source (ebv2[c].first, cg), 
                         target (ebv2[c].first, cg), ebv2[c].second);
      eev2.push_back (ee); }
    return eev2.size();
  }
};


// =====================================================
// triplet_t heuristics (derived from face elimination heuristics)
// =====================================================

template <class Face_heuristic_t>
class triplet_heuristic_t {
  Face_heuristic_t  h;
public:
  triplet_heuristic_t (Face_heuristic_t _h) : h (_h) {}
  int operator() (const vector<triplet_t>& tv1,
                  const line_graph_t& lg,
                  vector<triplet_t>& tv2) {
    vector<line_graph_t::face_t> fv1, fv2;
    for (size_t c= 0; c < tv1.size(); c++) {
      line_graph_t::face_t face; bool found;
      tie (face, found)= angel::edge (tv1[c].i, tv1[c].j, lg);
      if (found) fv1.push_back (face); }
    h (fv1, lg, fv2);
    tv2.resize (0);
    for (size_t c= 0, tc= 0; c < fv2.size(); c++) {
      int s= source (fv2[c], lg), t= target (fv2[c], lg);
      for (; s != tv1[tc].i || t != tv1[tc].j; tc++);
      tv2.push_back (tv1[tc]); }
    return tv2.size();
  }
};

template <class Vertex_heuristic_t>
class emulated_vertex_heuristic_t {
  Vertex_heuristic_t  h;
  c_graph_t::vertex_t last_vertex;
public:
  emulated_vertex_heuristic_t (Vertex_heuristic_t _h) : h (_h), last_vertex (0) {}
  int operator() (const vector<edge_ij_elim_t>& tv1, const c_graph_t& cg,
                  vector<edge_ij_elim_t>& tv2);
};


// =====================================================
// combining heuristics
// =====================================================

template <class Heuristic1_t, class Heuristic2_t>
class heuristic_pair_t {
private:
  Heuristic1_t h1;
  Heuristic2_t h2;
public:
  heuristic_pair_t (Heuristic1_t _h1, Heuristic2_t _h2):
    h1 (_h1), h2 (_h2) {}
  template <class Vector_t, class Ad_graph_t>
  int operator() (const Vector_t& v1, const Ad_graph_t& adg, Vector_t& v2) {
    Vector_t vt; h1 (v1, adg, vt); return h2 (vt, adg, v2); }
};

template <class Heuristic1_t, class Heuristic2_t, class Heuristic3_t>
class heuristic_triplet_t {
private:
  Heuristic1_t h1;
  Heuristic2_t h2;
  Heuristic3_t h3;
public:
  heuristic_triplet_t (Heuristic1_t _h1, Heuristic2_t _h2, Heuristic3_t _h3):
    h1 (_h1), h2 (_h2), h3 (_h3) {}

  template <class Vector_t, class Ad_graph_t>
  int operator() (const Vector_t& v1, const Ad_graph_t& adg, Vector_t& v2) {
    Vector_t vt1, vt2; h1 (v1, adg, vt1); h2 (vt1, adg, vt2); 
    return h3 (vt2, adg, v2);}
};

// =====================================================
// apply heuristic to some graph
// =====================================================

template <class Object_t, class Ad_graph_t, class Heuristic_t>
inline int use_heuristic (const Ad_graph_t& adg, vector<Object_t>& el_seq,
                          Heuristic_t h) {
  Ad_graph_t adg_copy (adg);
  vector<Object_t> v1;
  eliminatable_objects (adg_copy, v1);
  int costs= 0;
  el_seq.resize (0); // clean elimination sequence

  while (!v1.empty()) {
    vector<Object_t> v2;
    h (v1, adg_copy, v2);
    Object_t o= v2[0];
    costs+= eliminate (o, adg_copy);
    el_seq.push_back (o);
    eliminatable_objects (adg_copy, v1);
  }
  return costs;
}

template <class Object_t, class Ad_graph_t, class Heuristic_t>
inline int use_heuristic_noconst (Ad_graph_t& adg, vector<Object_t>& el_seq,
                                   Heuristic_t h) {
  Ad_graph_t& adg_copy (adg);
  vector<Object_t> v1;
  eliminatable_objects (adg_copy, v1);
  int costs= 0;
  el_seq.resize (0); // clean elimination sequence

  while (!v1.empty()) {
    vector<Object_t> v2;
    h (v1, adg_copy, v2);
    Object_t o= v2[0];
    costs+= eliminate (o, adg_copy);
    el_seq.push_back (o);
    eliminatable_objects (adg_copy, v1);
  }
  return costs;
}

template <class Object_t, class Ad_graph_t, class Heuristic_t>
inline int use_heuristic_debug (const Ad_graph_t& adg, vector<Object_t>& el_seq,
                                 Heuristic_t h) {
  // Ad_graph_t adg_copy (adg);
  Ad_graph_t adg_copy; 
  write_graph ("\nuse_heuristic_debug: passed graph", adg);
  cout << "edges are ";
  typename Ad_graph_t::edge_iterator ei, e_end;
  for (tie (ei, e_end)= edges (adg); ei != e_end; ++ei)
    cout << '(' << source (*ei, adg) << ", " << target (*ei, adg) << "), ";
  cout << "\n";

  write_graph ("\nuse_heuristic_debug: copied graph", adg_copy);
  adg_copy= adg;
  write_graph ("\nuse_heuristic_debug: copied graph", adg_copy);
  vector<Object_t> v1;
  eliminatable_objects (adg_copy, v1);
  int costs= 0;
  el_seq.resize (0); // clean elimination sequence

  while (!v1.empty()) {
    write_vector ("use_heuristic_debug: eliminatable objects", v1);
    vector<Object_t> v2;
    h (v1, adg_copy, v2);
    write_vector ("use_heuristic_debug: selected objects", v2);
    Object_t o= v2[0];
    costs+= eliminate (o, adg_copy);
    write_graph ("use_heuristic_debug: resulting graph", adg_copy);
    el_seq.push_back (o);
    eliminatable_objects (adg_copy, v1);
  }
  return costs;
}


template <class Object_t, class Ad_graph_t, class Heuristic_t, class Output_t>
inline int use_heuristic_trace (const Ad_graph_t& adg, vector<Object_t>& el_seq,
                                Heuristic_t h, Output_t output) {
  Ad_graph_t adg_copy (adg);
  vector<Object_t> v1;
  eliminatable_objects (adg_copy, v1);
  int costs= 0;
  el_seq.resize (0); // clean elimination sequence

  while (!v1.empty()) {
    vector<Object_t> v2;
    h (v1, adg_copy, v2);
    Object_t o= v2[0];
    int ocosts= eliminate (o, adg_copy);
    costs+= ocosts;
    output (cout, o); 
    cout << " costs " << ocosts << " --> overall " << costs << endl;
    el_seq.push_back (o);
    eliminatable_objects (adg_copy, v1);
  }
  return costs;
}

template <class Object_t, class Ad_graph_t, class Heuristic_t, class Output_t>
inline int apply_heuristic (const Ad_graph_t& adg, vector<Object_t>& el_seq,
                            Heuristic_t h, Output_t output) {
  Ad_graph_t adg_copy (adg);
  vector<Object_t> v1;
  eliminatable_objects (adg_copy, v1);
  output.write_graph ("Original graph", adg_copy);
  int costs= 0, iteration= 0;
  el_seq.resize (0); // clean elimination sequence

  while (!v1.empty()) {
    vector<Object_t> v2;
    h (v1, adg_copy, v2);
    Object_t o= v2[0];
    int ocosts= eliminate (o, adg_copy);
    costs+= ocosts;
    output << "Elimination of " << o << " costs " << ocosts << " --> overall " << costs << '\n';
    std::ostringstream gtext; gtext << "Graph after " << ++iteration << "iterations\n";
    output.write_graph (gtext.str(), adg_copy);
    el_seq.push_back (o);
    eliminatable_objects (adg_copy, v1);
  }
  return costs;
}

template <class Object_t, class Ad_graph_t, class Heuristic1_t, class Heuristic2_t, 
          class Heuristic3_t, class Heuristic4_t, class Heuristic5_t>
inline int best_heuristic (const Ad_graph_t& adg, vector<Object_t>& el_seq,
                           Heuristic1_t h1, Heuristic2_t h2, Heuristic3_t h3, 
                           Heuristic4_t h4, Heuristic5_t h5);

// =====================================================
// find subset of v1 that is best w.r.t. op
// =====================================================

template <class Object_t, class Ad_graph_t, class Op_t>
int find_best_subset (const vector<Object_t>& v1, const Ad_graph_t& adg,
                      vector<Object_t>& v2, Op_t op, bool maximize) {
  v2.resize (0);

  if (v1.size() == 0) return 0;
  int best= maximize ? -op (v1[0], adg) : op (v1[0], adg);
  v2.push_back (v1[0]);

  for (size_t c= 1; c < v1.size(); c++) {
    Object_t o= v1[c];
    int value= maximize ? -op (o, adg) : op (o, adg);
    if (value < best) v2.resize (0);
    if (value <= best) {
      v2.push_back (o); best= value;}
  }
  return v2.size();
}

#ifdef USEXAIFBOOSTER

// =====================================================
// scarcity preserving eliminations
// =====================================================

int edge_elim_effect (const edge_bool_t be,
                      const c_graph_t& angelLCG,
                      const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel);

int edge_elim_effect(const EdgeElim ee,
                     const c_graph_t& angelLCG,
                     const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel);

bool maintaining_edge_eliminations(const vector<EdgeElim>& bev1,
                                   const c_graph_t& angelLCG,
                                   const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
                                   vector<EdgeElim>& bev2);

bool reducing_edge_eliminations(const vector<EdgeElim>& bev1,
                                const c_graph_t& angelLCG,
                                const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
                                vector<EdgeElim>& bev2);

bool refill_avoiding_edge_eliminations(const vector<EdgeElim>& bev1,
                                       c_graph_t& angelLCG,
                                       const refillDependenceMap_t refillDependences,
                                       vector<EdgeElim>& bev2);

bool rerouting_considerate_edge_eliminations(const vector<EdgeElim>& bev,
                                             const c_graph_t& angelLCG,
                                             const std::vector<Transformation>& transformationsPerformedV,
                                             vector<EdgeElim>& reroutingConsiderateEdgeElimsV);

unsigned int lowestMarkowitzEdgeElim(const vector<EdgeElim>& inEEV,
                                     const c_graph_t& angelLCG,
                                     vector<EdgeElim>& outEEV);

bool reverseModeEdgeElim(const vector<EdgeElim>& inEEV,
                         const c_graph_t& angelLCG,
                         vector<EdgeElim>& outEEV);

// ==============================================================================
// |                    FILTERS FOR REROUTINGS                                  |
// ==============================================================================

size_t noncyclicReroutings(const vector<Rerouting>& erv,
                           const std::vector<Transformation>& transformationsPerformedV,
                           const c_graph_t& angelLCG,
                           vector<Rerouting>& noncyclicReroutingsV);
/*
bool maintaining_reroutings (const vector<edge_reroute_t>& erv,
                             const c_graph_t& angelLCG,
                             const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
                             vector<edge_reroute_t>& maintainReroutingsV);
*/

bool reducing_reroutings (const vector<Rerouting>& erv,
                          const c_graph_t& angelLCG,
                          const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
                          vector<Rerouting>& reducingReroutingsV);

// ==============================================================================
// |            FILTERS FOR ELIMINATIONS AND REROUTINGS (TRANSFORMATIONS)       |
// ==============================================================================

int transformation_effect(const Transformation t,
                          const c_graph_t& angelLCG,
                          const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel);

bool all_viable_transformations(c_graph_t& angelLCG,
                                const std::vector<Transformation>& transformationsPerformedV,
                                vector<Transformation>& allViableTransformationsV);

bool maintaining_transformations(const vector<Transformation>& tv,
                                 const c_graph_t& angelLCG,
                                 const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
                                 vector<Transformation>& maintainingTransformationsV);

bool reducing_transformations(const vector<Transformation>& tv,
                              const c_graph_t& angelLCG,
                              const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
                              vector<Transformation>& reducingTransformationsV);

bool refill_avoiding_transformations(const vector<Transformation>& tv,
                                     c_graph_t& angelLCG,
                                     const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel,
                                     const refillDependenceMap_t& refillDependences,
                                     vector<Transformation>& refillAvoidingTransformationsV);

bool rerouting_considerate_transformations(const vector<Transformation>& tv,
                                           const c_graph_t& angelLCG,
                                           const std::vector<Transformation>& transformationsPerformedV,
                                           vector<Transformation>& reroutingConsiderateTransformationsV); 

bool lowest_markowitz_transformations(const vector<Transformation>& tv,
                                      const c_graph_t& angelLCG,
                                      vector<Transformation>& lowestMarkowitzTransformationsV);

bool reverse_mode_transformations (const vector<Transformation>& tv,
                                   const c_graph_t& angelLCG,
                                   vector<Transformation>& reverseModeTransformationsV);

#endif // USEXAIFBOOSTER

#ifdef USE_MPI
template <class Heuristic_t, class Comm_t>
class par_heuristic_t {
  Heuristic_t       h;
  Comm_t            comm;
public:
  par_heuristic_t (Heuristic_t _h, Comm_t _comm) : h (_h), comm (_comm) {}
  template <class Vector_t, class Ad_graph_t>
  int operator() (const Vector_t& v1, const Ad_graph_t& adg, Vector_t& v2); 
};

template <class Comm_t>
class split_vector_t {
  Comm_t            comm;
public:
  split_vector_t (Comm_t _comm) : comm (_comm) {}
  template <class Vector_t, class Ad_graph_t>
  int operator() (const Vector_t& v1, const Ad_graph_t&, Vector_t& v2) {
    v2.resize (0);
    int me= comm.Get_rank(), np= comm.Get_size();
    size_t first= block_begin (me, np, v1.size()), last= block_begin (me + 1, np, v1.size()) - 1;
    for (; first <= last; first++) v2.push_back (v1[first]);
    return v2.size(); }
};

typedef split_vector_t<GMPI::Intracomm> std_split_vector_t;

template <class Comm_t>
class bcast_best_t {
  Comm_t            comm;
public:
  bcast_best_t (Comm_t _comm) : comm (_comm) {}
  template <class Vector_t, class Ad_graph_t>
  int operator() (const Vector_t& v1, const Ad_graph_t&, Vector_t& v2);
};

typedef bcast_best_t<GMPI::Intracomm> std_bcast_best_t;

template <class Heuristic_t, class Comm_t>
class par_frame_t {
private:
  split_vector_t<Comm_t>   my_split_vector;
  Heuristic_t              h;
  bcast_best_t<Comm_t>     my_bcast_best;
  heuristic_triplet_t<split_vector_t<Comm_t>,Heuristic_t,bcast_best_t<Comm_t> > my_triplet;
public:
  par_frame_t (Heuristic_t _h, Comm_t _comm) : my_split_vector (_comm), h (_h), 
                       my_bcast_best (_comm), my_triplet (my_split_vector, h, my_bcast_best) {}
  template <class Vector_t, class Ad_graph_t>
  int operator() (const Vector_t& v1, const Ad_graph_t& adg, Vector_t& v2) {
    return my_triplet (v1, adg, v2); }
};

template <class Heuristic1_t, class Heuristic2_t, class Comm_t>
class par_heuristic_pair_t {
private:
  typedef par_heuristic_t<Heuristic1_t,Comm_t>   ph1_t;
  typedef par_heuristic_t<Heuristic2_t,Comm_t>   ph2_t;
  typedef heuristic_pair_t<ph1_t,ph2_t>          pair_t;
  typedef par_frame_t<pair_t,Comm_t>             par_heuristic_t;
  ph1_t              ph1;
  ph2_t              ph2;
  pair_t             pair;
  par_heuristic_t    par_heuristic;
public:
  par_heuristic_pair_t (Heuristic1_t _h1, Heuristic2_t _h2, Comm_t _comm) :
    ph1 (_h1, _comm), ph2 (_h2, _comm), pair (ph1, ph2), par_heuristic (pair, _comm) {}
  template <class Vector_t, class Ad_graph_t>
  int operator() (const Vector_t& v1, const Ad_graph_t& adg, Vector_t& v2) {
    return par_heuristic (v1, adg, v2); }
};

template <class Heuristic1_t, class Heuristic2_t, class Heuristic3_t, class Comm_t>
class par_heuristic_triplet_t {
private:
  typedef par_heuristic_t<Heuristic1_t,Comm_t>   ph1_t;
  typedef par_heuristic_t<Heuristic2_t,Comm_t>   ph2_t;
  typedef par_heuristic_t<Heuristic3_t,Comm_t>   ph3_t;
  typedef heuristic_triplet_t<ph1_t,ph2_t,ph3_t> triplet_t;
  typedef par_frame_t<triplet_t,Comm_t>          par_heuristic_t;
  ph1_t              ph1;
  ph2_t              ph2;
  ph3_t              ph3;
  triplet_t          triplet;
  par_heuristic_t    par_heuristic;
public:
  par_heuristic_triplet_t (Heuristic1_t _h1, Heuristic2_t _h2, Heuristic3_t _h3, Comm_t _comm) :
    ph1 (_h1, _comm), ph2 (_h2, _comm), ph3 (_h3, _comm), triplet (ph1, ph2, ph3), 
    par_heuristic (triplet, _comm) {}
  template <class Vector_t, class Ad_graph_t>
  int operator() (const Vector_t& v1, const Ad_graph_t& adg, Vector_t& v2) {
    return par_heuristic (v1, adg, v2); }
};

#endif // USE_MPI

} // namespace angel

#include "heuristics_impl.hpp"

#endif  // _heuristics_include_

---