Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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

#include <ogdf/graphalg/MinSteinerTreeRZLoss.h>

Public Member Functions

 Main (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, int restricted)
 
getApproximation (EdgeWeightedGraphCopy< T > *&finalSteinerTree) const
 
long numberOfComponentLookUps ()
 Returns the number of components lookups during execution time. More...
 
long numberOfContractedComponents ()
 Returns the number of contracted components. More...
 
long numberOfGeneratedComponents ()
 Returns the number of generated components. More...
 

Private Types

template<typename TYPE >
using SaveStatic = steiner_tree::SaveStatic< TYPE >
 

Private Member Functions

void contractLoss (EdgeWeightedGraphCopy< T > &steinerTree, int compId)
 Contracts the loss of a full component and integrates it into the given terminal-spanning tree. More...
 
double extractMaxComponent (const EdgeWeightedGraphCopy< T > &steinerTree, int &maxCompId)
 Traverses over all full components and finds the one with the highest win-objective. More...
 
template<typename TERMINAL_CONTAINER >
gain (const TERMINAL_CONTAINER &terminals, const EdgeWeightedGraphCopy< T > &steinerTree)
 
void generateInitialTerminalSpanningTree (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< NodeArray< T >> &distance, const NodeArray< NodeArray< edge >> &pred)
 Builds a minimum terminal spanning tree (via a MST call on the complete terminal graph) More...
 
void multiPass (EdgeWeightedGraphCopy< T > &steinerTree)
 Contraction phase of the algorithm. More...
 
void setup (EdgeWeightedGraphCopy< T > &tree)
 Setup (build initial terminal-spanning tree, its save data structure, and find all components) More...
 
Finding full components
void findFullComponentsDW (const EdgeWeightedGraphCopy< T > &tree, const NodeArray< NodeArray< T >> &distance, const NodeArray< NodeArray< edge >> &pred)
 Find full components using algorithm by Dreyfus-Wagner. More...
 
void findFullComponentsEMV (const EdgeWeightedGraphCopy< T > &tree)
 Find full components using algorithm by Erickson et al. More...
 
void findFull3Components (const EdgeWeightedGraphCopy< T > &tree, const NodeArray< NodeArray< T >> &distance, const NodeArray< NodeArray< edge >> &pred)
 Find full components of size 3. More...
 
template<typename FCG >
void retrieveComponents (const FCG &fcg, const EdgeWeightedGraphCopy< T > &tree)
 Auxiliary function to retrieve components by Dreyfus-Wagner/Erickson et al implementation. More...
 

Private Attributes

long m_componentsContracted
 Number of contracted components. More...
 
long m_componentsGenerated
 Number of generated components. More...
 
long m_componentsLookUps
 Number of components lookups. More...
 
steiner_tree::FullComponentWithLossStore< T > m_fullCompStore
 All generated full components. More...
 
const EdgeWeightedGraph< T > & m_G
 The original edge-weighted graph. More...
 
NodeArray< bool > m_isNewTerminal
 Incidence vector for nonterminal nodes marked as terminals for improvement. More...
 
const NodeArray< bool > & m_isTerminal
 Incidence vector for terminal nodes. More...
 
int m_restricted
 Parameter for the number of terminals in a full component. More...
 
std::unique_ptr< steiner_tree::SaveStatic< T > > m_save
 The save data structure. More...
 
List< nodem_terminals
 List of terminal nodes (will be copied and sorted) More...
 

Detailed Description

template<typename T>
class ogdf::MinSteinerTreeRZLoss< T >::Main

Definition at line 134 of file MinSteinerTreeRZLoss.h.

Member Typedef Documentation

◆ SaveStatic

template<typename T >
template<typename TYPE >
using ogdf::MinSteinerTreeRZLoss< T >::Main::SaveStatic = steiner_tree::SaveStatic<TYPE>
private

Definition at line 135 of file MinSteinerTreeRZLoss.h.

Constructor & Destructor Documentation

◆ Main()

template<typename T >
ogdf::MinSteinerTreeRZLoss< T >::Main::Main ( const EdgeWeightedGraph< T > &  G,
const List< node > &  terminals,
const NodeArray< bool > &  isTerminal,
int  restricted 
)

