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

Static Public Attributes
static Logger	logger

Private Types
enum	SeparationResult { SeparationResult::NewConstraint, SeparationResult::Fail, SeparationResult::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. More...

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

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

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

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

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

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

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

void	printStats (bool assert=false)

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

void	resetLP ()
	Resets the LP defining variables. More...

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

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

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

Private Attributes
double	m_beta
	sqrt(n) More...

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

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

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

EpsilonTest	m_eps

const Graph *	m_G
	const reference to the original graph More...

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

EdgeArray< bool >	m_isThickEdge

int	m_nSquared
	n^2 More...

int	m_OPT
	The current guess for our optimal LP value. More...

OsiSolverInterface *	m_osi
	the solver. More...

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

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

double	m_sqrtlog
	sqrt(n) * ln(n) More...

int	m_thickEdgeNodeAmountLimit
	n/beta More...

EdgeArray< TWeight >	m_weight
	weights of each edge from m_G 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 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 89 of file SpannerBerman.h.

Member Enumeration Documentation

◆ SeparationResult

template<typename TWeight >

enum ogdf::SpannerBerman::SeparationResult

strongprivate

Used to indicate the result of the separation method.

Enumerator
NewConstraint
Fail
Solution

Definition at line 122 of file SpannerBerman.h.

Constructor & Destructor Documentation

◆ SpannerBerman()

template<typename TWeight >

ogdf::SpannerBerman< TWeight >::SpannerBerman ( )

inline

Definition at line 93 of file SpannerBerman.h.

◆ ~SpannerBerman()

template<typename TWeight >

virtual ogdf::SpannerBerman< TWeight >::~SpannerBerman ( )

inlinevirtual

Definition at line 98 of file SpannerBerman.h.

Member Function Documentation

◆ _isThickEdge()

template<typename TWeight >

bool ogdf::SpannerBerman< TWeight >::_isThickEdge ( edge e )

inlineprivate

Actually calculates whether e is thick or not.

Definition at line 351 of file SpannerBerman.h.

◆ addEdgeToSpanner()

template<typename TWeight >

void ogdf::SpannerBerman< TWeight >::addEdgeToSpanner ( edge e )

inlineprivate

Add an edge to the spanner.

Only used in the first phase!

Definition at line 277 of file SpannerBerman.h.

◆ addUnsettledThickEdges()

template<typename TWeight >

void ogdf::SpannerBerman< TWeight >::addUnsettledThickEdges ( )

inlineprivate

Definition at line 405 of file SpannerBerman.h.

◆ calculateThickEdges()

template<typename TWeight >

void ogdf::SpannerBerman< TWeight >::calculateThickEdges ( )

inlineprivate

Definition at line 342 of file SpannerBerman.h.

◆ createAntispanner()

template<typename TWeight >

void ogdf::SpannerBerman< TWeight >::createAntispanner	(	const edge	unsettledThinEdge,
		const EdgeArray< bool > &	out,
		EdgeArray< bool > &	antispanner
	)

inlineprivate

Definition at line 596 of file SpannerBerman.h.

◆ distance()

template<typename TWeight >

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

inlineprivate

Definition at line 394 of file SpannerBerman.h.

◆ execute()

template<typename TWeight >

virtual SpannerModule<TWeight>::ReturnType ogdf::SpannerBerman< 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 196 of file SpannerBerman.h.

◆ firstPart()

template<typename TWeight >

void ogdf::SpannerBerman< TWeight >::firstPart ( )

inlineprivate

First part of the algorithm: Settle all thick edges.

Definition at line 222 of file SpannerBerman.h.

◆ inArborescence()

template<typename TWeight >

void ogdf::SpannerBerman< TWeight >::inArborescence	(	const GraphAttributes &	GA,
		node	root,
		NodeArray< edge > &	predecessor,
		NodeArray< TWeight > &	distance
	)

inlineprivate

Calculates an in-arborescense rooted at root.

Definition at line 259 of file SpannerBerman.h.

◆ init()

template<typename TWeight >

virtual void ogdf::SpannerBerman< 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 170 of file SpannerBerman.h.

◆ isSettledEdge() [1/2]

template<typename TWeight >

bool ogdf::SpannerBerman< TWeight >::isSettledEdge ( const edge e )

inlineprivate

Shortcut for calling isSettledEdge with m_spanner and the current spanner weights.

Definition at line 380 of file SpannerBerman.h.

◆ isSettledEdge() [2/2]

template<typename TWeight >

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

inlineprivate

Returns: true, if the edge is settles in the given spanner.

Definition at line 385 of file SpannerBerman.h.

◆ isThickEdge()

template<typename TWeight >

bool ogdf::SpannerBerman< TWeight >::isThickEdge ( edge e )

inlineprivate

Definition at line 152 of file SpannerBerman.h.

◆ isThinEdge()

template<typename TWeight >

bool ogdf::SpannerBerman< TWeight >::isThinEdge ( edge e )

inlineprivate

Definition at line 150 of file SpannerBerman.h.

◆ outArborescence()

template<typename TWeight >

void ogdf::SpannerBerman< TWeight >::outArborescence	(	const GraphAttributes &	GA,
		node	root,
		NodeArray< edge > &	predecessor,
		NodeArray< TWeight > &	distance
	)

inlineprivate

Calculates an out-arborescense rooted at root.

Definition at line 268 of file SpannerBerman.h.

◆ preconditionsOk()

template<typename TWeight >

virtual bool ogdf::SpannerBerman< 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 101 of file SpannerBerman.h.

◆ printStats()

template<typename TWeight >

void ogdf::SpannerBerman< TWeight >::printStats ( bool assert = false )

inlineprivate

Definition at line 285 of file SpannerBerman.h.

◆ randomizedSelection()

template<typename TWeight >

void ogdf::SpannerBerman< TWeight >::randomizedSelection	(	const double *	fractions,
		EdgeArray< bool > &	out
	)

inlineprivate

Definition at line 587 of file SpannerBerman.h.

◆ resetLP()

template<typename TWeight >

void ogdf::SpannerBerman< TWeight >::resetLP ( )

inlineprivate

Resets the LP defining variables.

Deletes m_osi as well as every entry in m_constraints. Sets both variables to nullptr/empty list.

Definition at line 159 of file SpannerBerman.h.

◆ secondPart()

template<typename TWeight >

bool ogdf::SpannerBerman< TWeight >::secondPart ( )

inlineprivate

The second part: Settling all thin edges.

Definition at line 423 of file SpannerBerman.h.

◆ separation()

template<typename TWeight >

SeparationResult ogdf::SpannerBerman< TWeight >::separation	(	const double *	solution,
		const EdgeArray< int > &	indices
	)

inlineprivate

Definition at line 522 of file SpannerBerman.h.

◆ setOpt()

template<typename TWeight >

bool ogdf::SpannerBerman< TWeight >::setOpt ( int opt )

inlineprivate

Set a new value for m_OPT.

Logs about the new value and modifies the LP.

Returns: false, if the new value is too large. If so, the calculation can be aborted.

Definition at line 507 of file SpannerBerman.h.

Member Data Documentation

◆ logger

template<typename TWeight >

Logger ogdf::SpannerBerman< TWeight >::logger

static

Definition at line 91 of file SpannerBerman.h.

◆ m_beta

template<typename TWeight >

double ogdf::SpannerBerman< TWeight >::m_beta

private

sqrt(n)

Definition at line 133 of file SpannerBerman.h.

◆ m_constraints

template<typename TWeight >

std::vector<CoinPackedVector*> ogdf::SpannerBerman< TWeight >::m_constraints

private

Holds all constraints so they can be freed at destruction.

Definition at line 145 of file SpannerBerman.h.

◆ m_E1

template<typename TWeight >

EdgeArray<bool> ogdf::SpannerBerman< TWeight >::m_E1

private

Holds the set E1 from the first part of the algorithm.

Definition at line 137 of file SpannerBerman.h.

◆ m_E2

template<typename TWeight >

EdgeArray<bool> ogdf::SpannerBerman< TWeight >::m_E2

private

Holds the set E2 from the second part of the algorithm.

Definition at line 138 of file SpannerBerman.h.

◆ m_eps

template<typename TWeight >

EpsilonTest ogdf::SpannerBerman< TWeight >::m_eps

private

Definition at line 148 of file SpannerBerman.h.

◆ m_G

template<typename TWeight >

const Graph* ogdf::SpannerBerman< TWeight >::m_G

private

const reference to the original graph

Definition at line 124 of file SpannerBerman.h.

◆ m_inDistance

template<typename TWeight >

NodeArray<NodeArray<TWeight> > ogdf::SpannerBerman< TWeight >::m_inDistance

private

m_inDistance[v][w]: distance from v in a v-rooted in-arborescense to w

Definition at line 140 of file SpannerBerman.h.

◆ m_isThickEdge

template<typename TWeight >

EdgeArray<bool> ogdf::SpannerBerman< TWeight >::m_isThickEdge

private

Definition at line 129 of file SpannerBerman.h.

◆ m_nSquared

template<typename TWeight >

int ogdf::SpannerBerman< TWeight >::m_nSquared

private

n^2

Definition at line 132 of file SpannerBerman.h.

◆ m_OPT

template<typename TWeight >

int ogdf::SpannerBerman< TWeight >::m_OPT

private

The current guess for our optimal LP value.

Definition at line 146 of file SpannerBerman.h.

◆ m_osi

template<typename TWeight >

OsiSolverInterface* ogdf::SpannerBerman< TWeight >::m_osi

private

the solver.

Initial nullptr since it is initialized in the second phase.

Definition at line 144 of file SpannerBerman.h.

◆ m_outDistance

template<typename TWeight >

NodeArray<NodeArray<TWeight> > ogdf::SpannerBerman< TWeight >::m_outDistance

private

m_outDistance[v][w]: distance from v in a v-rooted out-arborescense to w

Definition at line 141 of file SpannerBerman.h.

◆ m_spannerWeight

template<typename TWeight >

EdgeArray<TWeight> ogdf::SpannerBerman< TWeight >::m_spannerWeight

private

weights for m_spanner Caches, if an edge is thick (or thin).

Use isThinEdge and isThickEdge for access. It is fully cached after calling calculateThickEdges

Definition at line 126 of file SpannerBerman.h.

◆ m_sqrtlog

template<typename TWeight >

double ogdf::SpannerBerman< TWeight >::m_sqrtlog

private

sqrt(n) * ln(n)

Definition at line 134 of file SpannerBerman.h.

◆ m_thickEdgeNodeAmountLimit

template<typename TWeight >

int ogdf::SpannerBerman< TWeight >::m_thickEdgeNodeAmountLimit

private

n/beta

Definition at line 135 of file SpannerBerman.h.

◆ m_weight

template<typename TWeight >

EdgeArray<TWeight> ogdf::SpannerBerman< TWeight >::m_weight

private

weights of each edge from m_G

Definition at line 125 of file SpannerBerman.h.

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

include/ogdf/graphalg/SpannerBerman.h

OpenGraph DrawingFramework

Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

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

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

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