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

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

enum frechet::k::kAlgorithm::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

fs	free-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

i	component ID
x	location 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

i	component ID
y	location 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

cancelFlag a flag that indicates interruption by the user.

Exceptions

InterruptedException when 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

InterruptedException when 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

map	intervals on first axis
range	axis 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

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

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

map	intervals on first axis
range	axis 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

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.

Exceptions

InterruptedException when 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

ival	an 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

comp	a 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

ival	an 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

comp	a 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:

include/frechet/k_frechet/kalgorithm.h
src/frechet/k_frechet/kalgorithm.cpp

Detailed Description

Classes

Public Types

Signals

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Friends

Member Typedef Documentation

◆ ptr

◆ Stack

Member Enumeration Documentation

◆ Result

Constructor & Destructor Documentation

◆ kAlgorithm()

Member Function Documentation

◆ bf_backtrack2()

◆ bf_pop1()

◆ bf_push1()

◆ bf_push2()

◆ bf_search_1()

◆ bf_search_2()

◆ bf_top1()

◆ bf_top2()

◆ bruteForceFinished

◆ bruteForceIteration

◆ greedy_1()

◆ greedy_12()

◆ greedy_2()

◆ greedy_xy()

◆ greedy_yx()

◆ greedyFinished

◆ greedyResult()

◆ horizontalIntervals()

◆ optimalResult()

◆ runBruteForce()

◆ runGreedy()

◆ setupMapsAndResults()

◆ verticalIntervals()

◆ working_add() [1/2]

◆ working_add() [2/2]

◆ working_remove() [1/2]

◆ working_remove() [2/2]

Friends And Related Function Documentation

◆ KWorkerJob

Member Data Documentation

◆ bf

◆ components

◆ domain

◆ greedy

◆ working