Randomized multiplicative spanner calculation by propagating random messages through the graph. More...
#include <ogdf/graphalg/SpannerElkinNeiman.h>
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 Graph * | m_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 GraphAttributes * | m_GA |
EdgeArray< bool > * | m_inSpanner |
GraphCopySimple * | m_spanner |
double | m_stretch |
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:
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.
Since the paper does not state much detail about the algorithm, some things must be explained here that are not trivial:
Definition at line 95 of file SpannerElkinNeiman.h.
|
inline |
Definition at line 117 of file SpannerElkinNeiman.h.
|
inline |
Definition at line 119 of file SpannerElkinNeiman.h.
|
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.
|
inlineoverrideprivatevirtual |
Initializes members and create an empty spanner.
Reimplemented from ogdf::SpannerModule< TWeight >.
Definition at line 161 of file SpannerElkinNeiman.h.
|
inlineoverridevirtual |
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.
|
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.
|
private |
The default value for epsilon.
This is a result of some experimental tests on arbitrary graphs: This epsilon provides a good compromise of
Definition at line 114 of file SpannerElkinNeiman.h.
|
private |
The parameter for the exponential distribution.
Definition at line 102 of file SpannerElkinNeiman.h.
|
private |
the parameter for the exponential distribution.
It depends on epsilon
Definition at line 101 of file SpannerElkinNeiman.h.
|
private |
Definition at line 99 of file SpannerElkinNeiman.h.
|
private |
The original graph.
Definition at line 97 of file SpannerElkinNeiman.h.
|
private |
m_stretch, but as an integer
Definition at line 104 of file SpannerElkinNeiman.h.
|
private |
the parameter k derived from the stretch
Definition at line 103 of file SpannerElkinNeiman.h.