Open
Graph Drawing
Framework

 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.

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 321 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 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
isNewTerminalis an input/output parameter where new terminals are set to true

Definition at line 340 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: