Randomized multiplicative spanner calculation by propagating random messages through the graph. More...

#include <ogdf/graphalg/SpannerElkinNeiman.h>

Inheritance diagram for ogdf::SpannerElkinNeiman< TWeight >:

Classes
struct	BfsNode

Public Member Functions
	SpannerElkinNeiman ()

	SpannerElkinNeiman (double epsilon)

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

void	setEpsilon (double epsilon)
	Sets the epsilon for this algorithm.

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.

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

Private Attributes
const double	DEFAULT_EPSILON = 0.8
	The default value for epsilon.

double	m_beta
	The parameter for the exponential distribution.

double	m_c
	the parameter for the exponential distribution.

EpsilonTest	m_eps

const Graph *	m_G
	The original graph.

int	m_intStretch
	m_stretch, but as an integer

int	m_k
	the parameter k derived from the stretch

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

Randomized multiplicative spanner calculation by propagating random messages through the graph.

M. Elkin und O. Neiman. Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. ACM Trans. Algorithms 15.1 (Nov. 2018). doi: 10.1145/3274651.

Conditions for the graph:

undirected
unweighted

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

The preconditions can be checked with SpannerElkinNeiman::preconditionsOk.

Calculates a \((2k-1)\)-spanner with size \(\mathcal{O}(n^{1+1/k}/\epsilon)\), \(0<\epsilon<1\). The runtime is \(\mathcal{O}(m)\) with a success probability of at least \(1-\epsilon\).

Note that in practice, \(\epsilon\) can be larger than 1 which can result in even better results, but has a larger probability of failing. Remember, that the success probability is a lower bound, so larger \(\epsilon\) does not imply that it is impossible to generate a solution.

Note: Implementation details:

Since the paper does not state much detail about the algorithm, some things must be explained here that are not trivial:

"Each vertex x that received a message originated at u, stores [...] a neighbor p_u(x) that lies on a shortest path from x to u": This also includes, that the message must be send via a shortest path. In the implementation a breadth first search is used since the graph is unweighted (no need for dijkstra). With marking visited notes it is ensured that when visiting a node the first time, it is a shortest path.
Continuing: "(this neighbor sent x the message from u, breaking ties arbitrarily if there is more than one)". To not make the code more complicated to search for all shortest paths, saving them into a list and in a second step choosing one random element from the list, just the first shortest path is taken (see above). It works and the results do not seem to be much worse.
There are two feasibility checks below with the second one modified. See the comment at the very end of the execute function.
The paper describes the algorithm, that u broadcasts a value to all nodes within distance k. Then, each receiving node x is handled (e.g. building m(x) and C(x) only with respect to x). If it is implemented this way, there has to be a n*n matrix for m_u(x) and p_u(x) which is very memory consuming. Tests with some large instances (n about 40000) resulted in out of memory issues during the initialization of the arrays. To lower the memory footprint to just O(n), the logic is switched around: The algorithm always fixes a receiving node x, which is fine for the later parts. So now all nodes u are searched, that sends a message to x. This can also be done by the same BFS with little modification. In summary, this allows for just storing the value and edge for each node, not a matrix of nodes.

Definition at line 95 of file SpannerElkinNeiman.h.

Constructor & Destructor Documentation

◆ SpannerElkinNeiman() [1/2]

template<typename TWeight >

ogdf::SpannerElkinNeiman< TWeight >::SpannerElkinNeiman ( )

inline

Definition at line 117 of file SpannerElkinNeiman.h.

◆ SpannerElkinNeiman() [2/2]

template<typename TWeight >

ogdf::SpannerElkinNeiman< TWeight >::SpannerElkinNeiman ( double epsilon )

inline

Definition at line 119 of file SpannerElkinNeiman.h.

Member Function Documentation

◆ execute()

template<typename TWeight >

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

◆ init()

template<typename TWeight >

virtual void ogdf::SpannerElkinNeiman< 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 161 of file SpannerElkinNeiman.h.

◆ preconditionsOk()

template<typename TWeight >

virtual bool ogdf::SpannerElkinNeiman< 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 132 of file SpannerElkinNeiman.h.

◆ setEpsilon()

template<typename TWeight >

void ogdf::SpannerElkinNeiman< TWeight >::setEpsilon ( double epsilon )

inline

Sets the epsilon for this algorithm.

Note that it must be >0 and bounded with <1 in the paper. The upper bound can be exceeded, so values like 2 or 3 can also be used.

Definition at line 126 of file SpannerElkinNeiman.h.

Member Data Documentation

◆ DEFAULT_EPSILON

template<typename TWeight >

const double ogdf::SpannerElkinNeiman< TWeight >::DEFAULT_EPSILON = 0.8

private

The default value for epsilon.

This is a result of some experimental tests on arbitrary graphs: This epsilon provides a good compromise of

Around 75% chance of success
low mean value of the resulting spanner sizes
medium statistical dispersion -> The results mainly disperse evenly, so a high dispersion leads to a higher probability of finding better minimum spanners

Definition at line 114 of file SpannerElkinNeiman.h.