#include <vector>
#include "angel_types.hpp"
#include "angel_io.hpp"
#include "eliminations.hpp"
#include "reroutings.hpp"
#include "heuristics_impl.hpp"
Go to the source code of this file.
Classes | |
class | angel::base_heuristic_t< Objective_t > |
class | angel::forward_mode_vertex_t |
Operator class for forward mode in vertex elimination. More... | |
class | angel::reverse_mode_vertex_t |
Operator class for reverse mode in vertex elimination. More... | |
class | angel::lowest_markowitz_vertex_t |
Operator class for lowest Markowitz in vertex elimination. More... | |
class | angel::lowest_relative_markowitz_vertex_t |
Operator class for relative lowest Markowitz in vertex elimination. More... | |
class | angel::lowest_fill_in_vertex_t |
Operator class for lowest fill-in in vertex elimination. More... | |
class | angel::lmmd_vertex_t |
Class for lowest Markowitz with minimal damage in vertex elimination. More... | |
class | angel::momr_vertex_t |
Operator class for maximal overall Markowitz degree reduction in vertex elimination. More... | |
class | angel::moplr_vertex_t |
Operator class for maximal overall path length reduction in vertex elimination. More... | |
class | angel::forward_mode_edge_t |
Operator class for mixed forward edge elimination. More... | |
class | angel::reverse_mode_edge_t |
Operator class for mixed reverse edge elimination. More... | |
class | angel::lowest_markowitz_edge_t |
Operator class for lowest Markowitz in mixed edge elimination. More... | |
class | angel::lowest_relative_markowitz_edge_t |
Operator class for lowest relative Markowitz in mixed edge elimination. More... | |
class | angel::lmmd_edge_t |
Class for lowest Markowitz with minimal damage in mixed edge elimination. More... | |
class | angel::momr_edge_t |
Operator class for lowest Markowitz in mixed edge elimination. More... | |
class | angel::minimal_distance_edge_t |
Minimizes the maximal distance of vertices involved in an edge elimination The motivation is that for small distances it is not very probable to re-insert one of new edges later. More... | |
class | angel::forward_mode_face_t |
Operator class for forward mode in face elimination. More... | |
class | angel::reverse_mode_face_t |
Operator class for reverse mode in vertex elimination. More... | |
class | angel::reverse_mode_face_whole_vertex_t |
Operator class for reverse_mode_face_whole_vertex. More... | |
class | angel::lowest_markowitz_face_t |
class | angel::lowest_markowitz_face_complete_t< Heuristic_t > |
Lowest Markowitz for face elimination with completion of vertex elimination. More... | |
class | angel::momr_face_t |
Operator class for maximal overall Markowitz degree reduction in face elimination. More... | |
class | angel::minimal_distance_face_t |
Minimal distance for face elimination. More... | |
class | angel::edge_ij_elim_heuristic_t< Edge_heuristic_t > |
Creates a heuristic for (i,j,front) type from a heuristic for (edge,front). More... | |
class | angel::triplet_heuristic_t< Face_heuristic_t > |
Creates a heuristic for triplet type from a heuristic for faces. More... | |
class | angel::emulated_vertex_heuristic_t< Vertex_heuristic_t > |
Simulates vertex elimination heuristics with edge eliminations. More... | |
class | angel::heuristic_pair_t< Heuristic1_t, Heuristic2_t > |
Make a pair of heuristics. More... | |
class | angel::heuristic_triplet_t< Heuristic1_t, Heuristic2_t, Heuristic3_t > |
Make a pair of heuristics. More... | |
Namespaces | |
namespace | angel |
Namespace for the complete library. | |
Functions | |
template<class Object_t , class Ad_graph_t , class Op_t , class Objective_t > | |
int | angel::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) |
Find best subset of v1 w.r.t. op , skeleton for new heuristics. | |
int | angel::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) |
Forward mode in edge elimination. | |
int | angel::forward_mode_edge_front (const vector< c_graph_t::edge_t > &ev1, const c_graph_t &cg, vector< c_graph_t::edge_t > &ev2) |
Forward mode in front edge elimination. | |
int | angel::forward_mode_edge_back (const vector< c_graph_t::edge_t > &ev1, const c_graph_t &cg, vector< c_graph_t::edge_t > &ev2) |
Forward mode in back edge elimination. | |
int | angel::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) |
Reverse mode in edge elimination. | |
int | angel::reverse_mode_edge_front (const vector< c_graph_t::edge_t > &ev1, const c_graph_t &cg, vector< c_graph_t::edge_t > &ev2) |
Reverse mode in front edge elimination. | |
int | angel::reverse_mode_edge_back (const vector< c_graph_t::edge_t > &ev1, const c_graph_t &cg, vector< c_graph_t::edge_t > &ev2) |
Reverse mode in back edge elimination. | |
int | angel::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) |
Lowest Markowitz in edge elimination. | |
int | angel::lowest_markowitz_edge_front (const vector< c_graph_t::edge_t > &ev1, const c_graph_t &cg, vector< c_graph_t::edge_t > &ev2) |
Lowest Markowitz in front edge elimination. | |
int | angel::lowest_markowitz_edge_back (const vector< c_graph_t::edge_t > &ev1, const c_graph_t &cg, vector< c_graph_t::edge_t > &ev2) |
Lowest Markowitz in back edge elimination. | |
int | angel::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) |
Lowest relative Markowitz in edge elimination. | |
int | angel::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) |
Lowest relative Markowitz in front edge elimination. | |
int | angel::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) |
Lowest relative Markowitz in back edge elimination. | |
int | angel::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) |
Lowest Fill-in in edge elimination. | |
int | angel::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) |
Lowest fill-in in front edge elimination. | |
int | angel::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) |
Lowest fill-in in back edge elimination. | |
int | angel::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) |
Maximal overall Markowitz reduction in edge elimination. | |
int | angel::momr_edge_front (const vector< c_graph_t::edge_t > &ev1, const c_graph_t &cg, vector< c_graph_t::edge_t > &ev2) |
Maximal overall Markowitz reduction in front edge elimination. | |
int | angel::momr_edge_back (const vector< c_graph_t::edge_t > &ev1, const c_graph_t &cg, vector< c_graph_t::edge_t > &ev2) |
Maximal overall Markowitz reduction in back edge elimination. | |
int | angel::moplr_edge (const vector< c_graph_t::edge_t > &ev1, bool front, const c_graph_t &cg, vector< c_graph_t::edge_t > &ev2) |
Maximal overall path length reduction in mixed edge elimination. | |
void | angel::markowitz_on_line_graph (const line_graph_t &lg, vector< int > &mdegree) |
template<class Object_t , class Ad_graph_t , class Heuristic_t > | |
int | angel::use_heuristic (const Ad_graph_t &adg, vector< Object_t > &el_seq, Heuristic_t h) |
Use heuristic to transform c-/line graph into bi-/tri-partite graph. | |
template<class Object_t , class Ad_graph_t , class Heuristic_t > | |
int | angel::use_heuristic_noconst (Ad_graph_t &adg, vector< Object_t > &el_seq, Heuristic_t h) |
Use heuristic to transform c-/line graph into bi-/tri-partite graph. | |
template<class Object_t , class Ad_graph_t , class Heuristic_t > | |
int | angel::use_heuristic_debug (const Ad_graph_t &adg, vector< Object_t > &el_seq, Heuristic_t h) |
Debugging version of use_heuristic, several outputs. | |
template<class Object_t , class Ad_graph_t , class Heuristic_t , class Output_t > | |
int | angel::use_heuristic_trace (const Ad_graph_t &adg, vector< Object_t > &el_seq, Heuristic_t h, Output_t output) |
Tracing version of use_heuristic, writes costs for every elimination. | |
template<class Object_t , class Ad_graph_t , class Heuristic_t , class Output_t > | |
int | angel::apply_heuristic (const Ad_graph_t &adg, vector< Object_t > &el_seq, Heuristic_t h, Output_t output) |
Applies heuristic and uses output visitor write costs and graphs for every elimination. | |
template<class Object_t , class Ad_graph_t , class Heuristic1_t , class Heuristic2_t , class Heuristic3_t , class Heuristic4_t , class Heuristic5_t > | |
int | angel::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) |
Applies 5 heuristics to adg and returns the elimination sequence of the cheapest one. | |
template<class Object_t , class Ad_graph_t , class Op_t > | |
int | angel::find_best_subset (const vector< Object_t > &v1, const Ad_graph_t &adg, vector< Object_t > &v2, Op_t op, bool maximize) |
Find best subset of v1 w.r.t. op , skeleton for new heuristics. | |
int | angel::edge_elim_effect (const edge_bool_t be, const c_graph_t &angelLCG, const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) |
Determines the effect, in terms of nontrivial edge count, of performing edge elimination be . | |
int | angel::edge_elim_effect (const EdgeElim ee, const c_graph_t &angelLCG, const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) |
Determines the effect, in terms of nontrivial edge count, of performing edge elimination ee . | |
bool | angel::maintaining_edge_eliminations (const vector< EdgeElim > &bev1, const c_graph_t &angelLCG, const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, vector< EdgeElim > &bev2) |
Filter that selects edge elimination targets that don't increase the nontrivial edge count. | |
bool | angel::reducing_edge_eliminations (const vector< EdgeElim > &bev1, const c_graph_t &angelLCG, const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, vector< EdgeElim > &bev2) |
Filter that selects edge elimination targets that decrease the nontrivial edge count. | |
bool | angel::refill_avoiding_edge_eliminations (const vector< EdgeElim > &bev1, c_graph_t &angelLCG, const refillDependenceMap_t refillDependences, vector< EdgeElim > &bev2) |
Filter that selects edge elimination targets whose refill dependences (a possibly empty set of vertices) have been met (meaning that there is no alternate path for the edge through the vertex). | |
bool | angel::rerouting_considerate_edge_eliminations (const vector< EdgeElim > &bev, const c_graph_t &angelLCG, const std::vector< Transformation > &transformationsPerformedV, vector< EdgeElim > &reroutingConsiderateEdgeElimsV) |
unsigned int | angel::lowestMarkowitzEdgeElim (const vector< EdgeElim > &inEEV, const c_graph_t &angelLCG, vector< EdgeElim > &outEEV) |
bool | angel::reverseModeEdgeElim (const vector< EdgeElim > &inEEV, const c_graph_t &angelLCG, vector< EdgeElim > &outEEV) |
size_t | angel::noncyclicReroutings (const vector< Rerouting > &erv, const std::vector< Transformation > &transformationsPerformedV, const c_graph_t &angelLCG, vector< Rerouting > &noncyclicReroutingsV) |
bool | angel::reducing_reroutings (const vector< Rerouting > &erv, const c_graph_t &angelLCG, const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, vector< Rerouting > &reducingReroutingsV) |
int | angel::transformation_effect (const Transformation t, const c_graph_t &angelLCG, const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) |
bool | angel::all_viable_transformations (c_graph_t &angelLCG, const std::vector< Transformation > &transformationsPerformedV, vector< Transformation > &allViableTransformationsV) |
bool | angel::maintaining_transformations (const vector< Transformation > &tv, const c_graph_t &angelLCG, const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, vector< Transformation > &maintainingTransformationsV) |
bool | angel::reducing_transformations (const vector< Transformation > &tv, const c_graph_t &angelLCG, const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, vector< Transformation > &reducingTransformationsV) |
bool | angel::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 | angel::rerouting_considerate_transformations (const vector< Transformation > &tv, const c_graph_t &angelLCG, const std::vector< Transformation > &transformationsPerformedV, vector< Transformation > &reroutingConsiderateTransformationsV) |
bool | angel::lowest_markowitz_transformations (const vector< Transformation > &tv, const c_graph_t &angelLCG, vector< Transformation > &lowestMarkowitzTransformationsV) |
bool | angel::reverse_mode_transformations (const vector< Transformation > &tv, const c_graph_t &angelLCG, vector< Transformation > &reverseModeTransformationsV) |
Variables | |
forward_mode_vertex_t | angel::forward_mode_vertex |
Forward mode in vertex elimination. | |
reverse_mode_vertex_t | angel::reverse_mode_vertex |
Reverse mode in vertex elimination. | |
lowest_markowitz_vertex_t | angel::lowest_markowitz_vertex |
Lowest Markowitz degree first in vertex elimination. | |
lowest_relative_markowitz_vertex_t | angel::lowest_relative_markowitz_vertex |
Lowest relative Markowitz degree first in vertex elimination. | |
lowest_fill_in_vertex_t | angel::lowest_fill_in_vertex |
Lowest fill-in in vertex elimination. | |
lmmd_vertex_t | angel::lmmd_vertex |
Predefined object of lmmd_vertex_t with weight=1.0. | |
momr_vertex_t | angel::momr_vertex |
Instance of momr_vertex_t, can be used as a function and an argument. | |
moplr_vertex_t | angel::moplr_vertex |
Maximal overall path length reduction in vertex elimination. | |
forward_mode_edge_t | angel::forward_mode_edge |
Forward mode in edge elimination (mixed front and back elimination). | |
reverse_mode_edge_t | angel::reverse_mode_edge |
Reverse mode in edge elimination (mixed front and back elimination). | |
lowest_markowitz_edge_t | angel::lowest_markowitz_edge |
Lowest Markowitz in edge elimination (mixed front and back elimination). | |
lowest_relative_markowitz_edge_t | angel::lowest_relative_markowitz_edge |
Lowest relative Markowitz in edge elimination (mixed front and back elimination). | |
lmmd_edge_t | angel::lmmd_edge |
Predefined object of lmmd_edge_t with weight=1.0. | |
momr_edge_t | angel::momr_edge |
Maximal overall Markowitz reduction in mixed edge elimination. | |
forward_mode_face_t | angel::forward_mode_face |
Forward mode in face elimination. | |
reverse_mode_face_t | angel::reverse_mode_face |
Reverse mode in face elimination. | |
reverse_mode_face_whole_vertex_t | angel::reverse_mode_face_whole_vertex |
Reverse mode emulating vertex elimination with face eliminations. | |
lowest_markowitz_face_t | angel::lowest_markowitz_face |
Lowest Markowitz for face elimination. | |
momr_face_t | angel::momr_face |
Maximal overall Markowitz degree reduction in face elimination. |