Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MinSteinerTreeGoemans139< T >::Main Class Reference

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 ()
 
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
 
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 164 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 292 of file MinSteinerTreeGoemans139.h.

◆ ~Main()

template<typename T >
ogdf::MinSteinerTreeGoemans139< T >::Main::~Main ( )
inline

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

◆ find3RestrictedComponents()

template<typename T >
void ogdf::MinSteinerTreeGoemans139< T >::Main::find3RestrictedComponents
private

Find 3-restricted components.

Definition at line 361 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 331 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 344 of file MinSteinerTreeGoemans139.h.

◆ findFullComponents()

template<typename T >
void ogdf::MinSteinerTreeGoemans139< T >::Main::findFullComponents
private

Find full components.

Definition at line 407 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 389 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 400 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 
)

Obtain an (1.39+epsilon)-approximation based on the LP solution.

Definition at line 422 of file MinSteinerTreeGoemans139.h.

◆ preprocess()

template<typename T >
void ogdf::MinSteinerTreeGoemans139< T >::Main::preprocess ( NodeArray< bool > &  isNewTerminal)
inlineprivate

Preprocess LP solution.

Precondition
every terminal is covered with >= 1

Definition at line 236 of file MinSteinerTreeGoemans139.h.

◆ removeComponents()

template<typename T >
void ogdf::MinSteinerTreeGoemans139< T >::Main::removeComponents ( ArrayBuffer< int > &  ids)
inlineprivate

Remove the full components with the given ids.

Definition at line 218 of file MinSteinerTreeGoemans139.h.

◆ removeInactiveComponents()

template<typename T >
void ogdf::MinSteinerTreeGoemans139< T >::Main::removeInactiveComponents ( )
inlineprivate

Remove inactive components from m_fullCompStore (since we do not need them any longer)

Definition at line 208 of file MinSteinerTreeGoemans139.h.

◆ retrieveComponents()

template<typename T >
template<typename FCG >
void ogdf::MinSteinerTreeGoemans139< T >::Main::retrieveComponents ( const FCG &  fcg)
private

Auxiliary function to retrieve components by Dreyfus-Wagner/Erickson et al implementation.

Definition at line 375 of file MinSteinerTreeGoemans139.h.

Member Data Documentation

◆ m_approx2SteinerTree

template<typename T >
EdgeWeightedGraphCopy<T>* ogdf::MinSteinerTreeGoemans139< T >::Main::m_approx2SteinerTree
private

Definition at line 181 of file MinSteinerTreeGoemans139.h.

◆ m_approx2Weight

template<typename T >
T ogdf::MinSteinerTreeGoemans139< T >::Main::m_approx2Weight
private

Definition at line 182 of file MinSteinerTreeGoemans139.h.

◆ m_eps

template<typename T >
const double ogdf::MinSteinerTreeGoemans139< T >::Main::m_eps
private

epsilon for double operations

Definition at line 179 of file MinSteinerTreeGoemans139.h.

◆ m_fullCompStore

template<typename T >
steiner_tree::FullComponentWithExtraStore<T, double> ogdf::MinSteinerTreeGoemans139< T >::Main::m_fullCompStore
private

all enumerated full components, with solution

Definition at line 169 of file MinSteinerTreeGoemans139.h.

◆ m_G

template<typename T >
const EdgeWeightedGraph<T>& ogdf::MinSteinerTreeGoemans139< T >::Main::m_G
private

Definition at line 166 of file MinSteinerTreeGoemans139.h.

◆ m_isTerminal

template<typename T >
const NodeArray<bool>& ogdf::MinSteinerTreeGoemans139< T >::Main::m_isTerminal
private

Definition at line 167 of file MinSteinerTreeGoemans139.h.

◆ m_restricted

template<typename T >
int ogdf::MinSteinerTreeGoemans139< T >::Main::m_restricted
private

Definition at line 171 of file MinSteinerTreeGoemans139.h.

◆ m_terminals

template<typename T >
const List<node>& ogdf::MinSteinerTreeGoemans139< T >::Main::m_terminals
private

List of terminals.

Definition at line 168 of file MinSteinerTreeGoemans139.h.

◆ m_use2approx

template<typename T >
Approx2State ogdf::MinSteinerTreeGoemans139< T >::Main::m_use2approx
private

Definition at line 177 of file MinSteinerTreeGoemans139.h.


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