A implementation-independed wrapper class to execute a spanner algorithm multiple times. More...

#include <ogdf/graphalg/SpannerIteratedWrapper.h>

Inheritance diagram for ogdf::SpannerIteratedWrapper< TWeight >:

Public Member Functions
	SpannerIteratedWrapper (SpannerModule< TWeight > *module, int maxIterations)
	Initializes the wrapper.

int	getExecutedIterations ()

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

Public Member Functions inherited from ogdf::SpannerModule< TWeight >
	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 ()

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 ()

Private Member Functions
virtual SpannerModule< TWeight >::ReturnType	execute () override
	Executes the core algorithm.

Private Attributes
int	m_iterations

const int	m_maxIterations

std::unique_ptr< SpannerModule< TWeight > >	m_module

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

Static Public Member Functions inherited from ogdf::SpannerModule< TWeight >
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 inherited from ogdf::SpannerModule< TWeight >
void	assertTimeLeft ()
	Assert, that time is left.

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 inherited from ogdf::SpannerModule< TWeight >
static TWeight	getWeight (const GraphAttributes &GA, edge e)

Protected Attributes inherited from ogdf::SpannerModule< TWeight >
const GraphAttributes *	m_GA

EdgeArray< bool > *	m_inSpanner

GraphCopySimple *	m_spanner

double	m_stretch

Detailed Description

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

A implementation-independed wrapper class to execute a spanner algorithm multiple times.

The amount of maximum iterations can be set. If this is reached or the optional timelimit is exceeded, the best solution so far is returned. The quality of the solution is determined by the sparsity of the spanner, namely the spanner with the least amount of edges regardless of whether the spanner is weighted or not.

If no valid solution was found and the timelimit is exceeded, SpannerModule::ReturnType::TimeoutInfeasible is returned. If all iterations are completed and no valid solution was found, SpannerModule::ReturnType::NoFeasibleSolution is returned. If an error happens, it is directly returned and the iterative execution aborted. If there is at least one valid result, the return type will be SpannerModule::ReturnType::Feasible and the spanner is valid.

Template Parameters

TWeight The type of weights to get from GA

Definition at line 58 of file SpannerIteratedWrapper.h.

Constructor & Destructor Documentation

◆ SpannerIteratedWrapper()

template<typename TWeight >

ogdf::SpannerIteratedWrapper< TWeight >::SpannerIteratedWrapper	(	SpannerModule< TWeight > *	module,
		int	maxIterations
	)

inline

Initializes the wrapper.

Parameters

module	The algorithm implementation to use. It is internally put into a unique pointer, so this class will take care about the deletion of the algorithm.
maxIterations	The maximum amount of alls to the algorithm.

Definition at line 67 of file SpannerIteratedWrapper.h.