|
|||
|
|
|
|||
|
|
Approximation multiplicative 2-spanner calculation. More...
#include <ogdf/graphalg/SpannerKortsarzPeleg.h>
Inheritance diagram for ogdf::SpannerKortsarzPeleg< 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. | |
Private Attributes | |
| 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 |
Approximation multiplicative 2-spanner calculation.
G. Kortsarz und D. Peleg. Generating Sparse 2-Spanners. Journal of Algorithms 17.2 (1994), S. 222–236. doi: https://doi.org/10.1006/jagm.1994.1032.
Conditions for the graph:
The stretch \(s\) must satisfy: \(s=2\).
The preconditions can be checked with SpannerKortsarzPeleg::preconditionsOk.
Calculates a 2-spanner with an approximation ratio \(\mathcal{O}(|E|/|V|)\). The runtime is \(\mathcal{O}(m^2n^2\log(n^2/m))\) (given in the paper).
The implemented runtime can be bound by \(\mathcal{O}(nm\cdot MDS(n, m))\) with \(MDS(n, m)\) being the runtime for the maximumDensitySubgraph implementation. The used implementation has a runtime of \(\mathcal{O}(mn^2\log n)\) so this implementation has a runtime of \(\mathcal{O}(m^2n^3\log n)\).
Note that the practical runtime is not as high since the MDS-problem is only called for neighbor-graphs of a vertex. For sparse graphs, these subgraphs typically are not as huge as the input graph. But remember: For complete graphs, the running time will approach the upper bound given in the O-notation.
Definition at line 84 of file SpannerKortsarzPeleg.h.
|
inlineprivate |
Adds e from m_G to the spanner and sets inSpanner.
Definition at line 216 of file SpannerKortsarzPeleg.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 120 of file SpannerKortsarzPeleg.h.
|
inlineoverrideprivatevirtual |
Initializes members and create an empty spanner.
Reimplemented from ogdf::SpannerModule< TWeight >.
Definition at line 113 of file SpannerKortsarzPeleg.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 91 of file SpannerKortsarzPeleg.h.
|
private |
Definition at line 87 of file SpannerKortsarzPeleg.h.
|
private |
The copy of GA.constGraph() to work on. Edges will be removed in each iteration.
Definition at line 86 of file SpannerKortsarzPeleg.h.