Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
frechet::k::kAlgorithm Class Reference

Detailed Description

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.

Author
Peter Schäfer

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< kAlgorithmptr
 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 IntervalMaphorizontalIntervals () const
 
const IntervalMapverticalIntervals () const
 
const struct GreedygreedyResult () const
 
const struct BruteForceoptimalResult () 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::Componentscomponents
 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...
 

Member Typedef Documentation

◆ ptr

typedef boost::shared_ptr<kAlgorithm> frechet::k::kAlgorithm::ptr

smart pointer to an kAlgorithm object

Definition at line 320 of file kalgorithm.h.

◆ Stack

typedef std::vector<std::pair<int, double> > frechet::k::kAlgorithm::Stack
protected

a stack of componentIDs and axis locations. Used by the brute-force algorithm for backtracking.

Definition at line 142 of file kalgorithm.h.

Member Enumeration Documentation

◆ Result

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.

Constructor & Destructor Documentation

◆ kAlgorithm()

kAlgorithm::kAlgorithm ( fs::FreeSpace::ptr  fs)

default constructor

Parameters
fsfree-space diagram data

Definition at line 10 of file kalgorithm.cpp.

Member Function Documentation

◆ bf_backtrack2()

bool kAlgorithm::bf_backtrack2 ( )
private

clear second stack

Returns
always false

Definition at line 367 of file kalgorithm.cpp.

◆ bf_pop1()

bool kAlgorithm::bf_pop1 ( )
private

pop from first stack

Returns
true if the stack contains more elements

Definition at line 356 of file kalgorithm.cpp.

◆ bf_push1()

void kAlgorithm::bf_push1 ( int  i,
double  x 
)
private

push an value to first stack

Parameters
icomponent ID
xlocation on x-axis

Definition at line 351 of file kalgorithm.cpp.

◆ bf_push2()

void kAlgorithm::bf_push2 ( int  i,
double  y 
)
private

push an value to second stack

Parameters
icomponent ID
ylocation on y-axis

Definition at line 362 of file kalgorithm.cpp.

◆ bf_search_1()

bool kAlgorithm::bf_search_1 ( volatile bool *  cancelFlag = 0)
throw (frechet::app::InterruptedException
)
private

run the brute-force algorithm on the x-axis. Results are placed in this->bf.

Parameters
cancelFlaga flag that indicates interruption by the user.
Exceptions
InterruptedExceptionwhen the user requests and interruption
Returns
true if there is a result

Definition at line 372 of file kalgorithm.cpp.

◆ bf_search_2()

bool kAlgorithm::bf_search_2 ( )
throw (frechet::app::InterruptedException
)
private

run the brute-force algorithm on the y-axis. Results are placed in this->bf.

Exceptions
InterruptedExceptionwhen the user requests and interruption
Returns
true if there is a result

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.

◆ bf_top1()

std::pair< int, double > & kAlgorithm::bf_top1 ( )
private
Returns
top of first backtracking stack

Definition at line 341 of file kalgorithm.cpp.

◆ bf_top2()

std::pair< int, double > & kAlgorithm::bf_top2 ( )
private
Returns
top of second backtracking stack

Definition at line 346 of file kalgorithm.cpp.

◆ bruteForceFinished

void frechet::k::kAlgorithm::bruteForceFinished ( )
signal

raised when the 'brute-force' algorithm finishes Connected to UI components to update their states.

◆ bruteForceIteration

void frechet::k::kAlgorithm::bruteForceIteration ( int  )
signal

raised after an iteration of the 'brute-force' algorithm Connected to UI components to update their states.

◆ greedy_1()

int kAlgorithm::greedy_1 ( const IntervalMap map,
const data::Interval range 
)
private

run the greedy algorithm on the first axis

Parameters
mapintervals on first axis
rangeaxis domain
Returns
min. number of components. Negative values indicate no result.

Definition at line 162 of file kalgorithm.cpp.

◆ greedy_12()

int kAlgorithm::greedy_12 ( const IntervalMap map1,
const data::Interval range1,
const IntervalMap map2,
const data::Interval range2,
int &  k_1 
)
private

run the greedy algorithm on tow axes

Parameters
map1intervals on first axis
range1first axis domain
map2intervals on second axis
range2second axis domain
k_1on return, hold result of first axis
Returns
min. number of components. Negative values indicate no result.

Definition at line 145 of file kalgorithm.cpp.

◆ greedy_2()

int kAlgorithm::greedy_2 ( const IntervalMap map,
const data::Interval range 
)
private