Definition at line 261 of file MinSteinerTreeRZLoss.h.

Member Function Documentation

◆ contractLoss()

template<typename T >
void ogdf::MinSteinerTreeRZLoss< T >::Main::contractLoss ( EdgeWeightedGraphCopy< T > &  steinerTree,
int  compId 
)
private

Contracts the loss of a full component and integrates it into the given terminal-spanning tree.

Parameters
steinerTreeThe Steiner tree into which the full component is integrated
compIdThe full component to be contracted and inserted

Definition at line 447 of file MinSteinerTreeRZLoss.h.

◆ extractMaxComponent()

template<typename T >
double ogdf::MinSteinerTreeRZLoss< T >::Main::extractMaxComponent ( const EdgeWeightedGraphCopy< T > &  steinerTree,
int &  maxCompId 
)
private

Traverses over all full components and finds the one with the highest win-objective.

Parameters
steinerTreeCurrent Steiner tree
maxCompIdThe index of the full component with highest win-objective
Returns
the win-objective of the returned full component

Definition at line 398 of file MinSteinerTreeRZLoss.h.

◆ findFull3Components()

template<typename T >
void ogdf::MinSteinerTreeRZLoss< T >::Main::findFull3Components ( const EdgeWeightedGraphCopy< T > &  tree,
const NodeArray< NodeArray< T >> &  distance,
const NodeArray< NodeArray< edge >> &  pred 
)
private

Find full components of size 3.

Definition at line 312 of file MinSteinerTreeRZLoss.h.

◆ findFullComponentsDW()

template<typename T >
void ogdf::MinSteinerTreeRZLoss< T >::Main::findFullComponentsDW ( const EdgeWeightedGraphCopy< T > &  tree,
const NodeArray< NodeArray< T >> &  distance,
const NodeArray< NodeArray< edge >> &  pred 
)
private

Find full components using algorithm by Dreyfus-Wagner.

Parameters
treeCurrent minimal terminal spanning tree
distanceThe distance matrix
predThe predecessor matrix for shortest paths

Definition at line 358 of file MinSteinerTreeRZLoss.h.

◆ findFullComponentsEMV()

template<typename T >
void ogdf::MinSteinerTreeRZLoss< T >::Main::findFullComponentsEMV ( const EdgeWeightedGraphCopy< T > &  tree)
private

Find full components using algorithm by Erickson et al.

Definition at line 366 of file MinSteinerTreeRZLoss.h.

◆ gain()

template<typename T >
template<typename TERMINAL_CONTAINER >
T ogdf::MinSteinerTreeRZLoss< T >::Main::gain ( const TERMINAL_CONTAINER &  terminals,
const EdgeWeightedGraphCopy< T > &  steinerTree 
)
private
   \brief Calculates the gain for a full component
  • *
    Parameters
    terminalsThe terminals of the full component
    steinerTreeCurrent Steiner tree
    Returns
    the gain (cost of save edges) of the returned full component

Definition at line 426 of file MinSteinerTreeRZLoss.h.

◆ generateInitialTerminalSpanningTree()

template<typename T >
void ogdf::MinSteinerTreeRZLoss< T >::Main::generateInitialTerminalSpanningTree ( EdgeWeightedGraphCopy< T > &  steinerTree,
const NodeArray< NodeArray< T >> &  distance,
const NodeArray< NodeArray< edge >> &  pred 
)
private

Builds a minimum terminal spanning tree (via a MST call on the complete terminal graph)

Parameters
steinerTreeThe resulting minimum terminal spanning tree
distanceThe distance matrix
predThe predecessor matrix for shortest paths

Definition at line 289 of file MinSteinerTreeRZLoss.h.

◆ getApproximation()

template<typename T >
T ogdf::MinSteinerTreeRZLoss< T >::Main::getApproximation ( EdgeWeightedGraphCopy< T > *&  finalSteinerTree) const
inline

Definition at line 239 of file MinSteinerTreeRZLoss.h.

◆ multiPass()

