Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
kalgorithm.h
Go to the documentation of this file.
1 #ifndef ALGORITHMBASE_H
2 #define ALGORITHMBASE_H
3 
4 #include <freespace.h>
5 #include <app/workerthread.h>
6 
7 #include <exception>
8 #include <stack>
9 #include <functional>
10 
11 //#include <boost/thread/mutex.hpp>
12 #include <QMutex>
13 
14 // throw (...) considered deprecated (but still useful)
15 #if defined __GNUC__
16 # pragma GCC diagnostic ignored "-Wdeprecated"
17 #elif defined _MSC_VER
18 # pragma warning( disable : 4290 )
19 #endif
20 
21 namespace frechet { namespace k {
22 
33 public:
37 
40  : Interval(), componentID(-1) {}
41 
47  MappedInterval(const Interval &ival, int compID)
48  : Interval(ival), componentID(compID) {}
49 
58  bool operator<(const MappedInterval &that) const;
64  bool operator==(const MappedInterval &that) const;
65 };
71 typedef std::vector<MappedInterval> IntervalMap;
72 
73 
113 class kAlgorithm : public QObject {
114  Q_OBJECT
115 signals:
118  void greedyFinished();
121  void bruteForceIteration(int);
124  void bruteForceFinished();
125  //void bruteForceCancelled();
126 
127 public:
131  enum Result {
132  UNKNOWN = -3,
133  RUNNING = -2,
135  };
136 
137 protected:
142  typedef std::vector<std::pair<int, double>> Stack;
143 
152 
158  struct WorkingSet {
167  QMutex lock;
168 
170  WorkingSet() : hmap(),vmap(),set(),lock() {}
171  } working;
172 
177  void working_add(const MappedInterval &ival);
182  void working_remove(const MappedInterval &ival);
187  void working_add(component_id_t comp);
192  void working_remove(component_id_t comp);
193 
194 public:
196  const IntervalMap &horizontalIntervals() const { return working.hmap; }
198  const IntervalMap &verticalIntervals() const { return working.vmap; }
199 
207  struct Greedy {
209  int k_x;
211  int k_y;
213  int k_xy;
215  int k_yx;
218 
220  bool valid() const { return k_yx > 0; }
221 
227  Result lowerBound() const { return (Result) std::max(k_x, k_y); }
233  Result upperBound() const { return (Result) std::min(k_xy, k_yx); }
234 
237  result()
238  { }
239  };
240 
242  const struct Greedy &greedyResult() const { return greedy; }
243 
244 private:
246  struct Greedy greedy;
247 
248 public:
258  struct BruteForce {
259  /* Bounds for the BF algorthm.
260  * Initially from the Greedy results; k_min may increase when the BF returns unsucessfully
261  */
263  int k_min = 0;
265  int k_max = 0;
272 
277 
279  bool valid() const { return k_optimal > 0; }
280 
282  BruteForce() : k_min(0),k_max(0),
284  result(), stack1(), stack2()
285  { }
286  };
287 
289  const struct BruteForce &optimalResult() const { return bf; }
290 
291 private:
293  struct BruteForce bf;
294 
296  std::pair<int, double> &bf_top1();
298  std::pair<int, double> &bf_top2();
299 
303  void bf_push1(int i, double x);
306  bool bf_pop1();
310  void bf_push2(int i, double y);
313  bool bf_backtrack2();
314 
316  void setupMapsAndResults();
317 
318 public:
320  typedef boost::shared_ptr<kAlgorithm> ptr;
321 
325 
328  int runGreedy();
329 
340  int runBruteForce(volatile bool *cancelFlag = 0) throw(frechet::app::InterruptedException);
341 
342 private:
344  friend class KWorkerJob;
345 
348  int greedy_xy();
351  int greedy_yx();
352 
360  int greedy_12(
361  const IntervalMap &map1, const data::Interval &range1,
362  const IntervalMap &map2, const data::Interval &range2,
363  int &k_1);
364 
369  int greedy_1(const IntervalMap &map, const data::Interval &range);
374  int greedy_2(const IntervalMap &map, const data::Interval &range);
375 
380  bool bf_search_1(volatile bool *cancelFlag = 0) throw(frechet::app::InterruptedException);
384  bool bf_search_2() throw(frechet::app::InterruptedException);
385 };
386 
390 class KWorkerJob : public frechet::app::WorkerJob {
391 private:
394 public:
397  KWorkerJob(kAlgorithm *owner) : alg(owner) {}
398 
400  virtual void runJob() {
401  alg->runBruteForce(&cancelRequested);
402  }
403 
406  virtual void afterInterrupted() {
407  emit alg->bruteForceFinished();
408  }
409 };
410 
411 } } // namespaces
412 
413 #endif // ALGORITHMBASE_H
void bf_push1(int i, double x)
push an value to first stack
Definition: kalgorithm.cpp:351
initial status; the algorithm has not ye been run
Definition: kalgorithm.h:132
The k-Frechet algorithm.
Definition: kalgorithm.h:113
MappedInterval(const Interval &ival, int compID)
default constructor
Definition: kalgorithm.h:47
Result upperBound() const
get an upper bound for the optimal result. Observe that k_optimal <= k_xy,k_yx
Definition: kalgorithm.h:233
void greedyFinished()
raised when the 'greedy' algorithm finishes Connected to UI components to update their states.
const struct BruteForce & optimalResult() const
Definition: kalgorithm.h:289
int k_x
number of components that is needed to cover the x-axis. 0 if the x-axis can not be covered.
Definition: kalgorithm.h:209
const fs::Components & components
connected components of the free-space diagram
Definition: kalgorithm.h:147
IntervalMap vmap
map to vertical (y-)axis
Definition: kalgorithm.h:162
data::BitSet set
subset of currently selected interval
Definition: kalgorithm.h:164
kAlgorithm * alg
pointer to kAlgorithm object
Definition: kalgorithm.h:393
int k_optimal
optimal value so far
Definition: kalgorithm.h:271
const IntervalMap & horizontalIntervals() const
Definition: kalgorithm.h:196
bool bf_search_1(volatile bool *cancelFlag=0)
run the brute-force algorithm on the x-axis. Results are placed in this->bf.
Definition: kalgorithm.cpp:372
void working_remove(const MappedInterval &ival)
remove a mapped interval from the current working-set
Definition: kalgorithm.cpp:325
struct BruteForce bf
result of the brute-force algorithm
Definition: kalgorithm.h:293
global definitions for all algorithms.
Results of the Greedy algorithm.
Definition: kalgorithm.h:207
data::IntervalPair domain
the x-axis and the y-axis of the free-space diagram (from Grid)
Definition: kalgorithm.h:151
std::vector< MappedInterval > IntervalMap
a vector of MappedInterval objects. Usually these are sorted according to the natural ordering impose...
Definition: kalgorithm.h:71
void bf_push2(int i, double y)
push an value to second stack
Definition: kalgorithm.cpp:362
indicates that the algorithm is currently running
Definition: kalgorithm.h:133
Result lowerBound() const
get a lower bound for the optimal result. Observe that k_x,k_y <= k_optimal
Definition: kalgorithm.h:227
std::vector< std::pair< int, double > > Stack
a stack of componentIDs and axis locations. Used by the brute-force algorithm for backtracking.
Definition: kalgorithm.h:142
int runBruteForce(volatile bool *cancelFlag=0)
run the brute force algorithm. The greedy algorithm must have been run before!
Definition: kalgorithm.cpp:267
a pair of horizonal / vertical intervals.
Definition: interval.h:456
IntervalMap hmap
map to horizontal (x-)axis
Definition: kalgorithm.h:160
int k_iteration
optimal value of last iteration
Definition: kalgorithm.h:269
int k_current
current number of selected components
Definition: kalgorithm.h:267
attaches a component ID to an interval
Definition: kalgorithm.h:32
int greedy_1(const IntervalMap &map, const data::Interval &range)
run the greedy algorithm on the first axis
Definition: kalgorithm.cpp:162
int runGreedy()
run the greedy algorithm
Definition: kalgorithm.cpp:78
void setupMapsAndResults()
initialize working-set data structures
Definition: kalgorithm.cpp:31
virtual void runJob()
run the brute-force algorithm
Definition: kalgorithm.h:400
data::BitSet result
subsset of selected components
Definition: kalgorithm.h:274
int greedy_yx()
run greedy algorithm (y-axis first)
Definition: kalgorithm.cpp:132
const struct Greedy & greedyResult() const
Definition: kalgorithm.h:242
int k_yx
number of components, when scanning the y-axis first. 0 if the axes can no be covered.
Definition: kalgorithm.h:215
bool operator<(const MappedInterval &that) const
comparison operator, needed for sorting a list of MappedInterval objects. We first compare the lower ...
Definition: kalgorithm.cpp:494
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
Definition: kalgorithm.h:246
bool bf_pop1()
pop from first stack
Definition: kalgorithm.cpp:356
void working_add(const MappedInterval &ival)
add a mapped interval to the current working-set
Definition: kalgorithm.cpp:321
std::pair< int, double > & bf_top2()
Definition: kalgorithm.cpp:346
Free-Space connected components and their projections to the domain axes.
Definition: components.h:27
Current working set of mapped intervals. Horizontal intervals are mapped to the range [0....
Definition: kalgorithm.h:158
int k_max
upper bound derived from greedy results. k_max = min{greedy.k_xy,greedy.k_yx}
Definition: kalgorithm.h:265
bool bf_search_2()
run the brute-force algorithm on the y-axis. Results are placed in this->bf.
Definition: kalgorithm.cpp:437
kAlgorithm(fs::FreeSpace::ptr fs)
default constructor
Definition: kalgorithm.cpp:10
data::BitSet result
subset of selected components
Definition: kalgorithm.h:217
results of the brute-force algorithm
Definition: kalgorithm.h:258
double min(double a, double b)
minimum function with checks for NAN
Definition: numeric.h:222
KWorkerJob(kAlgorithm *owner)
default constructor
Definition: kalgorithm.h:397
Result
negative values for k indicate the special conditions of the computation
Definition: kalgorithm.h:131
A simple bit vector of fixed size.
Definition: bitset.h:16
bool bf_backtrack2()
clear second stack
Definition: kalgorithm.cpp:367
background worker job for running the k-Frechet brute-force algorithm.
Definition: kalgorithm.h:390
int greedy_2(const IntervalMap &map, const data::Interval &range)
run the greedy algorithm on the second axis
Definition: kalgorithm.cpp:202
bool operator==(const MappedInterval &that) const
equality operator, needed for sorting a list of MappedInterval objects.
Definition: kalgorithm.cpp:508
Stack stack1
stacks used for backtracking
Definition: kalgorithm.h:276
int k_min
lower bound derived from greedy results. k_min = max{greedy.k_x,greedy.k_y}
Definition: kalgorithm.h:263
void bruteForceFinished()
raised when the 'brute-force' algorithm finishes Connected to UI components to update their states.
Greedy()
empty constructor
Definition: kalgorithm.h:236
std::pair< int, double > & bf_top1()
Definition: kalgorithm.cpp:341
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.
Definition: kalgorithm.h:211
MappedInterval()
empty constructor; creates an invalid interval
Definition: kalgorithm.h:39
unsigned int component_id_t
used as identifier for free-space components
Definition: types.h:74
boost::shared_ptr< kAlgorithm > ptr
smart pointer to an kAlgorithm object
Definition: kalgorithm.h:320
an interval of two double values.
Definition: interval.h:31
virtual void afterInterrupted()
called after the algorithm was interrupted Raise a Qt signal that triggers UI updates.
Definition: kalgorithm.h:406
int k_xy
number of components, when scanning the x-axis first. 0 if the axes can no be covered.
Definition: kalgorithm.h:213
there is no solution at all
Definition: kalgorithm.h:134
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
Definition: kalgorithm.cpp:145
boost::shared_ptr< FreeSpace > ptr
smart pointer to FreeSpace object
Definition: freespace.h:92
int greedy_xy()
run the greedy algorithm (x-axis first)
Definition: kalgorithm.cpp:119
double max(double a, double b)
maximum function with checks for NAN
Definition: numeric.h:233
const IntervalMap & verticalIntervals() const
Definition: kalgorithm.h:198