ogdf::SpannerBasicGreedy< TWeight > Class Template Reference

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 67 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 93 of file SpannerBasicGreedy.h.

init()

template<typename TWeight >

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

inlineoverrideprivatevirtual

Initializes members and create an empty spanner.

Reimplemented from ogdf::SpannerModule< TWeight >.

Definition at line 87 of file SpannerBasicGreedy.h.

preconditionsOk()

template<typename TWeight >

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

inlineoverridevirtual

Returns

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

Implements ogdf::SpannerModule< TWeight >.

Definition at line 73 of file SpannerBasicGreedy.h.

weight()

template<typename TWeight >

TWeight ogdf::SpannerBasicGreedy< TWeight >::weight ( edge  e )

inlineprivate

Returns

the weights of an edge e from m_G

Definition at line 124 of file SpannerBasicGreedy.h.

Member Data Documentation

m_eps

template<typename TWeight >

EpsilonTest ogdf::SpannerBasicGreedy< TWeight >::m_eps

private

Definition at line 69 of file SpannerBasicGreedy.h.

m_spannerWeights

template<typename TWeight >

EdgeArray<TWeight> ogdf::SpannerBasicGreedy< TWeight >::m_spannerWeights

private

Definition at line 68 of file SpannerBasicGreedy.h.

---

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

• include/ogdf/graphalg/SpannerBasicGreedy.h