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.

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

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

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

void	find3RestrictedComponents ()
	Find 3-restricted components.

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

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

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

void	findFullComponents ()
	Find full components.

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

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

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

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

Private Attributes
EdgeWeightedGraphCopy< T > *	m_approx2SteinerTree

T	m_approx2Weight

const double	m_eps
	epsilon for double operations

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

const EdgeWeightedGraph< T > &	m_G

const NodeArray< bool > &	m_isTerminal

int	m_restricted

const List< node > &	m_terminals
	List of terminals.

Approx2State	m_use2approx

Detailed Description

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

Class managing LP-based approximation.

Definition at line 144 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 269 of file MinSteinerTreeGoemans139.h.

◆ ~Main()

template<typename T >

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

inline

Definition at line 300 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 208 of file MinSteinerTreeGoemans139.h.

◆ find3RestrictedComponents()

template<typename T >

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

private

Find 3-restricted components.

Definition at line 337 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 308 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 320 of file MinSteinerTreeGoemans139.h.

◆ findFullComponents()

template<typename T >

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

private

Find full components.

Definition at line 387 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 366 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 379 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`
	)