1 #ifndef ALGORITHMBASE_H 2 #define ALGORITHMBASE_H 16 # pragma GCC diagnostic ignored "-Wdeprecated" 17 #elif defined _MSC_VER 18 # pragma warning( disable : 4290 ) 21 namespace frechet {
namespace k {
142 typedef std::vector<std::pair<int, double>>
Stack;
296 std::pair<int, double> &
bf_top1();
298 std::pair<int, double> &
bf_top2();
320 typedef boost::shared_ptr<kAlgorithm>
ptr;
380 bool bf_search_1(volatile
bool *cancelFlag = 0) throw(
frechet::app::InterruptedException);
413 #endif // ALGORITHMBASE_H void bf_push1(int i, double x)
push an value to first stack
initial status; the algorithm has not ye been run
MappedInterval(const Interval &ival, int compID)
default constructor
Result upperBound() const
get an upper bound for the optimal result. Observe that k_optimal <= k_xy,k_yx
void greedyFinished()
raised when the 'greedy' algorithm finishes Connected to UI components to update their states.
const struct BruteForce & optimalResult() const
int k_x
number of components that is needed to cover the x-axis. 0 if the x-axis can not be covered.
const fs::Components & components
connected components of the free-space diagram
IntervalMap vmap
map to vertical (y-)axis
data::BitSet set
subset of currently selected interval
kAlgorithm * alg
pointer to kAlgorithm object
int k_optimal
optimal value so far
const IntervalMap & horizontalIntervals() const
bool bf_search_1(volatile bool *cancelFlag=0)
run the brute-force algorithm on the x-axis. Results are placed in this->bf.
void working_remove(const MappedInterval &ival)
remove a mapped interval from the current working-set
struct BruteForce bf
result of the brute-force algorithm
global definitions for all algorithms.
Results of the Greedy algorithm.
data::IntervalPair domain
the x-axis and the y-axis of the free-space diagram (from Grid)
std::vector< MappedInterval > IntervalMap
a vector of MappedInterval objects. Usually these are sorted according to the natural ordering impose...
void bf_push2(int i, double y)
push an value to second stack
indicates that the algorithm is currently running
BruteForce()
empty constructor
Result lowerBound() const
get a lower bound for the optimal result. Observe that k_x,k_y <= k_optimal
std::vector< std::pair< int, double > > Stack
a stack of componentIDs and axis locations. Used by the brute-force algorithm for backtracking.
int runBruteForce(volatile bool *cancelFlag=0)
run the brute force algorithm. The greedy algorithm must have been run before!
a pair of horizonal / vertical intervals.
IntervalMap hmap
map to horizontal (x-)axis
int k_iteration
optimal value of last iteration
int k_current
current number of selected components
attaches a component ID to an interval
int greedy_1(const IntervalMap &map, const data::Interval &range)
run the greedy algorithm on the first axis
WorkingSet()
empty constructor
int runGreedy()
run the greedy algorithm
void setupMapsAndResults()
initialize working-set data structures
virtual void runJob()
run the brute-force algorithm
data::BitSet result
subsset of selected components
int greedy_yx()
run greedy algorithm (y-axis first)
const struct Greedy & greedyResult() const
int k_yx
number of components, when scanning the y-axis first. 0 if the axes can no be covered.
bool operator<(const MappedInterval &that) const
comparison operator, needed for sorting a list of MappedInterval objects. We first compare the lower ...
void bruteForceIteration(int)
raised after an iteration of the 'brute-force' algorithm Connected to UI components to update their s...
struct Greedy greedy
results of the greedy algorithm
bool bf_pop1()
pop from first stack
void working_add(const MappedInterval &ival)
add a mapped interval to the current working-set
std::pair< int, double > & bf_top2()
Free-Space connected components and their projections to the domain axes.
Current working set of mapped intervals. Horizontal intervals are mapped to the range [0....
int k_max
upper bound derived from greedy results. k_max = min{greedy.k_xy,greedy.k_yx}
bool bf_search_2()
run the brute-force algorithm on the y-axis. Results are placed in this->bf.
kAlgorithm(fs::FreeSpace::ptr fs)
default constructor
data::BitSet result
subset of selected components
results of the brute-force algorithm
double min(double a, double b)
minimum function with checks for NAN
KWorkerJob(kAlgorithm *owner)
default constructor
Result
negative values for k indicate the special conditions of the computation
A simple bit vector of fixed size.
bool bf_backtrack2()
clear second stack
background worker job for running the k-Frechet brute-force algorithm.
int greedy_2(const IntervalMap &map, const data::Interval &range)
run the greedy algorithm on the second axis
bool operator==(const MappedInterval &that) const
equality operator, needed for sorting a list of MappedInterval objects.
Stack stack1
stacks used for backtracking
int k_min
lower bound derived from greedy results. k_min = max{greedy.k_x,greedy.k_y}
void bruteForceFinished()
raised when the 'brute-force' algorithm finishes Connected to UI components to update their states.
Greedy()
empty constructor
std::pair< int, double > & bf_top1()
struct frechet::k::kAlgorithm::WorkingSet working
int k_y
number of components that is needed to cover the y-axis. 0 if the y-axis can not be covered.
MappedInterval()
empty constructor; creates an invalid interval
unsigned int component_id_t
used as identifier for free-space components
boost::shared_ptr< kAlgorithm > ptr
smart pointer to an kAlgorithm object
an interval of two double values.
virtual void afterInterrupted()
called after the algorithm was interrupted Raise a Qt signal that triggers UI updates.
int k_xy
number of components, when scanning the x-axis first. 0 if the axes can no be covered.
there is no solution at all
int greedy_12(const IntervalMap &map1, const data::Interval &range1, const IntervalMap &map2, const data::Interval &range2, int &k_1)
run the greedy algorithm on tow axes
boost::shared_ptr< FreeSpace > ptr
smart pointer to FreeSpace object
int greedy_xy()
run the greedy algorithm (x-axis first)
double max(double a, double b)
maximum function with checks for NAN
const IntervalMap & verticalIntervals() const