Approximation algorithm for calculating spanners. More...

#include <ogdf/graphalg/SpannerBerman.h>

Inheritance diagram for ogdf::SpannerBerman< TWeight >:

Public Member Functions
	SpannerBerman ()

virtual	~SpannerBerman ()

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 ()

Static Public Attributes
static Logger	logger

Private Types
enum class	SeparationResult { NewConstraint , Fail , Solution }
	Used to indicate the result of the separation method. More...

Private Member Functions
bool	_isThickEdge (edge e)
	Actually calculates whether `e` is thick or not.

void	addEdgeToSpanner (edge e)
	Add an edge to the spanner.

void	addUnsettledThickEdges ()

void	calculateThickEdges ()

void	createAntispanner (const edge unsettledThinEdge, const EdgeArray< bool > &out, EdgeArray< bool > &antispanner)

TWeight	distance (const GraphCopySimple &G, const EdgeArray< TWeight > &weights, const node s, const node t, int maxLookupDist)

virtual SpannerModule< TWeight >::ReturnType	execute () override
	Executes the core algorithm.

void	firstPart ()
	First part of the algorithm: Settle all thick edges.

void	inArborescence (const GraphAttributes &GA, node root, NodeArray< edge > &predecessor, NodeArray< TWeight > &distance)
	Calculates an in-arborescense rooted at `root`.

virtual void	init (const GraphAttributes &GA, double stretch, GraphCopySimple &spanner, EdgeArray< bool > &inSpanner) override
	Initializes members and create an empty spanner.

bool	isSettledEdge (const edge e)
	Shortcut for calling isSettledEdge with m_spanner and the current spanner weights.

bool	isSettledEdge (const edge e, const GraphCopySimple &_spanner, const EdgeArray< TWeight > &_spannerWeight)

bool	isThickEdge (edge e)

bool	isThinEdge (edge e)

void	outArborescence (const GraphAttributes &GA, node root, NodeArray< edge > &predecessor, NodeArray< TWeight > &distance)
	Calculates an out-arborescense rooted at `root`.

void	printStats (bool assert=false)

void	randomizedSelection (const double *fractions, EdgeArray< bool > &out)

void	resetLP ()
	Resets the LP defining variables.

bool	secondPart ()
	The second part: Settling all thin edges.

SeparationResult	separation (const double *solution, const EdgeArray< int > &indices)

bool	setOpt (int opt)
	Set a new value for m_OPT.

Private Attributes
double	m_beta
	sqrt(n)

std::vector< CoinPackedVector * >	m_constraints
	Holds all constraints so they can be freed at destruction.

EdgeArray< bool >	m_E1
	Holds the set E1 from the first part of the algorithm.

EdgeArray< bool >	m_E2
	Holds the set E2 from the second part of the algorithm.

EpsilonTest	m_eps

const Graph *	m_G
	const reference to the original graph

NodeArray< NodeArray< TWeight > >	m_inDistance
	m_inDistance[v][w]: distance from v in a v-rooted in-arborescense to w

EdgeArray< bool >	m_isThickEdge

int	m_nSquared
	n^2

int	m_OPT
	The current guess for our optimal LP value.

OsiSolverInterface *	m_osi
	the solver.

NodeArray< NodeArray< TWeight > >	m_outDistance
	m_outDistance[v][w]: distance from v in a v-rooted out-arborescense to w

EdgeArray< TWeight >	m_spannerWeight
	weights for m_spanner Caches, if an edge is thick (or thin).

double	m_sqrtlog
	sqrt(n) * ln(n)

int	m_thickEdgeNodeAmountLimit
	n/beta

EdgeArray< TWeight >	m_weight
	weights of each edge from m_G

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

Detailed Description

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

Approximation algorithm for calculating spanners.

P. Berman, A. Bhattacharyya, K. Makarychev, S. Raskhodnikova und G. Yaroslavtsev. Approximation algorithms for spanner problems and Directed Steiner Forest. Information and Computation 222 (2013). 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), S. 93–107. doi: https://doi.org/10.1016/j.ic. 2012.10.007.

Conditions for the graph:

simple
weakly connected: The graph must be connected, if acrs are seen as edges. To calculate a spanner on disconnected graphs use SpannerBermanDisconnected.

The stretch \(s\) must satisfy: \(s\geq1\in\mathbb{R}\).

The preconditions can be checked with SpannerBerman::preconditionsOk.

Calculates a k-spanner with an approximation ratio of \(\mathcal{O}(n^{1/2}\log n)\) for the size. The graph can be directed and weighted. Undirected and/or unweighted graphs still preserve the approximation ratio.

To enable logging you have to set the log level of the algorithm's logger to Logger::Level::Default or below:

SpannerBerman<int>::logger.localLogLevel(Logger::Level::Default);
// or
SpannerBerman<double>::logger.localLogLevel(Logger::Level::Default);

Definition at line 76 of file SpannerBerman.h.

OpenGraph DrawingFramework

Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Enumeration Documentation

◆ SeparationResult

Constructor & Destructor Documentation

◆ SpannerBerman()

◆ ~SpannerBerman()

Member Function Documentation

◆ _isThickEdge()

◆ addEdgeToSpanner()

◆ addUnsettledThickEdges()

◆ calculateThickEdges()

◆ createAntispanner()

◆ distance()

◆ execute()

◆ firstPart()

◆ inArborescence()

◆ init()

◆ isSettledEdge() [1/2]

◆ isSettledEdge() [2/2]

◆ isThickEdge()

◆ isThinEdge()

◆ outArborescence()

◆ preconditionsOk()

◆ printStats()

◆ randomizedSelection()

◆ resetLP()

◆ secondPart()

◆ separation()

◆ setOpt()

Member Data Documentation

◆ logger

◆ m_beta

◆ m_constraints

◆ m_E1

◆ m_E2

◆ m_eps

◆ m_G

◆ m_inDistance

◆ m_isThickEdge

◆ m_nSquared

◆ m_OPT

◆ m_osi

◆ m_outDistance

◆ m_spannerWeight

◆ m_sqrtlog

◆ m_thickEdgeNodeAmountLimit

◆ m_weight

Open
Graph Drawing
Framework