# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
ogdf::MinSteinerTreeZelikovsky< T > Class Template Reference

This class implements the 11/6-approximation algorithm by Zelikovsky for the minimum Steiner tree problem along with variants and practical improvements. More...

#include <ogdf/graphalg/MinSteinerTreeZelikovsky.h>

Inheritance diagram for ogdf::MinSteinerTreeZelikovsky< T >:

## Public Types

enum class  Pass { one , multi }
Enables a heuristic version (for TG exhaustive and voronoi only) More...

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

enum class  SaveCalculation { staticEnum , staticLCATree , dynamicLCATree , hybrid }
Different methods for obtaining save edges. More...

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

enum class  TripleGeneration { exhaustive , voronoi , ondemand }
Choice of triple generation. More...

enum class  TripleReduction { on , off }
Switches immediate triple dropping. More...

enum class  WinCalculation { absolute , relative }
Choice of objective function. More...

## Public Member Functions

MinSteinerTreeZelikovsky (WinCalculation wc=WinCalculation::absolute, TripleGeneration tg=TripleGeneration::voronoi, SaveCalculation sc=SaveCalculation::hybrid, TripleReduction tr=TripleReduction::on, Pass pass=Pass::multi)

virtual ~MinSteinerTreeZelikovsky ()

virtualcall (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree) override
Calls the Steiner tree algorithm for nontrivial cases but handles trivial cases directly.

void forceAPSP (bool force=true)
For the 3-restricted case, it is sufficient to compute an SSSP from every terminal instead of doing a full APSP.

long numberOfContractedTriples () const
Returns the number of contracted triples.

long numberOfGeneratedTriples () const
Returns the number of generated triples.

long numberOfTripleLookUps () const
Returns the number of triple lookups during execution time.

Pass pass () const
Returns type of pass currently in use.

void pass (Pass p)
Sets type of pass.

SaveCalculation saveCalculation () const
Returns type of save calculation currently in use.

void saveCalculation (SaveCalculation sv)
Sets type of save calculation.

TripleGeneration tripleGeneration () const
Returns type of triple generation currently in use.

void tripleGeneration (TripleGeneration tg)
Sets type of triple generation.

TripleReduction tripleReduction () const
Returns type of triple reduction currently in use.

void tripleReduction (TripleReduction tr)
Sets type of triple reduction.

WinCalculation winCalculation () const
Returns type of gain calculation currently in use.

void winCalculation (WinCalculation wc)
Sets type of gain calculation.

Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
virtual ~MinSteinerTreeModule ()
Do nothing on destruction.

## Protected Member Functions

double calcWin (double gain, T cost) const
Calculate the win.

void computeDistanceMatrix ()
Computes the distance matrix for the original graph.

virtualcomputeSteinerTree (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree) override
Builds a minimum Steiner tree given a weighted graph and a list of terminals.

void contractTriple (const Triple< T > &triple, Save< T > &save, NodeArray< bool > &isNewTerminal)
Contracts a triple and updates the save data structure.

bool findBestTripleForCenter (node center, const Save< T > &save, Triple< T > &maxTriple) const
Find the best triple for a given nonterminal center.

void generateInitialTerminalSpanningTree (EdgeWeightedGraphCopy< T > &steinerTree)

void generateTriple (node u, node v, node w, node center, const T &minCost, const Save< T > &save)
Add a found triple to the triples list.

void generateTriples (const Save< T > &save)
Generates triples according to the chosen option.

void generateTriples (const Save< T > &save, const steiner_tree::Full3ComponentGeneratorModule< T > &fcg)
Generates triples using the given full 3-component generator.

void multiPass (Save< T > &save, NodeArray< bool > &isNewTerminal)
Contraction phase for the original version of the algorithm.

void onePass (Save< T > &save, NodeArray< bool > &isNewTerminal)
Contraction phase for the one pass heuristic.

void tripleOnDemand (Save< T > &save, NodeArray< bool > &isNewTerminal)
Contraction phase for algorithm generating triples on demand.

## Private Attributes

NodeArray< NodeArray< T > > m_distance
The distance matrix.

const NodeArray< bool > * m_isTerminal
Incidence vector for terminal nodes.

const EdgeWeightedGraph< T > * m_originalGraph
The original edge-weighted graph.

Pass m_pass
Chosen option for pass.

NodeArray< NodeArray< edge > > m_pred
The predecessor matrix.

