Interface for spanner algorithms. More...

#include <ogdf/graphalg/SpannerModule.h>

Inheritance diagram for ogdf::SpannerModule< TWeight >:

Classes
struct	TimeoutException
	A simple exception used to exit from the execution, if the timelimit is reached. More...

Public Member Functions
	SpannerModule ()
	Initializes a spanner module.

virtual	~SpannerModule ()

virtual ReturnType	call (const GraphAttributes &GA, double stretch, GraphCopySimple &spanner, EdgeArray< bool > &inSpanner)
	Executes the algorithm.

int64_t	getTimeNeeded ()

virtual bool	preconditionsOk (const GraphAttributes &GA, double stretch, std::string &error)=0

void	setTimelimit (int64_t milliseconds)
	Sets the timelimit for the algorithm in milliseconds.

Public Member Functions inherited from ogdf::Module
	Module ()
	Initializes a module.

virtual	~Module ()

Static Public Member Functions
static void	apspSpanner (const GraphAttributes &GA, const GraphCopySimple &spanner, NodeArray< NodeArray< TWeight > > &shortestPathMatrix)
	Calculates an all-pair shortest-path on `spanner` with the weights given by `GA`.

static bool	isMultiplicativeSpanner (const GraphAttributes &GA, const GraphCopySimple &spanner, double stretch)
	Validates a spanner.

Static Public Member Functions inherited from ogdf::Module
static bool	isSolution (ReturnType ret)
	Returns true iff `ret` indicates that the module returned a feasible solution.

Protected Member Functions
void	assertTimeLeft ()
	Assert, that time is left.

virtual ReturnType	execute ()=0
	Executes the core algorithm.

int64_t	getTimeLeft ()

int	getWeight (const GraphAttributes &GA, edge e)

double	getWeight (const GraphAttributes &GA, edge e)

virtual void	init (const GraphAttributes &GA, double stretch, GraphCopySimple &spanner, EdgeArray< bool > &inSpanner)
	Initializes members and create an empty spanner.

bool	isTimelimitEnabled ()

Static Protected Member Functions
static TWeight	getWeight (const GraphAttributes &GA, edge e)

Protected Attributes
const GraphAttributes *	m_GA

EdgeArray< bool > *	m_inSpanner

GraphCopySimple *	m_spanner

double	m_stretch

Private Attributes
int64_t	m_timelimit = -1
	Timelimit in milliseconds.

StopwatchCPU	m_watch
	Used for keeping track of time.

Additional Inherited Members
Public Types inherited from ogdf::Module
enum class	ReturnType { Feasible , Optimal , NoFeasibleSolution , TimeoutFeasible , TimeoutInfeasible , Error }
	The return type of a module. More...

Detailed Description

template<typename TWeight>
class ogdf::SpannerModule< TWeight >

Interface for spanner algorithms.

All spanner implementations must:

implement SpannerModule::execute and SpannerModule::preconditionsOk
be timelimited: Call SpannerModule::assertTimeLeft e.g. in the main loop
create a spanner (m_spanner) and a set of used edges regarding the original graph (m_inSpanner)

Definition at line 57 of file SpannerModule.h.

Constructor & Destructor Documentation

◆ SpannerModule()

template<typename TWeight >

ogdf::SpannerModule< TWeight >::SpannerModule ( )

inline

Initializes a spanner module.

Definition at line 60 of file SpannerModule.h.

◆ ~SpannerModule()

template<typename TWeight >

virtual ogdf::SpannerModule< TWeight >::~SpannerModule ( )

inlinevirtual

Definition at line 63 of file SpannerModule.h.

Member Function Documentation

◆ apspSpanner()

template<typename TWeight >

void ogdf::SpannerModule< TWeight >::apspSpanner	(	const GraphAttributes &	GA,
		const GraphCopySimple &	spanner,
		NodeArray< NodeArray< TWeight > > &	shortestPathMatrix
	)

static

Calculates an all-pair shortest-path on spanner with the weights given by GA.

Definition at line 209 of file SpannerModule.h.

◆ assertTimeLeft()

template<typename TWeight >

void ogdf::SpannerModule< TWeight >::assertTimeLeft ( )

inlineprotected

Assert, that time is left.

If there is no time left (and the timelimit is active), an exception will be thwron to abort the execution.

Definition at line 172 of file SpannerModule.h.

◆ call()

template<typename TWeight >

virtual ReturnType ogdf::SpannerModule< TWeight >::call	(	const GraphAttributes &	GA,
		double	stretch,
		GraphCopySimple &	spanner,
		EdgeArray< bool > &	inSpanner
	)

inlinevirtual

Executes the algorithm.

Example:

GraphAttributes GA = ....
int stretch = 2;
GraphCopySimple spanner;
EdgeArray<bool> inSpanner;
std::unique_ptr<SpannerModule<int>> sm = std::make_unique<BaswanaSenClusterSpanner<int>>();
typename SpannerModule<int>::Result result = sm->call(GA, stretch, spanner, inSpanner);

