![]() |
Fréchet View
1.6.0
A Tool for Exploring Fréchet Distance Algorithms
|
The k-Frechet algorithm.
Given a set of components, and their projections to the domain axes, select a subset such that both axes are covered. Don't use more than k components;
This is the decision version of the problem. As result, it returns the minimum number of k components.
There is a 'greedy' variant and a 'brute-force' variant. The greedy variant returns two appromixation values for k. The brute-force variant returns the optimal value for k.
Note that the greedy algorithm is optimal for one axis, and has an approximation factor 2 for both axes. We can use the intermediate results of the greedy algorithms as bounds for the optimal results.
Since the brute-force variant has exponential time complexity, it is run in a worker thread that can be interrupted by the user.
Basically, the brute-force algorithm is an exhaustive search, picking at most k elements from a base set. Breadth-first search is not appropriate, we are using a depth-first approach.
The depth of the search tree is limited, but can still become huge. For practicality, we use iterative deepening. The tree depth is first limited to k_min. With each iteration, the tree-depth limit is increased by one, until we reach k_max.
The iterative deepening approach performs redundant work, but it stops at the first solution. This seems to be a huge practical advantage over an exhaustive full-depth search.
The amount of redundant work is tolerable, considering exponential growth of the seach tree.
Definition at line 113 of file kalgorithm.h.
#include <kalgorithm.h>
Inherits QObject.
Classes | |
struct | BruteForce |
results of the brute-force algorithm More... | |
struct | Greedy |
Results of the Greedy algorithm. More... | |
struct | WorkingSet |
Current working set of mapped intervals. Horizontal intervals are mapped to the range [0..n] Vertical intervals are mapped to the range [n..n+m]. More... | |
Public Types | |
enum | Result { UNKNOWN = -3, RUNNING = -2, NO_SOLUTION = -1 } |
negative values for k indicate the special conditions of the computation More... | |
typedef boost::shared_ptr< kAlgorithm > | ptr |
smart pointer to an kAlgorithm object More... | |
Signals | |
void | greedyFinished () |
raised when the 'greedy' algorithm finishes Connected to UI components to update their states. More... | |
void | bruteForceIteration (int) |
raised after an iteration of the 'brute-force' algorithm Connected to UI components to update their states. More... | |
void | bruteForceFinished () |
raised when the 'brute-force' algorithm finishes Connected to UI components to update their states. More... | |
Public Member Functions | |
const IntervalMap & | horizontalIntervals () const |
const IntervalMap & | verticalIntervals () const |
const struct Greedy & | greedyResult () const |
const struct BruteForce & | optimalResult () const |
kAlgorithm (fs::FreeSpace::ptr fs) | |
default constructor More... | |
int | runGreedy () |
run the greedy algorithm More... | |
int | runBruteForce (volatile bool *cancelFlag=0) throw (frechet::app::InterruptedException) |
run the brute force algorithm. The greedy algorithm must have been run before! More... | |
Protected Types | |
typedef std::vector< std::pair< int, double > > | Stack |
a stack of componentIDs and axis locations. Used by the brute-force algorithm for backtracking. More... | |
Protected Member Functions | |
void | working_add (const MappedInterval &ival) |
add a mapped interval to the current working-set More... | |
void | working_remove (const MappedInterval &ival) |
remove a mapped interval from the current working-set More... | |
void | working_add (component_id_t comp) |
add a mapped interval to the current working-set More... | |
void | working_remove (component_id_t comp) |
remove a mapped interval from the current working-set More... | |
Protected Attributes | |
const fs::Components & | components |
connected components of the free-space diagram More... | |
data::IntervalPair | domain |
the x-axis and the y-axis of the free-space diagram (from Grid) More... | |
struct frechet::k::kAlgorithm::WorkingSet | working |
Private Member Functions | |
std::pair< int, double > & | bf_top1 () |
std::pair< int, double > & | bf_top2 () |
void | bf_push1 (int i, double x) |
push an value to first stack More... | |
bool | bf_pop1 () |
pop from first stack More... | |
void | bf_push2 (int i, double y) |
push an value to second stack More... | |
bool | bf_backtrack2 () |
clear second stack More... | |
void | setupMapsAndResults () |
initialize working-set data structures More... | |
int | greedy_xy () |
run the greedy algorithm (x-axis first) More... | |
int | greedy_yx () |
run greedy algorithm (y-axis first) More... | |
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 More... | |
int | greedy_1 (const IntervalMap &map, const data::Interval &range) |
run the greedy algorithm on the first axis More... | |
int | greedy_2 (const IntervalMap &map, const data::Interval &range) |
run the greedy algorithm on the second axis More... | |
bool | bf_search_1 (volatile bool *cancelFlag=0) throw (frechet::app::InterruptedException) |
run the brute-force algorithm on the x-axis. Results are placed in this->bf. More... | |
bool | bf_search_2 () throw (frechet::app::InterruptedException) |
run the brute-force algorithm on the y-axis. Results are placed in this->bf. More... | |
Private Attributes | |
struct Greedy | greedy |
results of the greedy algorithm More... | |
struct BruteForce | bf |
result of the brute-force algorithm More... | |
Friends | |
class | KWorkerJob |
background worker job for the k-Frechet algorithm More... | |
typedef boost::shared_ptr<kAlgorithm> frechet::k::kAlgorithm::ptr |
smart pointer to an kAlgorithm object
Definition at line 320 of file kalgorithm.h.
|
protected |
a stack of componentIDs and axis locations. Used by the brute-force algorithm for backtracking.
Definition at line 142 of file kalgorithm.h.
negative values for k indicate the special conditions of the computation
Enumerator | |
---|---|
UNKNOWN | initial status; the algorithm has not ye been run |
RUNNING | indicates that the algorithm is currently running |
NO_SOLUTION | there is no solution at all |
Definition at line 131 of file kalgorithm.h.
kAlgorithm::kAlgorithm | ( | fs::FreeSpace::ptr | fs | ) |
default constructor
fs | free-space diagram data |
Definition at line 10 of file kalgorithm.cpp.
|
private |
|
private |
pop from first stack
Definition at line 356 of file kalgorithm.cpp.
|
private |
push an value to first stack
i | component ID |
x | location on x-axis |
Definition at line 351 of file kalgorithm.cpp.
|
private |
push an value to second stack
i | component ID |
y | location on y-axis |
Definition at line 362 of file kalgorithm.cpp.
|
private |
run the brute-force algorithm on the x-axis. Results are placed in this->bf.
cancelFlag | a flag that indicates interruption by the user. |
InterruptedException | when the user requests and interruption |
Definition at line 372 of file kalgorithm.cpp.
|
private |
run the brute-force algorithm on the y-axis. Results are placed in this->bf.
InterruptedException | when the user requests and interruption |
Search vertical range second. For the second axis we use again the greedy approach (just without backtracking).
In addition, we must look for already selected intervals. We check whether components are already in the working set, but we do not update the working set.
Definition at line 437 of file kalgorithm.cpp.
|
private |
Definition at line 341 of file kalgorithm.cpp.
|
private |
Definition at line 346 of file kalgorithm.cpp.
|
signal |
raised when the 'brute-force' algorithm finishes Connected to UI components to update their states.
|
signal |
raised after an iteration of the 'brute-force' algorithm Connected to UI components to update their states.
|
private |
run the greedy algorithm on the first axis
map | intervals on first axis |
range | axis domain |
Definition at line 162 of file kalgorithm.cpp.
|
private |
run the greedy algorithm on tow axes
map1 | intervals on first axis |
range1 | first axis domain |
map2 | intervals on second axis |
range2 | second axis domain |
k_1 | on return, hold result of first axis |
Definition at line 145 of file kalgorithm.cpp.
|
private |
run the greedy algorithm on the second axis
map | intervals on first axis |
range | axis domain |
Definition at line 202 of file kalgorithm.cpp.
|
private |
run the greedy algorithm (x-axis first)
Definition at line 119 of file kalgorithm.cpp.
|
private |
run greedy algorithm (y-axis first)
Definition at line 132 of file kalgorithm.cpp.
|
signal |
raised when the 'greedy' algorithm finishes Connected to UI components to update their states.
|
inline |
Definition at line 242 of file kalgorithm.h.
|
inline |
Definition at line 196 of file kalgorithm.h.
|
inline |
Definition at line 289 of file kalgorithm.h.
int kAlgorithm::runBruteForce | ( | volatile bool * | cancelFlag = 0 | ) | |
throw | ( | frechet::app::InterruptedException | |||
) |
run the brute force algorithm. The greedy algorithm must have been run before!
cancelFlag | a flag that indicates interruption by the user. The algorithm polls this flag regularly and throws an InterruptedException when the flag is found to be true. The application logic will catch the exception and clean up. |
InterruptedException | when the user requests and interruption |
Two search strategies:
(1) set k_max (known from Greedy) and perform a depth-first search limited by k_max. Store the best solution whenever one is found.
Disadvantage: we must traverse the whole search tree, and it could be huge.
->(2) iterative deepening starting at k_min (known from Greedy). Keep on incrementing the search depth until a solution is found.
This strategy does some redundant work, but it can stop at the first found solution. With exponential growth, the amount of redundant work becomes less significant.
Idea: it would be more effective if we could exploit information from previous iterations. (like, store the quality (length) of a partial solution? Sort choices?)
Definition at line 267 of file kalgorithm.cpp.
int kAlgorithm::runGreedy | ( | ) |
run the greedy algorithm
We run the Greedy algorithm in two directions x-axis then y-axis and y-axis then x-axis and select the minimum result.
If the first fails, we can return unsuccessful.
More variations are conceivable: don't start at 0 but pick the starting point at random. Scan left-to-right and right-to-left. However, this is not likely to improve results.
Definition at line 78 of file kalgorithm.cpp.
|
private |
initialize working-set data structures
Insert the intervals into the maps.
For the sake of this algorithm, we consider the intervals to be OPEN at the right. We do this to avoid unwanted overlaps.
Horizontal intervals are in the range [0..n] Vertical intervals are shifted to the range [n..n+m] (so that we can store them in the same tree, but still keep them separated)
Definition at line 31 of file kalgorithm.cpp.
|
inline |
Definition at line 198 of file kalgorithm.h.
|
protected |
add a mapped interval to the current working-set
ival | an interval with a component |
Definition at line 321 of file kalgorithm.cpp.
|
protected |
add a mapped interval to the current working-set
comp | a free-space component |
Definition at line 329 of file kalgorithm.cpp.
|
protected |
remove a mapped interval from the current working-set
ival | an interval with a component |
Definition at line 325 of file kalgorithm.cpp.
|
protected |
remove a mapped interval from the current working-set
comp | a free-space component |
Definition at line 335 of file kalgorithm.cpp.
|
friend |
background worker job for the k-Frechet algorithm
Definition at line 344 of file kalgorithm.h.
|
private |
result of the brute-force algorithm
Definition at line 293 of file kalgorithm.h.
|
protected |
connected components of the free-space diagram
Definition at line 147 of file kalgorithm.h.
|
protected |
the x-axis and the y-axis of the free-space diagram (from Grid)
Definition at line 151 of file kalgorithm.h.
|
private |
results of the greedy algorithm
Definition at line 246 of file kalgorithm.h.
|
protected |