Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::steiner_tree::Full3ComponentGeneratorModule< T > Class Template Referenceabstract

Interface for full 3-component generation including auxiliary functions. More...

#include <ogdf/graphalg/steiner_tree/Full3ComponentGeneratorModule.h>

+ Inheritance diagram for ogdf::steiner_tree::Full3ComponentGeneratorModule< T >:

Public Member Functions

 Full3ComponentGeneratorModule ()=default
 
virtual ~Full3ComponentGeneratorModule ()=default
 
virtual void call (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const NodeArray< NodeArray< T >> &distance, const NodeArray< NodeArray< edge >> &pred, std::function< void(node, node, node, node, T)> generateFunction) const =0
 Generate full components and call generateFunction for each full component. More...
 

Protected Member Functions

void checkAndGenerateFunction (node u, node v, node w, node center, T minCost, const NodeArray< NodeArray< edge >> &pred, const NodeArray< bool > &isTerminal, std::function< void(node, node, node, node, T)> generateFunction) const
 
void forAllTerminalTriples (const List< node > &terminals, const NodeArray< NodeArray< T >> &distance, std::function< void(node, node, node, const NodeArray< T > &, const NodeArray< T > &, const NodeArray< T > &)> func) const
 
void updateBestCenter (node x, node &center, T &minCost, const NodeArray< T > &dist1, const NodeArray< T > &dist2, const NodeArray< T > &dist3) const
 Update center node if it is the best so far. More...
 

Detailed Description

template<typename T>
class ogdf::steiner_tree::Full3ComponentGeneratorModule< T >

Interface for full 3-component generation including auxiliary functions.

A full 3-component is basically a tree with exactly three terminal leaves but no inner terminals. There must be exactly one nonterminal of degree 3, the so-called center.

Definition at line 47 of file Full3ComponentGeneratorModule.h.

Constructor & Destructor Documentation

◆ Full3ComponentGeneratorModule()

◆ ~Full3ComponentGeneratorModule()

template<typename T >
virtual ogdf::steiner_tree::Full3ComponentGeneratorModule< T >::~Full3ComponentGeneratorModule ( )
virtualdefault

Member Function Documentation

◆ call()

template<typename T >
virtual void ogdf::steiner_tree::Full3ComponentGeneratorModule< T >::call ( const EdgeWeightedGraph< T > &  G,
const List< node > &  terminals,
const NodeArray< bool > &  isTerminal,
const NodeArray< NodeArray< T >> &  distance,
const NodeArray< NodeArray< edge >> &  pred,
std::function< void(node, node, node, node, T)>  generateFunction 
) const
pure virtual

Generate full components and call generateFunction for each full component.

Implemented in ogdf::steiner_tree::Full3ComponentGeneratorVoronoi< T >, and ogdf::steiner_tree::Full3ComponentGeneratorEnumeration< T >.

◆ checkAndGenerateFunction()

template<typename T >
void ogdf::steiner_tree::Full3ComponentGeneratorModule< T >::checkAndGenerateFunction ( node  u,
node  v,
node  w,
node  center,
minCost,
const NodeArray< NodeArray< edge >> &  pred,
const NodeArray< bool > &  isTerminal,
std::function< void(node, node, node, node, T)>  generateFunction 
) const
inlineprotected

Definition at line 103 of file Full3ComponentGeneratorModule.h.

◆ forAllTerminalTriples()

template<typename T >
void ogdf::steiner_tree::Full3ComponentGeneratorModule< T >::forAllTerminalTriples ( const List< node > &  terminals,
const NodeArray< NodeArray< T >> &  distance,
std::function< void(node, node, node, const NodeArray< T > &, const NodeArray< T > &, const NodeArray< T > &)>  func 
) const
inlineprotected

Definition at line 89 of file Full3ComponentGeneratorModule.h.

◆ updateBestCenter()

template<typename T >
void ogdf::steiner_tree::Full3ComponentGeneratorModule< T >::updateBestCenter ( node  x,
node center,
T &  minCost,
const NodeArray< T > &  dist1,
const NodeArray< T > &  dist2,
const NodeArray< T > &  dist3 
) const
inlineprotected

Update center node if it is the best so far.

(Just a helper to avoid code duplication.)

Parameters
xThe node to test
centerThe returned best center node
minCostThe returned cost of the component with that node
dist1SSSP distance vector of the first terminal
dist2SSSP distance vector of the second terminal
dist3SSSP distance vector of the third terminal

Definition at line 72 of file Full3ComponentGeneratorModule.h.


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