Template Parameters

TWeight the type of weights to get from GA

Parameters

GA	The graph used. GraphAttributes can be used to pass in weights
stretch	The multiplicative shortest-path-length factor
spanner	The resulting spanner. Must be a copy of GA.constGraph()
inSpanner	Maps true to an edge iff the edge is in the spanner

Returns: The state in which the algorithm returns. Only for OK the spanner is valid.

Definition at line 86 of file SpannerModule.h.

◆ execute()

template<typename TWeight >

virtual ReturnType ogdf::SpannerModule< TWeight >::execute ( )

protectedpure virtual

Executes the core algorithm.

Called after initialization. This method is used for the timelimit, so do not forget to call assertTimeLeft from time to time.

Implemented in ogdf::SpannerBasicGreedy< TWeight >, ogdf::SpannerBaswanaSen< TWeight >, ogdf::SpannerBerman< TWeight >, ogdf::SpannerBermanDisconnected< TWeight >, ogdf::SpannerElkinNeiman< TWeight >, ogdf::SpannerIteratedWrapper< TWeight >, and ogdf::SpannerKortsarzPeleg< TWeight >.

◆ getTimeLeft()

template<typename TWeight >

int64_t ogdf::SpannerModule< TWeight >::getTimeLeft ( )

inlineprotected

Returns: the amount of time in milliseconds left for execution.

Definition at line 166 of file SpannerModule.h.

◆ getTimeNeeded()

template<typename TWeight >

int64_t ogdf::SpannerModule< TWeight >::getTimeNeeded ( )

inline

Returns: the time in milliseconds needed for executing the algorithm (see the execute method).

Definition at line 125 of file SpannerModule.h.

◆ getWeight() [1/3]

template<typename TWeight >

static TWeight ogdf::SpannerModule< TWeight >::getWeight	(	const GraphAttributes &	GA,
		edge	e
	)

staticprotected

Returns: the weight of an edge e from GA

◆ getWeight() [2/3]

int ogdf::SpannerModule< int >::getWeight	(	const GraphAttributes &	GA,
		edge	e
	)

inlineprotected

Definition at line 253 of file SpannerModule.h.

◆ getWeight() [3/3]

double ogdf::SpannerModule< double >::getWeight	(	const GraphAttributes &	GA,
		edge	e
	)

inlineprotected

Definition at line 262 of file SpannerModule.h.

◆ init()

template<typename TWeight >

virtual void ogdf::SpannerModule< TWeight >::init	(	const GraphAttributes &	GA,
		double	stretch,
		GraphCopySimple &	spanner,
		EdgeArray< bool > &	inSpanner
	)

inlineprotectedvirtual

Initializes members and create an empty spanner.

Reimplemented in ogdf::SpannerBasicGreedy< TWeight >, ogdf::SpannerBaswanaSen< TWeight >, ogdf::SpannerBerman< TWeight >, ogdf::SpannerElkinNeiman< TWeight >, and ogdf::SpannerKortsarzPeleg< TWeight >.

Definition at line 136 of file SpannerModule.h.

◆ isMultiplicativeSpanner()

template<typename TWeight >

bool ogdf::SpannerModule< TWeight >::isMultiplicativeSpanner	(	const GraphAttributes &	GA,
		const GraphCopySimple &	spanner,
		double	stretch
	)

static

Validates a spanner.

Returns: true iff the spanner is a k-multiplicative spanner of GA

Definition at line 219 of file SpannerModule.h.

◆ isTimelimitEnabled()

template<typename TWeight >

bool ogdf::SpannerModule< TWeight >::isTimelimitEnabled ( )

inlineprotected

Returns: true, if there should be a timelimit.

Definition at line 161 of file SpannerModule.h.

◆ preconditionsOk()

template<typename TWeight >

virtual bool ogdf::SpannerModule< TWeight >::preconditionsOk	(	const GraphAttributes &	GA,
		double	stretch,
		std::string &	error
	)

pure virtual

Returns: true, if the given GA and stretch are valid for a specific algorithm. If not, an error message is provided via error

Implemented in ogdf::SpannerBasicGreedy< TWeight >, ogdf::SpannerBaswanaSen< TWeight >, ogdf::SpannerBerman< TWeight >, ogdf::SpannerBermanDisconnected< TWeight >, ogdf::SpannerElkinNeiman< TWeight >, ogdf::SpannerIteratedWrapper< TWeight >, and ogdf::SpannerKortsarzPeleg< TWeight >.

◆ setTimelimit()

template<typename TWeight >

void ogdf::SpannerModule< TWeight >::setTimelimit ( int64_t milliseconds )

inline

Sets the timelimit for the algorithm in milliseconds.

Use -1 to disable the timelimit. On timelimit, the algorithm will be aborted. Note that 0 is a valid timelimit. Do not change this during the execution of the algorithm.

Definition at line 120 of file SpannerModule.h.