Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
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.
 
 ~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.
 

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
 
m_approx2Weight
 
const double m_eps
 epsilon for double operations
 
steiner_tree::FullComponentWithExtraStore< T, doublem_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 
)

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

Definition at line 401 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 214 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 200 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 190 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 352 of file MinSteinerTreeGoemans139.h.

Member Data Documentation

◆ m_approx2SteinerTree

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

Definition at line 161 of file MinSteinerTreeGoemans139.h.

◆ m_approx2Weight

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

Definition at line 162 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 159 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 149 of file MinSteinerTreeGoemans139.h.

◆ m_G

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

Definition at line 145 of file MinSteinerTreeGoemans139.h.

◆ m_isTerminal

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

Definition at line 146 of file MinSteinerTreeGoemans139.h.

◆ m_restricted

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

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

◆ m_use2approx

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

Definition at line 157 of file MinSteinerTreeGoemans139.h.


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