run the greedy algorithm on the second axis

Parameters
mapintervals on first axis
rangeaxis domain
Returns
min. number of components. Negative values indicate no result.

Definition at line 202 of file kalgorithm.cpp.

◆ greedy_xy()

int kAlgorithm::greedy_xy ( )
private

run the greedy algorithm (x-axis first)

Returns
k_xy, min. number of components. Negative values indicate no result.

Definition at line 119 of file kalgorithm.cpp.

◆ greedy_yx()

int kAlgorithm::greedy_yx ( )
private

run greedy algorithm (y-axis first)

Returns
k_yx, min. number of components. Negative values indicate no result.

Definition at line 132 of file kalgorithm.cpp.

◆ greedyFinished

void frechet::k::kAlgorithm::greedyFinished ( )
signal

raised when the 'greedy' algorithm finishes Connected to UI components to update their states.

◆ greedyResult()

const struct Greedy& frechet::k::kAlgorithm::greedyResult ( ) const
inline
Returns
results of the greedy algorithm (if available)

Definition at line 242 of file kalgorithm.h.

◆ horizontalIntervals()

const IntervalMap& frechet::k::kAlgorithm::horizontalIntervals ( ) const
inline
Returns
the working-set of currently selected horizontal intervals

Definition at line 196 of file kalgorithm.h.

◆ optimalResult()

const struct BruteForce& frechet::k::kAlgorithm::optimalResult ( ) const
inline
Returns
result of the brute-force algorithm (if available). This result is optimal.

Definition at line 289 of file kalgorithm.h.

◆ runBruteForce()

int kAlgorithm::runBruteForce ( volatile bool *  cancelFlag = 0)
throw (frechet::app::InterruptedException
)

run the brute force algorithm. The greedy algorithm must have been run before!

Parameters
cancelFlaga 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.
Exceptions
InterruptedExceptionwhen the user requests and interruption
Returns
result of the brute-force algorithm Negative values indicate that no result is available.

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.

◆ runGreedy()

int kAlgorithm::runGreedy ( )

run the greedy algorithm

Returns
min. number of components. Negative values indicate that no result is available.

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.

◆ setupMapsAndResults()

void kAlgorithm::setupMapsAndResults ( )
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.

◆ verticalIntervals()

const IntervalMap& frechet::k::kAlgorithm::verticalIntervals ( ) const
inline
Returns
the working-set of currently selected vertical intervals

Definition at line 198 of file kalgorithm.h.

◆ working_add() [1/2]

void kAlgorithm::working_add ( const MappedInterval ival)
protected

add a mapped interval to the current working-set

Parameters
ivalan interval with a component

Definition at line 321 of file kalgorithm.cpp.

◆ working_add() [2/2]

void kAlgorithm::working_add ( component_id_t  comp)
protected

add a mapped interval to the current working-set

Parameters
compa free-space component

Definition at line 329 of file kalgorithm.cpp.

◆ working_remove() [1/2]

void kAlgorithm::working_remove ( const MappedInterval ival)
protected

remove a mapped interval from the current working-set

Parameters
ivalan interval with a component

Definition at line 325 of file kalgorithm.cpp.

◆ working_remove() [2/2]

void kAlgorithm::working_remove ( component_id_t  comp)
protected

remove a mapped interval from the current working-set

Parameters
compa free-space component

Definition at line 335 of file kalgorithm.cpp.

Friends And Related Function Documentation

◆ KWorkerJob

friend class KWorkerJob
friend

background worker job for the k-Frechet algorithm

Definition at line 344 of file kalgorithm.h.

Member Data Documentation

◆ bf

struct BruteForce frechet::k::kAlgorithm::bf
private

result of the brute-force algorithm

Definition at line 293 of file kalgorithm.h.

◆ components

const fs::Components& frechet::k::kAlgorithm::components
protected

connected components of the free-space diagram

Definition at line 147 of file kalgorithm.h.

◆ domain

data::IntervalPair frechet::k::kAlgorithm::domain
protected

the x-axis and the y-axis of the free-space diagram (from Grid)

Definition at line 151 of file kalgorithm.h.

◆ greedy

struct Greedy frechet::k::kAlgorithm::greedy
private

results of the greedy algorithm

Definition at line 246 of file kalgorithm.h.

◆ working

struct frechet::k::kAlgorithm::WorkingSet frechet::k::kAlgorithm::working
protected

The documentation for this class was generated from the following files: