|
|||
|
|
|
|||
|
|
Multiplicative spanner by greedily adding edges. More...
#include <ogdf/graphalg/SpannerBasicGreedy.h>
Inheritance diagram for ogdf::SpannerBasicGreedy< TWeight >:Classes | |
| struct | EdgeWeightComparator |
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 | |
| double | distanceInSpanner (node s, node t, double maxLookupDist) |
| 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... | |
| TWeight | weight (edge e) |
Private Attributes | |
| EpsilonTest | m_eps |
| EdgeArray< TWeight > | m_spannerWeights |
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 |
Multiplicative spanner by greedily adding edges.
I. Althöfer, G. Das, D. Dobkin und D. Joseph. On Sparse Spanners of Weighted Graphs. Discrete Comput Geom 9 (1993), S. 81–100. doi: https://doi.org/10.1007/BF02189308.
Conditions for the graph:
The stretch \(s\) must satisfy: \(s\geq1\in\mathbb{R}\).
The preconditions can be checked with SpannerBasicGreedy::preconditionsOk.
Calculates a \((2k-1)\)-spanner with size \(<n^{(1+1/k)}\) ( \(\mathcal{O}(n^{1+1/k})\)) and lightness \(<1+n/k\) ( \(\mathcal{O}(n/k)\)). The runtime is \(\mathcal{O}(mn^{1+1/k}\log n)\)
Definition at line 67 of file SpannerBasicGreedy.h.
|
private |
|
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 93 of file SpannerBasicGreedy.h.
|
inlineoverrideprivatevirtual |
Initializes members and create an empty spanner.
Reimplemented from ogdf::SpannerModule< TWeight >.
Definition at line 87 of file SpannerBasicGreedy.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 73 of file SpannerBasicGreedy.h.
|
inlineprivate |
e from m_G Definition at line 124 of file SpannerBasicGreedy.h.
|
private |
Definition at line 69 of file SpannerBasicGreedy.h.
|
private |
Definition at line 68 of file SpannerBasicGreedy.h.