Interface for spanner algorithms.
More...
#include <ogdf/graphalg/SpannerModule.h>
template<typename TWeight>
class ogdf::SpannerModule< TWeight >
Interface for spanner algorithms.
All spanner implementations must:
Definition at line 57 of file SpannerModule.h.
◆ SpannerModule()
template<typename TWeight >
◆ ~SpannerModule()
template<typename TWeight >
◆ apspSpanner()
template<typename TWeight >
Calculates an all-pair shortest-path on spanner
with the weights given by GA
.
Definition at line 209 of file SpannerModule.h.
◆ assertTimeLeft()
template<typename TWeight >
Assert, that time is left.
If there is no time left (and the timelimit is active), an exception will be thwron to abort the execution.
Definition at line 172 of file SpannerModule.h.
◆ call()
template<typename TWeight >
Executes the algorithm.
Example:
GraphAttributes GA = ....
int stretch = 2;
GraphCopySimple spanner;
EdgeArray<bool> inSpanner;
std::unique_ptr<SpannerModule<int>> sm = std::make_unique<BaswanaSenClusterSpanner<int>>();
typename SpannerModule<int>::Result result = sm->call(GA, stretch, spanner, inSpanner);
- Template Parameters
-
TWeight | the type of weights to get from GA |
- Parameters
-
GA | The graph used. GraphAttributes can be used to pass in weights |
stretch | The multiplicative shortest-path-length factor |
spanner | The resulting spanner. Must be a copy of GA.constGraph() |
inSpanner | Maps true to an edge iff the edge is in the spanner |
- Returns
- The state in which the algorithm returns. Only for OK the spanner is valid.
Definition at line 86 of file SpannerModule.h.
◆ execute()
template<typename TWeight >
◆ getTimeLeft()
template<typename TWeight >
- Returns
- the amount of time in milliseconds left for execution.
Definition at line 166 of file SpannerModule.h.
◆ getTimeNeeded()
template<typename TWeight >
- Returns
- the time in milliseconds needed for executing the algorithm (see the execute method).
Definition at line 125 of file SpannerModule.h.
◆ getWeight() [1/3]
template<typename TWeight >
- Returns
- the weight of an edge
e
from GA
◆ getWeight() [2/3]
◆ getWeight() [3/3]
◆ init()
template<typename TWeight >
◆ isMultiplicativeSpanner()
template<typename TWeight >
Validates a spanner.
- Returns
- true iff the
spanner
is a k-multiplicative spanner of GA
Definition at line 219 of file SpannerModule.h.
◆ isTimelimitEnabled()
template<typename TWeight >
- Returns
- true, if there should be a timelimit.
Definition at line 161 of file SpannerModule.h.
◆ preconditionsOk()
template<typename TWeight >
◆ setTimelimit()
template<typename TWeight >
Sets the timelimit for the algorithm in milliseconds.
Use -1 to disable the timelimit. On timelimit, the algorithm will be aborted. Note that 0 is a valid timelimit. Do not change this during the execution of the algorithm.
Definition at line 120 of file SpannerModule.h.
◆ m_GA
template<typename TWeight >
◆ m_inSpanner
template<typename TWeight >
◆ m_spanner
template<typename TWeight >
◆ m_stretch
template<typename TWeight >
◆ m_timelimit
template<typename TWeight >
Timelimit in milliseconds.
-1 disables the timeout.
Definition at line 179 of file SpannerModule.h.
◆ m_watch
template<typename TWeight >
The documentation for this class was generated from the following file: