Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::SpannerBaswanaSen< TWeight > Class Template Reference

Randomized multiplicative spanner calculation by forming clusters. More...

#include <ogdf/graphalg/SpannerBaswanaSen.h>

+ Inheritance diagram for ogdf::SpannerBaswanaSen< 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. 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

void addToSpanner (edge e)
 Adds e from m_G to the spanner and sets inSpanner. More...
 
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...
 
void phase1 ()
 Phase 1: Forming clusters. More...
 
void phase2 ()
 Phase 2: Vertex-Cluster Joining. More...
 
TWeight weight (edge e)
 

Private Attributes

NodeArray< nodem_cluster
 the current cluster for each iteration in phase 1 and the final cluster from phase 1 which is used in phase 2 More...
 
EpsilonTest m_eps
 
GraphCopySimple m_G
 The copy of GA.constGraph() to work on. Edges will be removed in each iteration. 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...
 
- 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 GraphAttributesm_GA
 
EdgeArray< bool > * m_inSpanner
 
GraphCopySimplem_spanner
 
double m_stretch
 

Detailed Description

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

Randomized multiplicative spanner calculation by forming clusters.

S. Baswana und S. Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures & Algorithms 30.4 (2007), S. 532-563. doi: https://doi.org/10.1002/rsa.20130.

Conditions for the graph:

  • undirected
  • weighted

The stretch \(s\) must satisfy: \(s\in\{1,3,5,7,\ldots\}\).

The preconditions can be checked with SpannerBaswanaSen::preconditionsOk.

Calculates a \((2k-1)\)-spanner with size \(\mathcal{O}(kn^{1+1/k})\). There are no guarantees for the lightness. The expected runtime is \(\mathcal{O}(km)\).

Definition at line 74 of file SpannerBaswanaSen.h.

Member Function Documentation

◆ addToSpanner()

template<typename TWeight >
void ogdf::SpannerBaswanaSen< TWeight >::addToSpanner ( edge  e)
inlineprivate

Adds e from m_G to the spanner and sets inSpanner.

Definition at line 125 of file SpannerBaswanaSen.h.

◆ execute()

template<typename TWeight >
virtual SpannerModule<TWeight>::ReturnType ogdf::SpannerBaswanaSen< TWeight >::execute ( )
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 116 of file SpannerBaswanaSen.h.

◆ init()

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

Initializes members and create an empty spanner.

Reimplemented from ogdf::SpannerModule< TWeight >.

Definition at line 108 of file SpannerBaswanaSen.h.

◆ phase1()

template<typename TWeight >
void ogdf::SpannerBaswanaSen< TWeight >::phase1 ( )
inlineprivate

Phase 1: Forming clusters.

Definition at line 138 of file SpannerBaswanaSen.h.

◆ phase2()

template<typename TWeight >
void ogdf::SpannerBaswanaSen< TWeight >::phase2 ( )
inlineprivate

Phase 2: Vertex-Cluster Joining.

Definition at line 273 of file SpannerBaswanaSen.h.

◆ preconditionsOk()

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

Returns
true, if the given 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 84 of file SpannerBaswanaSen.h.

◆ weight()

template<typename TWeight >
TWeight ogdf::SpannerBaswanaSen< TWeight >::weight ( edge  e)
inlineprivate
Returns
the weights of an edge e from m_G

Definition at line 133 of file SpannerBaswanaSen.h.

Member Data Documentation

◆ m_cluster

template<typename TWeight >
NodeArray<node> ogdf::SpannerBaswanaSen< TWeight >::m_cluster
private

the current cluster for each iteration in phase 1 and the final cluster from phase 1 which is used in phase 2

Definition at line 78 of file SpannerBaswanaSen.h.

◆ m_eps

template<typename TWeight >
EpsilonTest ogdf::SpannerBaswanaSen< TWeight >::m_eps
private

Definition at line 80 of file SpannerBaswanaSen.h.

◆ m_G

template<typename TWeight >
GraphCopySimple ogdf::SpannerBaswanaSen< TWeight >::m_G
private

The copy of GA.constGraph() to work on. Edges will be removed in each iteration.

Definition at line 76 of file SpannerBaswanaSen.h.


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