|
|||
|
|
|
|||
|
|
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 |
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.