Approximation multiplicative 2-spanner calculation. More...

#include <ogdf/graphalg/SpannerKortsarzPeleg.h>

Inheritance diagram for ogdf::SpannerKortsarzPeleg< TWeight >:

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
void	addToSpanner (edge e)
	Adds `e` from m_G to the spanner and sets inSpanner.

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.

Private Attributes
EpsilonTest	m_eps

GraphCopySimple	m_G
	The copy of GA.constGraph() to work on. Edges will be removed in each iteration.

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

Approximation multiplicative 2-spanner calculation.

G. Kortsarz und D. Peleg. Generating Sparse 2-Spanners. Journal of Algorithms 17.2 (1994), S. 222–236. doi: https://doi.org/10.1006/jagm.1994.1032.

Conditions for the graph:

simple
undirected
unweighted

The stretch \(s\) must satisfy: \(s=2\).

The preconditions can be checked with SpannerKortsarzPeleg::preconditionsOk.

Calculates a 2-spanner with an approximation ratio \(\mathcal{O}(|E|/|V|)\). The runtime is \(\mathcal{O}(m^2n^2\log(n^2/m))\) (given in the paper).

The implemented runtime can be bound by \(\mathcal{O}(nm\cdot MDS(n, m))\) with \(MDS(n, m)\) being the runtime for the maximumDensitySubgraph implementation. The used implementation has a runtime of \(\mathcal{O}(mn^2\log n)\) so this implementation has a runtime of \(\mathcal{O}(m^2n^3\log n)\).

Note that the practical runtime is not as high since the MDS-problem is only called for neighbor-graphs of a vertex. For sparse graphs, these subgraphs typically are not as huge as the input graph. But remember: For complete graphs, the running time will approach the upper bound given in the O-notation.

Definition at line 73 of file SpannerKortsarzPeleg.h.

Member Function Documentation

◆ addToSpanner()

template<typename TWeight >

void ogdf::SpannerKortsarzPeleg< TWeight >::addToSpanner ( edge e )

inlineprivate

Adds e from m_G to the spanner and sets inSpanner.

Definition at line 205 of file SpannerKortsarzPeleg.h.

◆ execute()

template<typename TWeight >

virtual SpannerModule< TWeight >::ReturnType ogdf::SpannerKortsarzPeleg< 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 109 of file SpannerKortsarzPeleg.h.

◆ init()

template<typename TWeight >

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