Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::SpannerElkinNeiman< TWeight > Class Template Reference

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. More...
 
- Public Member Functions inherited from ogdf::SpannerModule< TWeight >
 SpannerModule ()
 Initializes a spanner module. More...
 
virtual ~SpannerModule ()
 
virtual ReturnType call (const GraphAttributes &GA, double stretch, GraphCopySimple &spanner, EdgeArray< bool > &inSpanner)
 Executes the algorithm. More...
 
int64_t getTimeNeeded ()
 
void setTimelimit (int64_t milliseconds)
 Sets the timelimit for the algorithm in milliseconds. More...
 
- Public Member Functions inherited from ogdf::Module
 Module ()
 Initializes a module. More...
 
virtual ~Module ()
 

Private Member Functions

virtual SpannerModule< TWeight >::ReturnType execute () override
 Executes the core algorithm. More...
 
virtual void init (const GraphAttributes &GA, double stretch, GraphCopySimple &spanner, EdgeArray< bool > &inSpanner) override
 Initializes members and create an empty spanner. More...
 

Private Attributes

const double DEFAULT_EPSILON = 0.8
 The default value for epsilon. More...
 
double m_beta
 The parameter for the exponential distribution. More...
 
double m_c
 the parameter for the exponential distribution. More...
 
EpsilonTest m_eps
 
const Graphm_G
 The original graph. More...
 
int m_intStretch
 m_stretch, but as an integer More...
 
int m_k
 the parameter k derived from the stretch More...
 

Additional Inherited Members

- Public Types inherited from ogdf::Module
enum  ReturnType { ReturnType::Feasible, ReturnType::Optimal, ReturnType::NoFeasibleSolution, ReturnType::TimeoutFeasible, ReturnType::TimeoutInfeasible, ReturnType::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. More...
 
static bool isMultiplicativeSpanner (const GraphAttributes &GA, const GraphCopySimple &spanner, double stretch)
 Validates a spanner. More...
 
- 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. More...
 
- Protected Member Functions inherited from ogdf::SpannerModule< TWeight >
void assertTimeLeft ()
 Assert, that time is left. More...
 
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 GraphAttributesm_GA
 
EdgeArray< bool > * m_inSpanner
 
GraphCopySimplem_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.

◆ m_beta

template<typename TWeight >
double ogdf::SpannerElkinNeiman< TWeight >::m_beta
private

The parameter for the exponential distribution.

Definition at line 102 of file SpannerElkinNeiman.h.

◆ m_c

template<typename TWeight >
double ogdf::SpannerElkinNeiman< TWeight >::m_c
private

the parameter for the exponential distribution.

It depends on epsilon

Definition at line 101 of file SpannerElkinNeiman.h.

◆ m_eps

template<typename TWeight >
EpsilonTest ogdf::SpannerElkinNeiman< TWeight >::m_eps
private

Definition at line 99 of file SpannerElkinNeiman.h.

◆ m_G

template<typename TWeight >
const Graph* ogdf::SpannerElkinNeiman< TWeight >::m_G
private

The original graph.

Definition at line 97 of file SpannerElkinNeiman.h.

◆ m_intStretch

template<typename TWeight >
int ogdf::SpannerElkinNeiman< TWeight >::m_intStretch
private

m_stretch, but as an integer

Definition at line 104 of file SpannerElkinNeiman.h.

◆ m_k

template<typename TWeight >
int ogdf::SpannerElkinNeiman< TWeight >::m_k
private

the parameter k derived from the stretch

Definition at line 103 of file SpannerElkinNeiman.h.


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