Randomized multiplicative spanner calculation by forming clusters. More...

#include <ogdf/graphalg/SpannerBaswanaSen.h>

Inheritance diagram for ogdf::SpannerBaswanaSen< 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.

void	phase1 ()
	Phase 1: Forming clusters.

void	phase2 ()
	Phase 2: Vertex-Cluster Joining.

TWeight	weight (edge e)

Private Attributes
NodeArray< node >	m_cluster
	the current cluster for each iteration in phase 1 and the final cluster from phase 1 which is used in phase 2

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

Randomized multiplicative spanner calculation by forming clusters.

S. Baswana und S. Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures & Algorithms 30.4 (2007), S. 532-563. doi: https://doi.org/10.1002/rsa.20130.

Conditions for the graph:

undirected
weighted

The stretch \(s\) must satisfy: \(s\in\{1,3,5,7,\ldots\}\).

The preconditions can be checked with SpannerBaswanaSen::preconditionsOk.

Calculates a \((2k-1)\)-spanner with size \(\mathcal{O}(kn^{1+1/k})\). There are no guarantees for the lightness. The expected runtime is \(\mathcal{O}(km)\).

Definition at line 62 of file SpannerBaswanaSen.h.

Member Function Documentation

◆ addToSpanner()

template<typename TWeight >

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

inlineprivate

Adds e from m_G to the spanner and sets inSpanner.

Definition at line 113 of file SpannerBaswanaSen.h.

◆ execute()

template<typename TWeight >

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

◆ init()

template<typename TWeight >

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