heuristics.hpp File Reference

#include <vector>
#include "angel_types.hpp"
#include "angel_io.hpp"
#include "eliminations.hpp"
#include "reroutings.hpp"
#include "heuristics_impl.hpp"

Include dependency graph for heuristics.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces

namespace  angel

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...

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.


Generated on Wed Mar 11 10:33:18 2009 for angel by  doxygen 1.5.3