SaveCalculation m_saveCalculation
Chosen option for save calculation.

bool m_ssspDistances
True iff we only compute SSSP from terminals instead of APSP for full component construction.

const List< node > * m_terminals
List of terminal nodes.

TripleGeneration m_tripleGeneration
Chosen option for triple generation.

long m_tripleLookUps
Number of triple lookups.

TripleReduction m_tripleReduction
Chosen option for triple reduction.

List< Triple< T > > m_triples
The list of triples during the algorithm.

long m_triplesContracted
Number of contracted triples.

long m_triplesGenerated
Number of generated triples.

WinCalculation m_winCalculation
Chosen option for gain calculation.

Static Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
static void getNonterminals (ArrayBuffer< node > &nonterminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
Generates a list (as ArrayBuffer<node>) of all nonterminals.

static void getTerminals (List< node > &terminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
Generates a list (as List<node>) of all terminals.

static bool isQuasiBipartite (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
Checks in O(n + m) time if a given Steiner tree problem instance is quasi-bipartite.

static bool isSteinerTree (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const EdgeWeightedGraphCopy< T > &steinerTree)
Checks in O(n) time if a given tree is acually a Steiner Tree.

static void sortTerminals (List< node > &terminals)
Sort terminals by index.

staticpruneAllDanglingSteinerPaths (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
Prunes nonterminal leaves and their paths to terminal or branching nodes.

staticpruneDanglingSteinerPathFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, node start)
Prunes the dangling Steiner path beginning at a given nonterminal leaf only.

staticpruneDanglingSteinerPathsFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const List< node > &start)
Prunes dangling Steiner paths beginning at given nonterminal leaves only.

staticremoveCyclesFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
Remove remaining cycles from a Steiner "almost" tree.

static void singleSourceShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &isTerminal, NodeArray< T > &distance, NodeArray< edge > &pred)
Modified single-source-shortest-paths (Dijkstra) with heuristic to prefer paths over terminals.

static void singleSourceShortestPathsStandard (const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &, NodeArray< T > &distance, NodeArray< edge > &pred)
Standard single-source-shortest-paths algoritm (Dijkstra)

static void singleSourceShortestPaths (const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &isTerminal, NodeArray< T > &distance, NodeArray< edge > &pred)
The default single-source-shortest-paths algorithm.

static void allTerminalShortestPathsStandard (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Runs singleSourceShortestPathsStandard from all terminals.

static void allTerminalShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Runs singleSourceShortestPathsPreferringTerminals from all terminals.

static void allTerminalShortestPaths (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc=singleSourceShortestPaths)
Runs a given (or the default) single-source-shortest-paths function from all terminals.

static void allNodeShortestPathsStandard (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Runs singleSourceShortestPathsStandard from all nodes.

static void allNodeShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Runs singleSourceShortestPathsPreferringTerminals from all nodes.

static void allNodeShortestPaths (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc=singleSourceShortestPaths)
Runs a given (or the default) single-source-shortest-paths function from all nodes.

static void allPairShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Modified all-pair-shortest-paths algorithm (Floyd-Warshall) with heuristic to prefer paths over terminals.

static void allPairShortestPathsStandard (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Standard all-pair-shortest-paths algorithm (Floyd-Warshall)

static void allPairShortestPaths (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
The default all-pair-shortest-paths algorithm.

static void drawSVG (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const EdgeWeightedGraphCopy< T > &steinerTree, const char *filename)
Writes an SVG file of a minimum Steiner tree in the original graph.

static void drawSVG (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const char *filename)
Writes an SVG file of the instance graph.

static void drawSteinerTreeSVG (const EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const char *filename)
Writes a SVG that shows only the given Steiner tree.

## Detailed Description

template<typename T>
class ogdf::MinSteinerTreeZelikovsky< T >

This class implements the 11/6-approximation algorithm by Zelikovsky for the minimum Steiner tree problem along with variants and practical improvements.

This implementation is based on:

(A. Zelikovsky, An 11/6-Approximation Algorithm for the Network Steiner Problem, Algorithmica, volume 9, number 5, pages 463-470, Springer, 1993)

(A. Zelikovsky, A faster approximation algorithm for the Steiner problem in graphs, Information Processing Letters, volume 46, number 2, pages 79-83, 1993)

(A. Zelikovsky, Better approximation bound for the network and euclidean Steiner tree problems, Technical Report, 2006)

Definition at line 66 of file MinSteinerTreeZelikovsky.h.

## ◆ Save

template<typename T >
template<typename TYPE >
 using ogdf::MinSteinerTreeZelikovsky< T >::Save = steiner_tree::Save

Definition at line 69 of file MinSteinerTreeZelikovsky.h.

## ◆ Triple

template<typename T >
template<typename TYPE >
 using ogdf::MinSteinerTreeZelikovsky< T >::Triple = steiner_tree::Triple

Definition at line 71 of file MinSteinerTreeZelikovsky.h.

## ◆ Pass

template<typename T >
 strong

Enables a heuristic version (for TG exhaustive and voronoi only)

Enumerator
one

heuristic: evaluate all triples, sort them descending by gain, traverse sorted triples once, contract when possible

multi

normal, greedy version

Definition at line 110 of file MinSteinerTreeZelikovsky.h.

## ◆ SaveCalculation

template<typename T >
 strong

Different methods for obtaining save edges.

Enumerator
staticEnum

Stores explicitly the save edge for every pair of terminals. Needs O(n^2) space but has fast query times.

staticLCATree

Builds a "weight tree" (save edges are inner nodes, terminals are leaves and searches save edges via LCA calculation of two nodes.

dynamicLCATree

Same as staticLCATree but each time a triple has been contracted the "weight tree" is updated dynamically rather than completely new from scratch. Has the fastest update time.

hybrid

Uses staticEnum for the triple generation phase (many queries) and dynamicLCATree during the contraction phase (few updates)

Definition at line 93 of file MinSteinerTreeZelikovsky.h.

## ◆ TripleGeneration

template<typename T >
 strong

Choice of triple generation.

Enumerator
exhaustive

try all possibilities

voronoi

use voronoi regions

ondemand

generate triples "on the fly", only usable with WinCalculation::absolute

Definition at line 80 of file MinSteinerTreeZelikovsky.h.

## ◆ TripleReduction

template<typename T >
 strong

Switches immediate triple dropping.

Enumerator
on

removes triples as soon as their gain is known to be non positive

off

keeps triples all the time

Definition at line 87 of file MinSteinerTreeZelikovsky.h.

## ◆ WinCalculation

template<typename T >
 strong

Choice of objective function.

Enumerator
absolute

win=gain-cost

relative

win=gain/cost

Definition at line 74 of file MinSteinerTreeZelikovsky.h.

## ◆ MinSteinerTreeZelikovsky()

template<typename T >
 ogdf::MinSteinerTreeZelikovsky< T >::MinSteinerTreeZelikovsky ( WinCalculation wc = WinCalculation::absolute, TripleGeneration tg = TripleGeneration::voronoi, SaveCalculation sc = SaveCalculation::hybrid, TripleReduction tr = TripleReduction::on, Pass pass = Pass::multi )
inline

Definition at line 118 of file MinSteinerTreeZelikovsky.h.

## ◆ ~MinSteinerTreeZelikovsky()

template<typename T >
 virtual ogdf::MinSteinerTreeZelikovsky< T >::~MinSteinerTreeZelikovsky ( )
inlinevirtual

Definition at line 129 of file MinSteinerTreeZelikovsky.h.

## ◆ calcWin()

template<typename T >
 double ogdf::MinSteinerTreeZelikovsky< T >::calcWin ( double gain, T cost ) const
inlineprotected

Calculate the win.

Definition at line 354 of file MinSteinerTreeZelikovsky.h.

## ◆ call()

template<typename T >
 virtual T ogdf::MinSteinerTreeZelikovsky< T >::call ( const EdgeWeightedGraph< T > & G, const List< node > & terminals, const NodeArray< bool > & isTerminal, EdgeWeightedGraphCopy< T > *& finalSteinerTree )
inlineoverridevirtual

Calls the Steiner tree algorithm for nontrivial cases but handles trivial cases directly.

Parameters
 G The weighted input graph terminals The list of terminal nodes isTerminal A bool array of terminals finalSteinerTree The final Steiner tree
Returns
The total cost of the final Steiner tree

Reimplemented from ogdf::MinSteinerTreeModule< T >.

Definition at line 131 of file MinSteinerTreeZelikovsky.h.

## ◆ computeDistanceMatrix()

template<typename T >
 void ogdf::MinSteinerTreeZelikovsky< T >::computeDistanceMatrix ( )
protected

Computes the distance matrix for the original graph.

Definition at line 469 of file MinSteinerTreeZelikovsky.h.

## ◆ computeSteinerTree()

template<typename T >
 T ogdf::MinSteinerTreeZelikovsky< T >::computeSteinerTree ( const EdgeWeightedGraph< T > & G, const List< node > & terminals, const NodeArray< bool > & isTerminal, EdgeWeightedGraphCopy< T > *& finalSteinerTree )
overrideprotectedvirtual

Builds a minimum Steiner tree given a weighted graph and a list of terminals.

MinSteinerTreeModule::call
Parameters
 G The weighted input graph terminals The list of terminal nodes isTerminal A bool array of terminals finalSteinerTree The final Steiner tree
Returns
The objective value (sum of edge costs) of the final Steiner tree

Implements ogdf::MinSteinerTreeModule< T >.

Definition at line 400 of file MinSteinerTreeZelikovsky.h.

## ◆ contractTriple()

template<typename T >
 void ogdf::MinSteinerTreeZelikovsky< T >::contractTriple ( const Triple< T > & triple, Save< T > & save, NodeArray< bool > & isNewTerminal )
inlineprotected

Contracts a triple and updates the save data structure.

Parameters
 triple triple to be contracted save save data structure isNewTerminal true for nodes to be interpreted as terminals

Definition at line 252 of file MinSteinerTreeZelikovsky.h.

## ◆ findBestTripleForCenter()

template<typename T >
 bool ogdf::MinSteinerTreeZelikovsky< T >::findBestTripleForCenter ( node center, const Save< T > & save, Triple< T > & maxTriple ) const
inlineprotected

Find the best triple for a given nonterminal center.

Parameters
 center the center node we want to find a better triple for save save data structure maxTriple the improved triple (output parameter)
Returns
True iff maxTriple is updated

Definition at line 272 of file MinSteinerTreeZelikovsky.h.

## ◆ forceAPSP()

template<typename T >
 void ogdf::MinSteinerTreeZelikovsky< T >::forceAPSP ( bool force = true )
inline

For the 3-restricted case, it is sufficient to compute an SSSP from every terminal instead of doing a full APSP.

In case a full APSP is faster, use this method.

Parameters
 force True to force APSP instead of SSSP.

Definition at line 144 of file MinSteinerTreeZelikovsky.h.

## ◆ generateInitialTerminalSpanningTree()

template<typename T >
 void ogdf::MinSteinerTreeZelikovsky< T >::generateInitialTerminalSpanningTree ( EdgeWeightedGraphCopy< T > & steinerTree )
inlineprotected

Definition at line 364 of file MinSteinerTreeZelikovsky.h.

## ◆ generateTriple()

template<typename T >
 void ogdf::MinSteinerTreeZelikovsky< T >::generateTriple ( node u, node v, node w, node center, const T & minCost, const Save< T > & save )
inlineprotected

Add a found triple to the triples list.

(Just a helper to avoid code duplication.)

Definition at line 205 of file MinSteinerTreeZelikovsky.h.

## ◆ generateTriples() [1/2]

template<typename T >
 void ogdf::MinSteinerTreeZelikovsky< T >::generateTriples ( const Save< T > & save )
inlineprotected

Generates triples according to the chosen option.

TripleGeneration
Parameters
 save data structure for calculation save edges

Definition at line 234 of file MinSteinerTreeZelikovsky.h.

## ◆ generateTriples() [2/2]

template<typename T >
 void ogdf::MinSteinerTreeZelikovsky< T >::generateTriples ( const Save< T > & save, const steiner_tree::Full3ComponentGeneratorModule< T > & fcg )
inlineprotected

Generates triples using the given full 3-component generator.

Parameters
 save data structure for calculation save edges fcg the chosen full 3-component generator

Definition at line 222 of file MinSteinerTreeZelikovsky.h.

## ◆ multiPass()

template<typename T >
 void ogdf::MinSteinerTreeZelikovsky< T >::multiPass ( Save< T > & save, NodeArray< bool > & isNewTerminal )
protected

Contraction phase for the original version of the algorithm.

MinSteinerTreeZelikovsky::multi
Parameters
 save save data structure isNewTerminal true for nodes to be interpreted as terminals

Definition at line 512 of file MinSteinerTreeZelikovsky.h.

## ◆ numberOfContractedTriples()

template<typename T >
 long ogdf::MinSteinerTreeZelikovsky< T >::numberOfContractedTriples ( ) const
inline

Returns the number of contracted triples.

Definition at line 180 of file MinSteinerTreeZelikovsky.h.

## ◆ numberOfGeneratedTriples()

template<typename T >
 long ogdf::MinSteinerTreeZelikovsky< T >::numberOfGeneratedTriples ( ) const
inline

Returns the number of generated triples.

Definition at line 177 of file MinSteinerTreeZelikovsky.h.

## ◆ numberOfTripleLookUps()

template<typename T >
 long ogdf::MinSteinerTreeZelikovsky< T >::numberOfTripleLookUps ( ) const
inline

Returns the number of triple lookups during execution time.

Definition at line 183 of file MinSteinerTreeZelikovsky.h.

## ◆ onePass()

template<typename T >
 void ogdf::MinSteinerTreeZelikovsky< T >::onePass ( Save< T > & save, NodeArray< bool > & isNewTerminal )
protected

Contraction phase for the one pass heuristic.

MinSteinerTreeZelikovsky::one
Parameters
 save save data structure isNewTerminal true for nodes to be interpreted as terminals

Definition at line 499 of file MinSteinerTreeZelikovsky.h.

## ◆ pass() [1/2]

template<typename T >
 Pass ogdf::MinSteinerTreeZelikovsky< T >::pass ( ) const
inline

Returns type of pass currently in use.

MinSteinerTreeZelikovsky::Pass

Definition at line 174 of file MinSteinerTreeZelikovsky.h.

## ◆ pass() [2/2]

template<typename T >
 void ogdf::MinSteinerTreeZelikovsky< T >::pass ( Pass p )
inline

Sets type of pass.

MinSteinerTreeZelikovsky::Pass

Definition at line 171 of file MinSteinerTreeZelikovsky.h.

## ◆ saveCalculation() [1/2]

template<typename T >
 SaveCalculation ogdf::MinSteinerTreeZelikovsky< T >::saveCalculation ( ) const
inline

Returns type of save calculation currently in use.

MinSteinerTreeZelikovsky::SaveCalculation

Definition at line 168 of file MinSteinerTreeZelikovsky.h.

## ◆ saveCalculation() [2/2]

template<typename T >
 void ogdf::MinSteinerTreeZelikovsky< T >::saveCalculation ( SaveCalculation sv )
inline

Sets type of save calculation.

MinSteinerTreeZelikovsky::SaveCalculation

Definition at line 165 of file MinSteinerTreeZelikovsky.h.

## ◆ tripleGeneration() [1/2]

template<typename T >
 TripleGeneration ogdf::MinSteinerTreeZelikovsky< T >::tripleGeneration ( ) const
inline

Returns type of triple generation currently in use.

MinSteinerTreeZelikovsky::TripleGeneration

Definition at line 156 of file MinSteinerTreeZelikovsky.h.

## ◆ tripleGeneration() [2/2]

template<typename T >
 void ogdf::MinSteinerTreeZelikovsky< T >::tripleGeneration ( TripleGeneration tg )
inline

Sets type of triple generation.

MinSteinerTreeZelikovsky::TripleGeneration

Definition at line 153 of file MinSteinerTreeZelikovsky.h.

## ◆ tripleOnDemand()

template<typename T >
 void ogdf::MinSteinerTreeZelikovsky< T >::tripleOnDemand ( Save< T > & save, NodeArray< bool > & isNewTerminal )
protected

Contraction phase for algorithm generating triples on demand.

MinSteinerTreeZelikovsky::ondemand
Parameters
 save save data structure isNewTerminal true for nodes to be interpreted as terminals

Definition at line 480 of file MinSteinerTreeZelikovsky.h.

## ◆ tripleReduction() [1/2]

template<typename T >
 TripleReduction ogdf::MinSteinerTreeZelikovsky< T >::tripleReduction ( ) const
inline

Returns type of triple reduction currently in use.

MinSteinerTreeZelikovsky::TripleReduction

Definition at line 162 of file MinSteinerTreeZelikovsky.h.

## ◆ tripleReduction() [2/2]

template<typename T >
 void ogdf::MinSteinerTreeZelikovsky< T >::tripleReduction ( TripleReduction tr )
inline

Sets type of triple reduction.

MinSteinerTreeZelikovsky::TripleReduction

Definition at line 159 of file MinSteinerTreeZelikovsky.h.

## ◆ winCalculation() [1/2]

template<typename T >
 WinCalculation ogdf::MinSteinerTreeZelikovsky< T >::winCalculation ( ) const
inline

Returns type of gain calculation currently in use.

MinSteinerTreeZelikovsky::WinCalculation

Definition at line 150 of file MinSteinerTreeZelikovsky.h.

## ◆ winCalculation() [2/2]

template<typename T >
 void ogdf::MinSteinerTreeZelikovsky< T >::winCalculation ( WinCalculation wc )
inline

Sets type of gain calculation.

MinSteinerTreeZelikovsky::WinCalculation

Definition at line 147 of file MinSteinerTreeZelikovsky.h.

## ◆ m_distance

template<typename T >
 NodeArray > ogdf::MinSteinerTreeZelikovsky< T >::m_distance
private

The distance matrix.

Definition at line 390 of file MinSteinerTreeZelikovsky.h.

## ◆ m_isTerminal

template<typename T >
 const NodeArray* ogdf::MinSteinerTreeZelikovsky< T >::m_isTerminal
private

Incidence vector for terminal nodes.

Definition at line 388 of file MinSteinerTreeZelikovsky.h.

## ◆ m_originalGraph

template<typename T >
 const EdgeWeightedGraph* ogdf::MinSteinerTreeZelikovsky< T >::m_originalGraph
private

The original edge-weighted graph.

Definition at line 387 of file MinSteinerTreeZelikovsky.h.

## ◆ m_pass

template<typename T >
 Pass ogdf::MinSteinerTreeZelikovsky< T >::m_pass
private

Chosen option for pass.

Pass

Definition at line 384 of file MinSteinerTreeZelikovsky.h.

## ◆ m_pred

template<typename T >
 NodeArray > ogdf::MinSteinerTreeZelikovsky< T >::m_pred
private

The predecessor matrix.

Definition at line 391 of file MinSteinerTreeZelikovsky.h.

## ◆ m_saveCalculation

template<typename T >
 SaveCalculation ogdf::MinSteinerTreeZelikovsky< T >::m_saveCalculation
private

Chosen option for save calculation.

SaveCalculation

Definition at line 382 of file MinSteinerTreeZelikovsky.h.

## ◆ m_ssspDistances

template<typename T >
 bool ogdf::MinSteinerTreeZelikovsky< T >::m_ssspDistances
private

True iff we only compute SSSP from terminals instead of APSP for full component construction.

Definition at line 385 of file MinSteinerTreeZelikovsky.h.

## ◆ m_terminals

template<typename T >
 const List* ogdf::MinSteinerTreeZelikovsky< T >::m_terminals
private

List of terminal nodes.

Definition at line 389 of file MinSteinerTreeZelikovsky.h.

## ◆ m_tripleGeneration

template<typename T >
 TripleGeneration ogdf::MinSteinerTreeZelikovsky< T >::m_tripleGeneration
private

Chosen option for triple generation.

TripleGeneration

Definition at line 381 of file MinSteinerTreeZelikovsky.h.

## ◆ m_tripleLookUps

template<typename T >
 long ogdf::MinSteinerTreeZelikovsky< T >::m_tripleLookUps
private

Number of triple lookups.

Definition at line 396 of file MinSteinerTreeZelikovsky.h.

## ◆ m_tripleReduction

template<typename T >
 TripleReduction ogdf::MinSteinerTreeZelikovsky< T >::m_tripleReduction
private

Chosen option for triple reduction.

TripleReduction

Definition at line 383 of file MinSteinerTreeZelikovsky.h.

## ◆ m_triples

template<typename T >
 List > ogdf::MinSteinerTreeZelikovsky< T >::m_triples
private

The list of triples during the algorithm.

Definition at line 392 of file MinSteinerTreeZelikovsky.h.

## ◆ m_triplesContracted

template<typename T >
 long ogdf::MinSteinerTreeZelikovsky< T >::m_triplesContracted
private

Number of contracted triples.

Definition at line 395 of file MinSteinerTreeZelikovsky.h.

## ◆ m_triplesGenerated

template<typename T >
 long ogdf::MinSteinerTreeZelikovsky< T >::m_triplesGenerated
private

Number of generated triples.

Definition at line 394 of file MinSteinerTreeZelikovsky.h.

## ◆ m_winCalculation

template<typename T >
 WinCalculation ogdf::MinSteinerTreeZelikovsky< T >::m_winCalculation
private

Chosen option for gain calculation.