Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::SpannerModule< TWeight > Class Template Referenceabstract

Interface for spanner algorithms. More...

#include <ogdf/graphalg/SpannerModule.h>

+ Inheritance diagram for ogdf::SpannerModule< TWeight >:

Classes

struct  TimeoutException
 

Public Member Functions

 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 ()
 
virtual bool preconditionsOk (const GraphAttributes &GA, double stretch, std::string &error)=0
 
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 ()
 

Static Public Member Functions

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

void assertTimeLeft ()
 Assert, that time is left. More...
 
virtual ReturnType execute ()=0
 Executes the core algorithm. 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

static TWeight getWeight (const GraphAttributes &GA, edge e)
 

Protected Attributes

const GraphAttributesm_GA
 
EdgeArray< bool > * m_inSpanner
 
GraphCopySimplem_spanner
 
double m_stretch
 

Private Attributes

int64_t m_timelimit = -1
 Timelimit in milliseconds. More...
 
StopwatchCPU m_watch
 Used for keeping track of time. More...
 

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

Detailed Description

template<typename TWeight>
class ogdf::SpannerModule< TWeight >

Interface for spanner algorithms.

All spanner implementations must:

Definition at line 57 of file SpannerModule.h.

Constructor & Destructor Documentation

◆ SpannerModule()

template<typename TWeight >
ogdf::SpannerModule< TWeight >::SpannerModule ( )
inline

Initializes a spanner module.

Definition at line 60 of file SpannerModule.h.

◆ ~SpannerModule()

template<typename TWeight >
virtual ogdf::SpannerModule< TWeight >::~SpannerModule ( )
inlinevirtual

Definition at line 63 of file SpannerModule.h.

Member Function Documentation

◆ apspSpanner()

template<typename TWeight >
void ogdf::SpannerModule< TWeight >::apspSpanner ( const GraphAttributes GA,
const GraphCopySimple spanner,
NodeArray< NodeArray< TWeight >> &  shortestPathMatrix 
)
static

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 >
void ogdf::SpannerModule< TWeight >::assertTimeLeft ( )
inlineprotected

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 >
virtual ReturnType ogdf::SpannerModule< TWeight >::call ( const GraphAttributes GA,
double  stretch,
GraphCopySimple spanner,
EdgeArray< bool > &  inSpanner 
)
inlinevirtual

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
TWeightthe type of weights to get from GA
Parameters
GAThe graph used. GraphAttributes can be used to pass in weights
stretchThe multiplicative shortest-path-length factor
spannerThe resulting spanner. Must be a copy of GA.constGraph()
inSpannerMaps 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 >
virtual ReturnType ogdf::SpannerModule< TWeight >::execute ( )
protectedpure virtual

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.

Implemented in ogdf::SpannerBerman< TWeight >, ogdf::SpannerElkinNeiman< TWeight >, ogdf::SpannerKortsarzPeleg< TWeight >, ogdf::SpannerBaswanaSen< TWeight >, ogdf::SpannerIteratedWrapper< TWeight >, ogdf::SpannerBasicGreedy< TWeight >, and ogdf::SpannerBermanDisconnected< TWeight >.

◆ getTimeLeft()

template<typename TWeight >
int64_t ogdf::SpannerModule< TWeight >::getTimeLeft ( )
inlineprotected
Returns
the amount of time in milliseconds left for execution.

Definition at line 166 of file SpannerModule.h.

◆ getTimeNeeded()

template<typename TWeight >
int64_t ogdf::SpannerModule< TWeight >::getTimeNeeded ( )
inline
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 >
static TWeight ogdf::SpannerModule< TWeight >::getWeight ( const GraphAttributes GA,
edge  e 
)
staticprotected
Returns
the weight of an edge e from GA

◆ getWeight() [2/3]

int ogdf::SpannerModule< int >::getWeight ( const GraphAttributes GA,
edge  e 
)
inlineprotected

Definition at line 253 of file SpannerModule.h.

◆ getWeight() [3/3]

double ogdf::SpannerModule< double >::getWeight ( const GraphAttributes GA,
edge  e 
)
inlineprotected

Definition at line 262 of file SpannerModule.h.

◆ init()

template<typename TWeight >
virtual void ogdf::SpannerModule< TWeight >::init ( const GraphAttributes GA,
double  stretch,
GraphCopySimple spanner,
EdgeArray< bool > &  inSpanner 
)
inlineprotectedvirtual

◆ isMultiplicativeSpanner()

template<typename TWeight >
bool ogdf::SpannerModule< TWeight >::isMultiplicativeSpanner ( const GraphAttributes GA,
const GraphCopySimple spanner,
double  stretch 
)
static

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 >
bool ogdf::SpannerModule< TWeight >::isTimelimitEnabled ( )
inlineprotected
Returns
true, if there should be a timelimit.

Definition at line 161 of file SpannerModule.h.

◆ preconditionsOk()

template<typename TWeight >
virtual bool ogdf::SpannerModule< TWeight >::preconditionsOk ( const GraphAttributes GA,
double  stretch,
std::string &  error 
)
pure virtual

◆ setTimelimit()

template<typename TWeight >
void ogdf::SpannerModule< TWeight >::setTimelimit ( int64_t  milliseconds)
inline

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.

Member Data Documentation

◆ m_GA

template<typename TWeight >
const GraphAttributes* ogdf::SpannerModule< TWeight >::m_GA
protected

Definition at line 128 of file SpannerModule.h.

◆ m_inSpanner

template<typename TWeight >
EdgeArray<bool>* ogdf::SpannerModule< TWeight >::m_inSpanner
protected

Definition at line 131 of file SpannerModule.h.

◆ m_spanner

template<typename TWeight >
GraphCopySimple* ogdf::SpannerModule< TWeight >::m_spanner
protected

Definition at line 130 of file SpannerModule.h.

◆ m_stretch

template<typename TWeight >
double ogdf::SpannerModule< TWeight >::m_stretch
protected

Definition at line 129 of file SpannerModule.h.

◆ m_timelimit

template<typename TWeight >
int64_t ogdf::SpannerModule< TWeight >::m_timelimit = -1
private

Timelimit in milliseconds.

-1 disables the timeout.

Definition at line 179 of file SpannerModule.h.

◆ m_watch

template<typename TWeight >
StopwatchCPU ogdf::SpannerModule< TWeight >::m_watch
private

Used for keeping track of time.

Definition at line 180 of file SpannerModule.h.


The documentation for this class was generated from the following file: