|
|||
|
|
|
|||
|
|
A implementation-independed wrapper class to execute a spanner algorithm multiple times. More...
#include <ogdf/graphalg/SpannerIteratedWrapper.h>
Inheritance diagram for ogdf::SpannerIteratedWrapper< TWeight >:Public Member Functions | |
| SpannerIteratedWrapper (SpannerModule< TWeight > *module, int maxIterations) | |
| Initializes the wrapper. More... | |
| int | getExecutedIterations () |
| 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 | |
| virtual SpannerModule< TWeight >::ReturnType | execute () override |
| Executes the core algorithm. More... | |
Private Attributes | |
| int | m_iterations |
| const int | m_maxIterations |
| std::unique_ptr< SpannerModule< TWeight > > | m_module |
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) |
| virtual void | init (const GraphAttributes &GA, double stretch, GraphCopySimple &spanner, EdgeArray< bool > &inSpanner) |
| Initializes members and create an empty spanner. More... | |
| 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 |
A implementation-independed wrapper class to execute a spanner algorithm multiple times.
The amount of maximum iterations can be set. If this is reached or the optional timelimit is exceeded, the best solution so far is returned. The quality of the solution is determined by the sparsity of the spanner, namely the spanner with the least amount of edges regardless of whether the spanner is weighted or not.
If no valid solution was found and the timelimit is exceeded, SpannerModule::ReturnType::TimeoutInfeasible is returned. If all iterations are completed and no valid solution was found, SpannerModule::ReturnType::NoFeasibleSolution is returned. If an error happens, it is directly returned and the iterative execution aborted. If there is at least one valid result, the return type will be SpannerModule::ReturnType::Feasible and the spanner is valid.
| TWeight | The type of weights to get from GA |
Definition at line 66 of file SpannerIteratedWrapper.h.
|
inline |
Initializes the wrapper.
| module | The algorithm implementation to use. It is internally put into a unique pointer, so this class will take care about the deletion of the algorithm. |
| maxIterations | The maximum amount of alls to the algorithm. |
Definition at line 75 of file SpannerIteratedWrapper.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 95 of file SpannerIteratedWrapper.h.
|
inline |
Definition at line 87 of file SpannerIteratedWrapper.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 79 of file SpannerIteratedWrapper.h.
|
private |
Definition at line 92 of file SpannerIteratedWrapper.h.
|
private |
Definition at line 91 of file SpannerIteratedWrapper.h.
|
private |
Definition at line 90 of file SpannerIteratedWrapper.h.