# OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::steiner_tree::goemans::Approximation< T > Class Template Reference

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

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

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

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

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

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

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

## Private Attributes

const double m_eps
epsilon for double operations More...

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

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 48 of file Approximation.h.

## ◆ 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 321 of file Approximation.h.

## Member Function Documentation

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 240 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 218 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 89 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 81 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 264 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 340 of file Approximation.h.

## ◆ 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& 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& ogdf::steiner_tree::goemans::Approximation< T >::m_G
private

Definition at line 50 of file Approximation.h.

## ◆ m_isTerminal

template<typename T >
 const NodeArray& 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& 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: