Multiplicative spanner by greedily adding edges. More...

#include <ogdf/graphalg/SpannerBasicGreedy.h>

Inheritance diagram for ogdf::SpannerBasicGreedy< TWeight >:

Classes
struct	EdgeWeightComparator

Public Member Functions
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
double	distanceInSpanner (node s, node t, double maxLookupDist)

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

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

TWeight	weight (edge e)

Private Attributes
EpsilonTest	m_eps

EdgeArray< TWeight >	m_spannerWeights

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)

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::SpannerBasicGreedy< TWeight >

Multiplicative spanner by greedily adding edges.

I. Althöfer, G. Das, D. Dobkin und D. Joseph. On Sparse Spanners of Weighted Graphs. Discrete Comput Geom 9 (1993), S. 81–100. doi: https://doi.org/10.1007/BF02189308.

Conditions for the graph:

undirected
weighted

The stretch \(s\) must satisfy: \(s\geq1\in\mathbb{R}\).

The preconditions can be checked with SpannerBasicGreedy::preconditionsOk.

Calculates a \((2k-1)\)-spanner with size \(<n^{(1+1/k)}\) ( \(\mathcal{O}(n^{1+1/k})\)) and lightness \(<1+n/k\) ( \(\mathcal{O}(n/k)\)). The runtime is \(\mathcal{O}(mn^{1+1/k}\log n)\)

Definition at line 60 of file SpannerBasicGreedy.h.

Member Function Documentation

◆ distanceInSpanner()

template<typename TWeight >

double ogdf::SpannerBasicGreedy< TWeight >::distanceInSpanner	(	node	s,
		node	t,
		double	maxLookupDist
	)

private

◆ execute()

template<typename TWeight >

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

inlineoverrideprivatevirtual

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.

Implements ogdf::SpannerModule< TWeight >.

Definition at line 86 of file SpannerBasicGreedy.h.

◆ init()

template<typename TWeight >

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