template<typename T >
void ogdf::MinSteinerTreeRZLoss< T >::Main::multiPass ( EdgeWeightedGraphCopy< T > &  steinerTree)
private

Contraction phase of the algorithm.

Parameters
steinerTreethe terminal-spanning tree to be modified

Definition at line 373 of file MinSteinerTreeRZLoss.h.

◆ numberOfComponentLookUps()

template<typename T >
long ogdf::MinSteinerTreeRZLoss< T >::Main::numberOfComponentLookUps ( )
inline

Returns the number of components lookups during execution time.

Definition at line 255 of file MinSteinerTreeRZLoss.h.

◆ numberOfContractedComponents()

template<typename T >
long ogdf::MinSteinerTreeRZLoss< T >::Main::numberOfContractedComponents ( )
inline

Returns the number of contracted components.

Definition at line 250 of file MinSteinerTreeRZLoss.h.

◆ numberOfGeneratedComponents()

template<typename T >
long ogdf::MinSteinerTreeRZLoss< T >::Main::numberOfGeneratedComponents ( )
inline

Returns the number of generated components.

Definition at line 245 of file MinSteinerTreeRZLoss.h.

◆ retrieveComponents()

template<typename T >
template<typename FCG >
void ogdf::MinSteinerTreeRZLoss< T >::Main::retrieveComponents ( const FCG &  fcg,
const EdgeWeightedGraphCopy< T > &  tree 
)
private

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

Definition at line 337 of file MinSteinerTreeRZLoss.h.

◆ setup()

template<typename T >
void ogdf::MinSteinerTreeRZLoss< T >::Main::setup ( EdgeWeightedGraphCopy< T > &  tree)
inlineprivate

Setup (build initial terminal-spanning tree, its save data structure, and find all components)

Definition at line 166 of file MinSteinerTreeRZLoss.h.

Member Data Documentation

◆ m_componentsContracted

template<typename T >
long ogdf::MinSteinerTreeRZLoss< T >::Main::m_componentsContracted
private

Number of contracted components.

Definition at line 233 of file MinSteinerTreeRZLoss.h.

◆ m_componentsGenerated

template<typename T >
long ogdf::MinSteinerTreeRZLoss< T >::Main::m_componentsGenerated
private

Number of generated components.

Definition at line 232 of file MinSteinerTreeRZLoss.h.

◆ m_componentsLookUps

template<typename T >
long ogdf::MinSteinerTreeRZLoss< T >::Main::m_componentsLookUps
private

Number of components lookups.

Definition at line 234 of file MinSteinerTreeRZLoss.h.

◆ m_fullCompStore

template<typename T >
steiner_tree::FullComponentWithLossStore<T> ogdf::MinSteinerTreeRZLoss< T >::Main::m_fullCompStore
private

All generated full components.

Definition at line 229 of file MinSteinerTreeRZLoss.h.

◆ m_G

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

The original edge-weighted graph.

Definition at line 224 of file MinSteinerTreeRZLoss.h.

◆ m_isNewTerminal

template<typename T >
NodeArray<bool> ogdf::MinSteinerTreeRZLoss< T >::Main::m_isNewTerminal
private

Incidence vector for nonterminal nodes marked as terminals for improvement.

Definition at line 230 of file MinSteinerTreeRZLoss.h.

◆ m_isTerminal

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

Incidence vector for terminal nodes.

Definition at line 225 of file MinSteinerTreeRZLoss.h.

◆ m_restricted

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

Parameter for the number of terminals in a full component.

Definition at line 227 of file MinSteinerTreeRZLoss.h.

◆ m_save

template<typename T >
std::unique_ptr<steiner_tree::SaveStatic<T> > ogdf::MinSteinerTreeRZLoss< T >::Main::m_save
private

The save data structure.

Definition at line 228 of file MinSteinerTreeRZLoss.h.

◆ m_terminals

template<typename T >
List<node> ogdf::MinSteinerTreeRZLoss< T >::Main::m_terminals
private

List of terminal nodes (will be copied and sorted)

Definition at line 226 of file MinSteinerTreeRZLoss.h.


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