frechet::k::kAlgorithm::Greedy Struct Reference

Detailed Description

Results of the Greedy algorithm.

The greedy algorithms scans first the x-axis, then the y-axis. It can be run in reversed order, producing a valid result, too. We usually run both variants to get better appromiation bounds for the brute-force variant.

Definition at line 207 of file kalgorithm.h.

#include <kalgorithm.h>

Public Member Functions
bool	valid () const
Result	lowerBound () const
	get a lower bound for the optimal result. Observe that k_x,k_y <= k_optimal More...
Result	upperBound () const
	get an upper bound for the optimal result. Observe that k_optimal <= k_xy,k_yx More...
	Greedy ()
	empty constructor More...

Public Attributes
int	k_x
	number of components that is needed to cover the x-axis. 0 if the x-axis can not be covered. More...
int	k_y
	number of components that is needed to cover the y-axis. 0 if the y-axis can not be covered. More...
int	k_xy
	number of components, when scanning the x-axis first. 0 if the axes can no be covered. More...
int	k_yx
	number of components, when scanning the y-axis first. 0 if the axes can no be covered. More...
data::BitSet	result
	subset of selected components More...

Constructor & Destructor Documentation

Greedy()

frechet::k::kAlgorithm::Greedy::Greedy ( )

inline

empty constructor

Definition at line 236 of file kalgorithm.h.

Member Function Documentation

lowerBound()

Result frechet::k::kAlgorithm::Greedy::lowerBound ( ) const

inline

get a lower bound for the optimal result. Observe that k_x,k_y <= k_optimal

Returns

lower bound for the optimal result, negative if there is no result at all.

Definition at line 227 of file kalgorithm.h.

upperBound()

Result frechet::k::kAlgorithm::Greedy::upperBound ( ) const

inline

get an upper bound for the optimal result. Observe that k_optimal <= k_xy,k_yx

Returns

lower bound for the optimal result, negative if there is no result at all.

Definition at line 233 of file kalgorithm.h.

valid()

bool frechet::k::kAlgorithm::Greedy::valid ( ) const

inline

Returns

true if there is a valid result

Definition at line 220 of file kalgorithm.h.

Member Data Documentation

k_x

int frechet::k::kAlgorithm::Greedy::k_x

number of components that is needed to cover the x-axis. 0 if the x-axis can not be covered.

Definition at line 209 of file kalgorithm.h.

k_xy

int frechet::k::kAlgorithm::Greedy::k_xy

number of components, when scanning the x-axis first. 0 if the axes can no be covered.

Definition at line 213 of file kalgorithm.h.

k_y

int frechet::k::kAlgorithm::Greedy::k_y

number of components that is needed to cover the y-axis. 0 if the y-axis can not be covered.

Definition at line 211 of file kalgorithm.h.

k_yx

int frechet::k::kAlgorithm::Greedy::k_yx

number of components, when scanning the y-axis first. 0 if the axes can no be covered.

Definition at line 215 of file kalgorithm.h.

result

data::BitSet frechet::k::kAlgorithm::Greedy::result

subset of selected components

Definition at line 217 of file kalgorithm.h.

---

The documentation for this struct was generated from the following file:

• include/frechet/k_frechet/kalgorithm.h