Randomized multiplicative spanner calculation by forming clusters. More...
#include <ogdf/graphalg/SpannerBaswanaSen.h>
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. 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 | |
void | addToSpanner (edge e) |
Adds e from m_G to the spanner and sets inSpanner. More... | |
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... | |
void | phase1 () |
Phase 1: Forming clusters. More... | |
void | phase2 () |
Phase 2: Vertex-Cluster Joining. More... | |
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 More... | |
EpsilonTest | m_eps |
GraphCopySimple | m_G |
The copy of GA.constGraph() to work on. Edges will be removed in each iteration. 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 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:
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 74 of file SpannerBaswanaSen.h.
|
inlineprivate |
Adds e
from m_G to the spanner and sets inSpanner.
Definition at line 125 of file SpannerBaswanaSen.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 116 of file SpannerBaswanaSen.h.
|
inlineoverrideprivatevirtual |
Initializes members and create an empty spanner.
Reimplemented from ogdf::SpannerModule< TWeight >.
Definition at line 108 of file SpannerBaswanaSen.h.
|
inlineprivate |
Phase 1: Forming clusters.
Definition at line 138 of file SpannerBaswanaSen.h.
|
inlineprivate |
Phase 2: Vertex-Cluster Joining.
Definition at line 273 of file SpannerBaswanaSen.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 84 of file SpannerBaswanaSen.h.
|
inlineprivate |
e
from m_G Definition at line 133 of file SpannerBaswanaSen.h.
|
private |
the current cluster for each iteration in phase 1 and the final cluster from phase 1 which is used in phase 2
Definition at line 78 of file SpannerBaswanaSen.h.
|
private |
Definition at line 80 of file SpannerBaswanaSen.h.
|
private |
The copy of GA.constGraph() to work on. Edges will be removed in each iteration.
Definition at line 76 of file SpannerBaswanaSen.h.