The actual 1.39-approximation algorithm by Goemans et al. with a set of terminalized nodes as result. More...

#include <ogdf/graphalg/steiner_tree/goemans/Approximation.h>

Classes
struct	TemporaryEdges
	Add edges into a blowup graph and delete them on destruction. More...

Public Member Functions
	Approximation (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const FullComponentWithExtraStore< T, double > &fullCompStore, const std::minstd_rand &rng, double eps=1e-8)
	Initialize everything.

void	solve (NodeArray< bool > &isNewTerminal)
	Perform the actual approximation algorithm on the LP solution.

Private Member Functions
void	addComponent (NodeArray< bool > &isNewTerminal, const BlowupGraph< T > &blowupGraph, const edge rootEdge)
	Add a component of the blowup graph to the final solution (by changing nonterminals to terminals)

int	findCheapestComponentAndRemainingBasis (std::unique_ptr< ArrayBuffer< std::pair< node, int > > > &maxBasis, const BlowupGraph< T > &blowupGraph, const BlowupComponents< T > &gamma)
	For the end of the algorithm: find cheapest component and choose all remaining core edges as basis.

int	findComponentAndMaxBasis (std::unique_ptr< ArrayBuffer< std::pair< node, int > > > &maxBasis, BlowupGraph< T > &blowupGraph, const BlowupComponents< T > &gamma)
	Finds the best component and its maximum-weight basis in the given blowup graph with given core and witness set.

int	gammoidGetRank (const BlowupGraph< T > &blowupGraph) const
	Computes the rank of the gammoid (given by the blowup graph)

void	removeFractionalBasisAndCleanup (ArrayBuffer< std::pair< node, int > > &basis, BlowupGraph< T > &blowupGraph, BlowupComponents< T > &gamma)
	Remove a given basis and cleanup, the basis may be given fractionally.

Private Attributes
const double	m_eps
	epsilon for double operations

const FullComponentWithExtraStore< T, double > &	m_fullCompStore
	all enumerated full components, with solution

const EdgeWeightedGraph< T > &	m_G

const NodeArray< bool > &	m_isTerminal

std::minstd_rand	m_rng

const List< node > &	m_terminals

Detailed Description

template<typename T>
class ogdf::steiner_tree::goemans::Approximation< T >

The actual 1.39-approximation algorithm by Goemans et al. with a set of terminalized nodes as result.

Definition at line 49 of file Approximation.h.

Constructor & Destructor Documentation

◆ Approximation()

template<typename T >

ogdf::steiner_tree::goemans::Approximation< T >::Approximation	(	const EdgeWeightedGraph< T > &	G,
		const List< node > &	terminals,
		const NodeArray< bool > &	isTerminal,
		const FullComponentWithExtraStore< T, double > &	fullCompStore,
		const std::minstd_rand &	rng,
		double	eps = `1e-8`
	)

inline

Initialize everything.

Definition at line 316 of file Approximation.h.

Member Function Documentation

◆ addComponent()

template<typename T >

void ogdf::steiner_tree::goemans::Approximation< T >::addComponent	(	NodeArray< bool > &	isNewTerminal,
		const BlowupGraph< T > &	blowupGraph,
		const edge	rootEdge
	)

inlineprivate

Add a component of the blowup graph to the final solution (by changing nonterminals to terminals)

Definition at line 236 of file Approximation.h.

◆ findCheapestComponentAndRemainingBasis()

template<typename T >

int ogdf::steiner_tree::goemans::Approximation< T >::findCheapestComponentAndRemainingBasis	(	std::unique_ptr< ArrayBuffer< std::pair< node, int > > > &	maxBasis,
		const BlowupGraph< T > &	blowupGraph,
		const BlowupComponents< T > &	gamma
	)

inlineprivate

For the end of the algorithm: find cheapest component and choose all remaining core edges as basis.

Returns: The component id of the cheapest component

Definition at line 215 of file Approximation.h.

◆ findComponentAndMaxBasis()

template<typename T >

int ogdf::steiner_tree::goemans::Approximation< T >::findComponentAndMaxBasis	(	std::unique_ptr< ArrayBuffer< std::pair< node, int > > > &	maxBasis,
		BlowupGraph< T > &	blowupGraph,
		const BlowupComponents< T > &	gamma
	)

inlineprivate

Finds the best component and its maximum-weight basis in the given blowup graph with given core and witness set.

Returns: The component id of the best component

Definition at line 87 of file Approximation.h.

◆ gammoidGetRank()

template<typename T >

int ogdf::steiner_tree::goemans::Approximation< T >::gammoidGetRank ( const BlowupGraph< T > & blowupGraph ) const

inlineprivate

Computes the rank of the gammoid (given by the blowup graph)

Definition at line 79 of file Approximation.h.

◆ removeFractionalBasisAndCleanup()

template<typename T >

void ogdf::steiner_tree::goemans::Approximation< T >::removeFractionalBasisAndCleanup	(	ArrayBuffer< std::pair< node, int > > &	basis,
		BlowupGraph< T > &	blowupGraph,
		BlowupComponents< T > &	gamma
	)

inlineprivate

Remove a given basis and cleanup, the basis may be given fractionally.

Definition at line 260 of file Approximation.h.

◆ solve()

template<typename T >

void ogdf::steiner_tree::goemans::Approximation< T >::solve ( NodeArray< bool > & isNewTerminal )

Perform the actual approximation algorithm on the LP solution.

Parameters

isNewTerminal is an input/output parameter where new terminals are set to true

Definition at line 333 of file Approximation.h.

Member Data Documentation

◆ m_eps

template<typename T >

const double ogdf::steiner_tree::goemans::Approximation< T >::m_eps

private

epsilon for double operations

Definition at line 55 of file Approximation.h.

◆ m_fullCompStore

template<typename T >

const FullComponentWithExtraStore<T, double>& ogdf::steiner_tree::goemans::Approximation< T >::m_fullCompStore

private

all enumerated full components, with solution

Definition at line 53 of file Approximation.h.

◆ m_G

template<typename T >

const EdgeWeightedGraph<T>& ogdf::steiner_tree::goemans::Approximation< T >::m_G

private

Definition at line 50 of file Approximation.h.

◆ m_isTerminal

template<typename T >

const NodeArray<bool>& ogdf::steiner_tree::goemans::Approximation< T >::m_isTerminal

private

Definition at line 51 of file Approximation.h.

◆ m_rng

template<typename T >

std::minstd_rand ogdf::steiner_tree::goemans::Approximation< T >::m_rng

private

Definition at line 57 of file Approximation.h.

◆ m_terminals

template<typename T >

const List<node>& ogdf::steiner_tree::goemans::Approximation< T >::m_terminals

private

Definition at line 52 of file Approximation.h.

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

include/ogdf/graphalg/steiner_tree/goemans/Approximation.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Approximation()

Member Function Documentation

◆ addComponent()

◆ findCheapestComponentAndRemainingBasis()

◆ findComponentAndMaxBasis()

◆ gammoidGetRank()

◆ removeFractionalBasisAndCleanup()

◆ solve()

Member Data Documentation

◆ m_eps

◆ m_fullCompStore

◆ m_G

◆ m_isTerminal

◆ m_rng

◆ m_terminals

Open
Graph Drawing
Framework