Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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  Pass { Pass::one, Pass::multi }
 Enables a heuristic version (for TG exhaustive and voronoi only) More...
 
template<typename TYPE >
using Save = steiner_tree::Save< TYPE >
 
enum  SaveCalculation { SaveCalculation::staticEnum, SaveCalculation::staticLCATree, SaveCalculation::dynamicLCATree, SaveCalculation::hybrid }
 Different methods for obtaining save edges. More...
 
template<typename TYPE >
using Triple = steiner_tree::Triple< TYPE >
 
enum  TripleGeneration { TripleGeneration::exhaustive, TripleGeneration::voronoi, TripleGeneration::ondemand }
 Choice of triple generation. More...
 
enum  TripleReduction { TripleReduction::on, TripleReduction::off }
 Switches immediate triple dropping. More...
 
enum  WinCalculation { WinCalculation::absolute, WinCalculation::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 ()
 
virtual T call (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. More...
 
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. More...
 
long numberOfContractedTriples () const
 Returns the number of contracted triples. More...
 
long numberOfGeneratedTriples () const
 Returns the number of generated triples. More...
 
long numberOfTripleLookUps () const
 Returns the number of triple lookups during execution time. More...
 
Pass pass () const
 Returns type of pass currently in use. More...
 
void pass (Pass p)
 Sets type of pass. More...
 
SaveCalculation saveCalculation () const
 Returns type of save calculation currently in use. More...
 
void saveCalculation (SaveCalculation sv)
 Sets type of save calculation. More...
 
TripleGeneration tripleGeneration () const
 Returns type of triple generation currently in use. More...
 
void tripleGeneration (TripleGeneration tg)
 Sets type of triple generation. More...
 
TripleReduction tripleReduction () const
 Returns type of triple reduction currently in use. More...
 
void tripleReduction (TripleReduction tr)
 Sets type of triple reduction. More...
 
WinCalculation winCalculation () const
 Returns type of gain calculation currently in use. More...
 
void winCalculation (WinCalculation wc)
 Sets type of gain calculation. More...
 
- Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
virtual ~MinSteinerTreeModule ()
 Do nothing on destruction. More...
 

Protected Member Functions

double calcWin (double gain, T cost) const
 Calculate the win. More...
 
void computeDistanceMatrix ()
 Computes the distance matrix for the original graph. More...
 
virtual T computeSteinerTree (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. More...
 
void contractTriple (const Triple< T > &triple, Save< T > &save, NodeArray< bool > &isNewTerminal)
 Contracts a triple and updates the save data structure. More...
 
bool findBestTripleForCenter (node center, const Save< T > &save, Triple< T > &maxTriple) const
 Find the best triple for a given nonterminal center. More...
 
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. More...
 
void generateTriples (const Save< T > &save)
 Generates triples according to the chosen option. More...
 
void generateTriples (const Save< T > &save, const steiner_tree::Full3ComponentGeneratorModule< T > &fcg)
 Generates triples using the given full 3-component generator. More...
 
void multiPass (Save< T > &save, NodeArray< bool > &isNewTerminal)
 Contraction phase for the original version of the algorithm. More...
 
void onePass (Save< T > &save, NodeArray< bool > &isNewTerminal)
 Contraction phase for the one pass heuristic. More...
 
void tripleOnDemand (Save< T > &save, NodeArray< bool > &isNewTerminal)
 Contraction phase for algorithm generating triples on demand. More...
 

Private Attributes

NodeArray< NodeArray< T > > m_distance
 The distance matrix. More...
 
const NodeArray< bool > * m_isTerminal
 Incidence vector for terminal nodes. More...
 
const EdgeWeightedGraph< T > * m_originalGraph
 The original edge-weighted graph. More...
 
Pass m_pass
 Chosen option for pass. More...
 
NodeArray< NodeArray< edge > > m_pred
 The predecessor matrix. More...
 
SaveCalculation m_saveCalculation
 Chosen option for save calculation. More...
 
bool m_ssspDistances
 True iff we only compute SSSP from terminals instead of APSP for full component construction. More...
 
const List< node > * m_terminals
 List of terminal nodes. More...
 
TripleGeneration m_tripleGeneration
 Chosen option for triple generation. More...
 
long m_tripleLookUps
 Number of triple lookups. More...
 
TripleReduction m_tripleReduction
 Chosen option for triple reduction. More...
 
List< Triple< T > > m_triples
 The list of triples during the algorithm. More...
 
long m_triplesContracted
 Number of contracted triples. More...
 
long m_triplesGenerated
 Number of generated triples. More...
 
WinCalculation m_winCalculation
 Chosen option for gain calculation. More...
 

Additional Inherited Members

- 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. More...
 
static void getTerminals (List< node > &terminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
 Generates a list (as List<node>) of all terminals. More...
 
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. More...
 
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. More...
 
static void sortTerminals (List< node > &terminals)
 Sort terminals by index. More...
 
static T pruneAllDanglingSteinerPaths (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
 Prunes nonterminal leaves and their paths to terminal or branching nodes. More...
 
static T pruneDanglingSteinerPathFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, node start)
 Prunes the dangling Steiner path beginning at a given nonterminal leaf only. More...
 
static T pruneDanglingSteinerPathsFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const List< node > &start)
 Prunes dangling Steiner paths beginning at given nonterminal leaves only. More...
 
static T removeCyclesFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
 Remove remaining cycles from a Steiner "almost" tree. More...
 
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. More...
 
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) More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
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) More...
 
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. More...
 
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. More...
 
static void drawSVG (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const char *filename)
 Writes an SVG file of the instance graph. More...
 
static void drawSteinerTreeSVG (const EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const char *filename)
 Writes a SVG that shows only the given Steiner tree. More...
 

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.

Member Typedef Documentation

◆ Save

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

Definition at line 68 of file MinSteinerTreeZelikovsky.h.

◆ Triple

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

Definition at line 69 of file MinSteinerTreeZelikovsky.h.

Member Enumeration Documentation

◆ Pass

template<typename T >
enum ogdf::MinSteinerTreeZelikovsky::Pass
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 108 of file MinSteinerTreeZelikovsky.h.

◆ SaveCalculation

template<typename T >
enum ogdf::MinSteinerTreeZelikovsky::SaveCalculation
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 91 of file MinSteinerTreeZelikovsky.h.

◆ TripleGeneration

template<typename T >
enum ogdf::MinSteinerTreeZelikovsky::TripleGeneration
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 78 of file MinSteinerTreeZelikovsky.h.

◆ TripleReduction

template<typename T >
enum ogdf::MinSteinerTreeZelikovsky::TripleReduction
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 85 of file MinSteinerTreeZelikovsky.h.

◆ WinCalculation

template<typename T >
enum ogdf::MinSteinerTreeZelikovsky::WinCalculation
strong

Choice of objective function.

Enumerator
absolute 

win=gain-cost

relative 

win=gain/cost

Definition at line 72 of file MinSteinerTreeZelikovsky.h.

Constructor & Destructor Documentation

◆ MinSteinerTreeZelikovsky()

◆ ~MinSteinerTreeZelikovsky()

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

Definition at line 130 of file MinSteinerTreeZelikovsky.h.

Member Function Documentation

◆ calcWin()

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

Calculate the win.

Definition at line 405 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
GThe weighted input graph
terminalsThe list of terminal nodes
isTerminalA bool array of terminals
finalSteinerTreeThe final Steiner tree
Returns
The total cost of the final Steiner tree

Reimplemented from ogdf::MinSteinerTreeModule< T >.

Definition at line 132 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 522 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.

See also
MinSteinerTreeModule::call
Parameters
GThe weighted input graph
terminalsThe list of terminal nodes
isTerminalA bool array of terminals
finalSteinerTreeThe final Steiner tree
Returns
The objective value (sum of edge costs) of the final Steiner tree

Implements ogdf::MinSteinerTreeModule< T >.

Definition at line 454 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
tripletriple to be contracted
savesave data structure
isNewTerminaltrue for nodes to be interpreted as terminals

Definition at line 299 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
centerthe center node we want to find a better triple for
savesave data structure
maxTriplethe improved triple (output parameter)
Returns
True iff maxTriple is updated

Definition at line 320 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
forceTrue to force APSP instead of SSSP.

Definition at line 145 of file MinSteinerTreeZelikovsky.h.

◆ generateInitialTerminalSpanningTree()

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

Definition at line 416 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 250 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.

See also
TripleGeneration
Parameters
savedata structure for calculation save edges

Definition at line 280 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
savedata structure for calculation save edges
fcgthe chosen full 3-component generator

Definition at line 268 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.

See also
MinSteinerTreeZelikovsky::multi
Parameters
savesave data structure
isNewTerminaltrue for nodes to be interpreted as terminals

Definition at line 567 of file MinSteinerTreeZelikovsky.h.

◆ numberOfContractedTriples()

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

Returns the number of contracted triples.

Definition at line 216 of file MinSteinerTreeZelikovsky.h.

◆ numberOfGeneratedTriples()

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

Returns the number of generated triples.

Definition at line 210 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 222 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.

See also
MinSteinerTreeZelikovsky::one
Parameters
savesave data structure
isNewTerminaltrue for nodes to be interpreted as terminals

Definition at line 553 of file MinSteinerTreeZelikovsky.h.

◆ pass() [1/2]

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

Returns type of pass currently in use.

See also
MinSteinerTreeZelikovsky::Pass

Definition at line 204 of file MinSteinerTreeZelikovsky.h.

◆ pass() [2/2]

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

Sets type of pass.

See also
MinSteinerTreeZelikovsky::Pass

Definition at line 199 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.

See also
MinSteinerTreeZelikovsky::SaveCalculation

Definition at line 193 of file MinSteinerTreeZelikovsky.h.

◆ saveCalculation() [2/2]

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

Sets type of save calculation.

See also
MinSteinerTreeZelikovsky::SaveCalculation

Definition at line 187 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.

See also
MinSteinerTreeZelikovsky::TripleGeneration

Definition at line 169 of file MinSteinerTreeZelikovsky.h.

◆ tripleGeneration() [2/2]

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

Sets type of triple generation.

See also
MinSteinerTreeZelikovsky::TripleGeneration

Definition at line 163 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.

See also
MinSteinerTreeZelikovsky::ondemand
Parameters
savesave data structure
isNewTerminaltrue for nodes to be interpreted as terminals

Definition at line 532 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.

See also
MinSteinerTreeZelikovsky::TripleReduction

Definition at line 181 of file MinSteinerTreeZelikovsky.h.

◆ tripleReduction() [2/2]

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

Sets type of triple reduction.

See also
MinSteinerTreeZelikovsky::TripleReduction

Definition at line 175 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.

See also
MinSteinerTreeZelikovsky::WinCalculation

Definition at line 157 of file MinSteinerTreeZelikovsky.h.

◆ winCalculation() [2/2]

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

Sets type of gain calculation.

See also
MinSteinerTreeZelikovsky::WinCalculation

Definition at line 151 of file MinSteinerTreeZelikovsky.h.

Member Data Documentation

◆ m_distance

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

The distance matrix.

Definition at line 443 of file MinSteinerTreeZelikovsky.h.

◆ m_isTerminal

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

Incidence vector for terminal nodes.

Definition at line 441 of file MinSteinerTreeZelikovsky.h.

◆ m_originalGraph

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

The original edge-weighted graph.

Definition at line 440 of file MinSteinerTreeZelikovsky.h.

◆ m_pass

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

Chosen option for pass.

See also
Pass

Definition at line 437 of file MinSteinerTreeZelikovsky.h.

◆ m_pred

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

The predecessor matrix.

Definition at line 444 of file MinSteinerTreeZelikovsky.h.

◆ m_saveCalculation

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

Chosen option for save calculation.

See also
SaveCalculation

Definition at line 435 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 438 of file MinSteinerTreeZelikovsky.h.

◆ m_terminals

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

List of terminal nodes.

Definition at line 442 of file MinSteinerTreeZelikovsky.h.

◆ m_tripleGeneration

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

Chosen option for triple generation.

See also
TripleGeneration

Definition at line 434 of file MinSteinerTreeZelikovsky.h.

◆ m_tripleLookUps

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

Number of triple lookups.

Definition at line 449 of file MinSteinerTreeZelikovsky.h.

◆ m_tripleReduction

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

Chosen option for triple reduction.

See also
TripleReduction

Definition at line 436 of file MinSteinerTreeZelikovsky.h.

◆ m_triples

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

The list of triples during the algorithm.

Definition at line 445 of file MinSteinerTreeZelikovsky.h.

◆ m_triplesContracted

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

Number of contracted triples.

Definition at line 448 of file MinSteinerTreeZelikovsky.h.

◆ m_triplesGenerated

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

Number of generated triples.

Definition at line 447 of file MinSteinerTreeZelikovsky.h.

◆ m_winCalculation

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

Chosen option for gain calculation.

See also
WinCalculation

Definition at line 433 of file MinSteinerTreeZelikovsky.h.


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