Class managing LP-based approximation. More...

#include <ogdf/graphalg/MinSteinerTreeGoemans139.h>

Public Member Functions
	Main (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, int restricted, bool use2approx, bool separateCycles, double eps=1e-8)
	Initialize all attributes, sort the terminal list. More...

	~Main ()

T	getApproximation (EdgeWeightedGraphCopy< T > *&finalSteinerTree, const std::minstd_rand &rng, const bool doPreprocessing=true)
	Obtain an (1.39+epsilon)-approximation based on the LP solution. More...

Private Member Functions
Finding full components
void	findFull2Components (const NodeArray< NodeArray< T >> &distance, const NodeArray< NodeArray< edge >> &pred)
	Find full components of size 2. More...

void	findFull3Components (const NodeArray< NodeArray< T >> &distance, const NodeArray< NodeArray< edge >> &pred)
	Find full components of size 3. More...

void	find3RestrictedComponents ()
	Find 3-restricted components. More...

void	findFullComponentsDW ()
	Find full components using algorithm by Dreyfus-Wagner. More...

void	findFullComponentsEMV ()
	Find full components using algorithm by Erickson et al. More...

template<typename FCG >
void	retrieveComponents (const FCG &fcg)
	Auxiliary function to retrieve components by Dreyfus-Wagner/Erickson et al implementation. More...

void	findFullComponents ()
	Find full components. More...

Preliminaries and preprocessing for the approximation algorithm
void	removeInactiveComponents ()
	Remove inactive components from m_fullCompStore (since we do not need them any longer) More...

void	removeComponents (ArrayBuffer< int > &ids)
	Remove the full components with the given ids. More...

void	addComponent (NodeArray< bool > &isNewTerminal, int id)
	Add a full component to the final solution (by changing nonterminals to terminals) More...

void	preprocess (NodeArray< bool > &isNewTerminal)
	Preprocess LP solution. More...

Private Attributes
EdgeWeightedGraphCopy< T > *	m_approx2SteinerTree

T	m_approx2Weight

const double	m_eps
	epsilon for double operations More...

steiner_tree::FullComponentWithExtraStore< T, double >	m_fullCompStore
	all enumerated full components, with solution More...

const EdgeWeightedGraph< T > &	m_G

const NodeArray< bool > &	m_isTerminal

int	m_restricted

const List< node > &	m_terminals
	List of terminals. More...

Approx2State	m_use2approx

Detailed Description

template<typename T>
class ogdf::MinSteinerTreeGoemans139< T >::Main

Class managing LP-based approximation.

Definition at line 159 of file MinSteinerTreeGoemans139.h.

Constructor & Destructor Documentation

◆ Main()

template<typename T >

ogdf::MinSteinerTreeGoemans139< T >::Main::Main	(	const EdgeWeightedGraph< T > &	G,
		const List< node > &	terminals,
		const NodeArray< bool > &	isTerminal,
		int	restricted,
		bool	use2approx,
		bool	separateCycles,
		double	eps = `1e-8`
	)

inline

Initialize all attributes, sort the terminal list.

Definition at line 284 of file MinSteinerTreeGoemans139.h.

◆ ~Main()

template<typename T >

ogdf::MinSteinerTreeGoemans139< T >::Main::~Main ( )

inline

Definition at line 315 of file MinSteinerTreeGoemans139.h.

Member Function Documentation

◆ addComponent()

template<typename T >

void ogdf::MinSteinerTreeGoemans139< T >::Main::addComponent	(	NodeArray< bool > &	isNewTerminal,
		int	id
	)

inlineprivate

Add a full component to the final solution (by changing nonterminals to terminals)

Definition at line 223 of file MinSteinerTreeGoemans139.h.

◆ find3RestrictedComponents()

template<typename T >

void ogdf::MinSteinerTreeGoemans139< T >::Main::find3RestrictedComponents

private

Find 3-restricted components.

Definition at line 352 of file MinSteinerTreeGoemans139.h.

◆ findFull2Components()

template<typename T >

void ogdf::MinSteinerTreeGoemans139< T >::Main::findFull2Components	(	const NodeArray< NodeArray< T >> &	distance,
		const NodeArray< NodeArray< edge >> &	pred
	)

private

Find full components of size 2.

Definition at line 323 of file MinSteinerTreeGoemans139.h.

◆ findFull3Components()

template<typename T >

void ogdf::MinSteinerTreeGoemans139< T >::Main::findFull3Components	(	const NodeArray< NodeArray< T >> &	distance,
		const NodeArray< NodeArray< edge >> &	pred
	)

private

Find full components of size 3.

Definition at line 335 of file MinSteinerTreeGoemans139.h.

◆ findFullComponents()

template<typename T >

void ogdf::MinSteinerTreeGoemans139< T >::Main::findFullComponents

private

Find full components.

Definition at line 402 of file MinSteinerTreeGoemans139.h.

◆ findFullComponentsDW()

template<typename T >

void ogdf::MinSteinerTreeGoemans139< T >::Main::findFullComponentsDW

private

Find full components using algorithm by Dreyfus-Wagner.

Definition at line 381 of file MinSteinerTreeGoemans139.h.

◆ findFullComponentsEMV()

template<typename T >

void ogdf::MinSteinerTreeGoemans139< T >::Main::findFullComponentsEMV

private

Find full components using algorithm by Erickson et al.

Definition at line 394 of file MinSteinerTreeGoemans139.h.

◆ getApproximation()

template<typename T >

T ogdf::MinSteinerTreeGoemans139< T >::Main::getApproximation	(	EdgeWeightedGraphCopy< T > *&	finalSteinerTree,
		const std::minstd_rand &	rng,
		const bool	doPreprocessing = `true`
	)