# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
ogdf::MinSteinerTreeModule< T > Class Template Referenceabstract

Serves as an interface for various methods to compute or approximate minimum Steiner trees on undirected graphs with edge costs. More...

#include <ogdf/graphalg/MinSteinerTreeModule.h>

Inheritance diagram for ogdf::MinSteinerTreeModule< T >:

## Public Member Functions

virtual ~MinSteinerTreeModule ()
Do nothing on destruction.

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

## Static Public Member Functions

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.

Auxiliary post-processing functions
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.

Special SSSP and APSP algorithms used in component-based approximation algorithms
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.

Drawings for debugging
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.

## Protected Member Functions

virtualcomputeSteinerTree (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree)=0
Computes the actual Steiner tree.

## Static Private Member Functions

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

static void apspInit (const EdgeWeightedGraph< T > &G, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Common initialization routine for APSP algorithms.

static void apspInnerLoop (node v, const EdgeWeightedGraph< T > &G, NodeArray< NodeArray< T > > &distance, std::function< void(node, node, T)> func)
The inner loop for APSP algorithm to avoid code duplication.

static void ssspInit (const EdgeWeightedGraph< T > &G, node source, PrioritizedMapQueue< node, T > &queue, NodeArray< T > &distance, NodeArray< edge > &pred)
Common initialization routine for SSSP algorithms.

## Detailed Description

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

Serves as an interface for various methods to compute or approximate minimum Steiner trees on undirected graphs with edge costs.

Furthermore it supplies some auxiliary methods.

Template Parameters
 T The type of the edge costs of the Steiner tree instance

Definition at line 59 of file MinSteinerTreeModule.h.

## ◆ ~MinSteinerTreeModule()

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

Do nothing on destruction.

Definition at line 62 of file MinSteinerTreeModule.h.

## ◆ allNodesByListShortestPaths()

template<typename T >
template<typename NODELIST >
 static void ogdf::MinSteinerTreeModule< T >::allNodesByListShortestPaths ( const EdgeWeightedGraph< T > & G, const List< node > & terminals, const NodeArray< bool > & isTerminal, const NODELIST & nodes, NodeArray< NodeArray< T > > & distance, NodeArray< NodeArray< edge > > & pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc )
inlinestaticprivate

Runs a given (or the default) single-source-shortest-paths function from all nodes.

Definition at line 371 of file MinSteinerTreeModule.h.

## ◆ allNodeShortestPaths()

template<typename T >
 static void ogdf::MinSteinerTreeModule< T >::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 )
inlinestatic

Runs a given (or the default) single-source-shortest-paths function from all nodes.

Definition at line 201 of file MinSteinerTreeModule.h.

## ◆ allNodeShortestPathsPreferringTerminals()

template<typename T >
 static void ogdf::MinSteinerTreeModule< T >::allNodeShortestPathsPreferringTerminals ( const EdgeWeightedGraph< T > & G, const List< node > & terminals, const NodeArray< bool > & isTerminal, NodeArray< NodeArray< T > > & distance, NodeArray< NodeArray< edge > > & pred )
inlinestatic

Runs singleSourceShortestPathsPreferringTerminals from all nodes.

Definition at line 193 of file MinSteinerTreeModule.h.

## ◆ allNodeShortestPathsStandard()

template<typename T >
 static void ogdf::MinSteinerTreeModule< T >::allNodeShortestPathsStandard ( const EdgeWeightedGraph< T > & G, const List< node > & terminals, const NodeArray< bool > & isTerminal, NodeArray< NodeArray< T > > & distance, NodeArray< NodeArray< edge > > & pred )
inlinestatic

Runs singleSourceShortestPathsStandard from all nodes.

Definition at line 185 of file MinSteinerTreeModule.h.

## ◆ allPairShortestPaths()

template<typename T >
 static void ogdf::MinSteinerTreeModule< T >::allPairShortestPaths ( const EdgeWeightedGraph< T > & G, const NodeArray< bool > & isTerminal, NodeArray< NodeArray< T > > & distance, NodeArray< NodeArray< edge > > & pred )
inlinestatic

The default all-pair-shortest-paths algorithm.

allPairShortestPathsPreferringTerminals, allPairShortestPathsStandard

Definition at line 229 of file MinSteinerTreeModule.h.

## ◆ allPairShortestPathsPreferringTerminals()

template<typename T >
 void ogdf::MinSteinerTreeModule< T >::allPairShortestPathsPreferringTerminals ( const EdgeWeightedGraph< T > & G, const NodeArray< bool > & isTerminal, NodeArray< NodeArray< T > > & distance, NodeArray< NodeArray< edge > > & pred )
static

Modified all-pair-shortest-paths algorithm (Floyd-Warshall) with heuristic to prefer paths over terminals.

Parameters
 G Input graph isTerminal Incidence vector indicating terminal nodes distance Distance matrix result pred Resulting shortest path such that pred[s][t] contains last edge of an s-t-path

Definition at line 589 of file MinSteinerTreeModule.h.

## ◆ allPairShortestPathsStandard()

template<typename T >
 void ogdf::MinSteinerTreeModule< T >::allPairShortestPathsStandard ( const EdgeWeightedGraph< T > & G, const NodeArray< bool > & , NodeArray< NodeArray< T > > & distance, NodeArray< NodeArray< edge > > & pred )
static

Standard all-pair-shortest-paths algorithm (Floyd-Warshall)

Definition at line 634 of file MinSteinerTreeModule.h.

## ◆ allTerminalShortestPaths()

template<typename T >
 static void ogdf::MinSteinerTreeModule< T >::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 )
inlinestatic

Runs a given (or the default) single-source-shortest-paths function from all terminals.

Definition at line 175 of file MinSteinerTreeModule.h.

## ◆ allTerminalShortestPathsPreferringTerminals()

template<typename T >
 static void ogdf::MinSteinerTreeModule< T >::allTerminalShortestPathsPreferringTerminals ( const EdgeWeightedGraph< T > & G, const List< node > & terminals, const NodeArray< bool > & isTerminal, NodeArray< NodeArray< T > > & distance, NodeArray< NodeArray< edge > > & pred )
inlinestatic

Runs singleSourceShortestPathsPreferringTerminals from all terminals.

Definition at line 167 of file MinSteinerTreeModule.h.

## ◆ allTerminalShortestPathsStandard()

template<typename T >
 static void ogdf::MinSteinerTreeModule< T >::allTerminalShortestPathsStandard ( const EdgeWeightedGraph< T > & G, const List< node > & terminals, const NodeArray< bool > & isTerminal, NodeArray< NodeArray< T > > & distance, NodeArray< NodeArray< edge > > & pred )
inlinestatic

Runs singleSourceShortestPathsStandard from all terminals.

Definition at line 159 of file MinSteinerTreeModule.h.

## ◆ apspInit()

template<typename T >
 void ogdf::MinSteinerTreeModule< T >::apspInit ( const EdgeWeightedGraph< T > & G, NodeArray< NodeArray< T > > & distance, NodeArray< NodeArray< edge > > & pred )
staticprivate

Common initialization routine for APSP algorithms.

Definition at line 618 of file MinSteinerTreeModule.h.

## ◆ apspInnerLoop()

template<typename T >
 static void ogdf::MinSteinerTreeModule< T >::apspInnerLoop ( node v, const EdgeWeightedGraph< T > & G, NodeArray< NodeArray< T > > & distance, std::function< void(node, node, T)> func )
inlinestaticprivate

The inner loop for APSP algorithm to avoid code duplication.

Definition at line 355 of file MinSteinerTreeModule.h.

## ◆ call()

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

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 in ogdf::MinSteinerTreePrimalDual< T >, and ogdf::MinSteinerTreeZelikovsky< T >.

Definition at line 386 of file MinSteinerTreeModule.h.

## ◆ computeSteinerTree()

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

Computes the actual Steiner tree.

Returns
The total cost of the final Steiner tree

## ◆ drawSteinerTreeSVG()

template<typename T >
 void ogdf::MinSteinerTreeModule< T >::drawSteinerTreeSVG ( const EdgeWeightedGraphCopy< T > & steinerTree, const NodeArray< bool > & isTerminal, const char * filename )
static

Writes a SVG that shows only the given Steiner tree.

Parameters
 steinerTree The Steiner tree to be drawn isTerminal Incidence vector indicating terminal nodes filename The name of the output file

Definition at line 653 of file MinSteinerTreeModule.h.

## ◆ drawSVG() [1/2]

template<typename T >
 static void ogdf::MinSteinerTreeModule< T >::drawSVG ( const EdgeWeightedGraph< T > & G, const NodeArray< bool > & isTerminal, const char * filename )
inlinestatic

Writes an SVG file of the instance graph.

Parameters
 G The weighted graph instance isTerminal Incidence vector indicating terminal nodes filename The name of the output file

Definition at line 260 of file MinSteinerTreeModule.h.

## ◆ drawSVG() [2/2]

template<typename T >
 void ogdf::MinSteinerTreeModule< T >::drawSVG ( const EdgeWeightedGraph< T > & G, const NodeArray< bool > & isTerminal, const EdgeWeightedGraphCopy< T > & steinerTree, const char * filename )
static

Writes an SVG file of a minimum Steiner tree in the original graph.

Parameters
 G The original weighted graph isTerminal Incidence vector indicating terminal nodes steinerTree The Steiner tree of the given graph filename The name of the output file

Definition at line 693 of file MinSteinerTreeModule.h.

## ◆ getNonterminals()

template<typename T >
 static void ogdf::MinSteinerTreeModule< T >::getNonterminals ( ArrayBuffer< node > & nonterminals, const EdgeWeightedGraph< T > & G, const NodeArray< bool > & isTerminal )
inlinestatic

Generates a list (as ArrayBuffer<node>) of all nonterminals.

Parameters
 nonterminals The returned list (nonterminals are appended) G The weighted input graph isTerminal A bool array of terminals

Definition at line 328 of file MinSteinerTreeModule.h.

## ◆ getTerminals()

template<typename T >
 static void ogdf::MinSteinerTreeModule< T >::getTerminals ( List< node > & terminals, const EdgeWeightedGraph< T > & G, const NodeArray< bool > & isTerminal )
inlinestatic

Generates a list (as List<node>) of all terminals.

Parameters
 terminals The returned list (terminals are appended) G The weighted input graph isTerminal A bool array of terminals

Definition at line 307 of file MinSteinerTreeModule.h.

## ◆ isQuasiBipartite()

template<typename T >
 bool ogdf::MinSteinerTreeModule< T >::isQuasiBipartite ( const EdgeWeightedGraph< T > & G, const NodeArray< bool > & isTerminal )
static

Checks in O(n + m) time if a given Steiner tree problem instance is quasi-bipartite.

Parameters
 G The original graph isTerminal A bool array of terminals
Returns
true iff the given Steiner tree problem instance is quasi-bipartite

Definition at line 447 of file MinSteinerTreeModule.h.

## ◆ isSteinerTree()

template<typename T >
 bool ogdf::MinSteinerTreeModule< T >::isSteinerTree ( const EdgeWeightedGraph< T > & G, const List< node > & terminals, const NodeArray< bool > & isTerminal, const EdgeWeightedGraphCopy< T > & steinerTree )
static

Checks in O(n) time if a given tree is acually a Steiner Tree.

Parameters
 G The original graph terminals The list of terminal nodes isTerminal A bool array of terminals steinerTree The Steiner tree to be checked
Returns
true iff the given Steiner tree is actually one, false otherwise

Definition at line 420 of file MinSteinerTreeModule.h.

## ◆ pruneAllDanglingSteinerPaths()

template<typename T >
 T ogdf::MinSteinerTreeModule< T >::pruneAllDanglingSteinerPaths ( EdgeWeightedGraphCopy< T > & steinerTree, const NodeArray< bool > & isTerminal )
static

Prunes nonterminal leaves and their paths to terminal or branching nodes.

Parameters
 steinerTree The given Steiner tree isTerminal Incidence vector indicating terminal nodes
Returns
The total cost of the removed edges (achieved improvement)

Definition at line 488 of file MinSteinerTreeModule.h.

## ◆ pruneDanglingSteinerPathFrom()

template<typename T >
 T ogdf::MinSteinerTreeModule< T >::pruneDanglingSteinerPathFrom ( EdgeWeightedGraphCopy< T > & steinerTree, const NodeArray< bool > & isTerminal, node start )
static

Prunes the dangling Steiner path beginning at a given nonterminal leaf only.

Parameters
 steinerTree The given Steiner tree isTerminal Incidence vector indicating terminals start A nonterminal leaf to start pruning at
Returns
The total cost of the removed edges (achieved improvement)

Definition at line 462 of file MinSteinerTreeModule.h.

## ◆ pruneDanglingSteinerPathsFrom()

template<typename T >
 T ogdf::MinSteinerTreeModule< T >::pruneDanglingSteinerPathsFrom ( EdgeWeightedGraphCopy< T > & steinerTree, const NodeArray< bool > & isTerminal, const List< node > & start )
static

Prunes dangling Steiner paths beginning at given nonterminal leaves only.

pruneDanglingSteinerPathFrom(EdgeWeightedGraphCopy<T> &steinerTree, const NodeArray<bool> &isTerminal, node start)

Definition at line 478 of file MinSteinerTreeModule.h.

## ◆ removeCyclesFrom()

template<typename T >
 T ogdf::MinSteinerTreeModule< T >::removeCyclesFrom ( EdgeWeightedGraphCopy< T > & steinerTree, const NodeArray< bool > & isTerminal )
static

Remove remaining cycles from a Steiner "almost" tree.

Returns
The edge weights of the removed edges (achieved improvement)

Definition at line 501 of file MinSteinerTreeModule.h.

## ◆ singleSourceShortestPaths()

template<typename T >
 static void ogdf::MinSteinerTreeModule< T >::singleSourceShortestPaths ( const EdgeWeightedGraph< T > & G, node source, const NodeArray< bool > & isTerminal, NodeArray< T > & distance, NodeArray< edge > & pred )
inlinestatic

The default single-source-shortest-paths algorithm.

singleSourceShortestPathsPreferringTerminals, singleSourceShortestPathsStandard

Definition at line 149 of file MinSteinerTreeModule.h.

## ◆ singleSourceShortestPathsPreferringTerminals()

template<typename T >
 void ogdf::MinSteinerTreeModule< T >::singleSourceShortestPathsPreferringTerminals ( const EdgeWeightedGraph< T > & G, node source, const NodeArray< bool > & isTerminal, NodeArray< T > & distance, NodeArray< edge > & pred )
static

Modified single-source-shortest-paths (Dijkstra) with heuristic to prefer paths over terminals.

A shortest path over a terminal will mark the nodes that come after that terminal as unreachable by setting the predecessor to nullptr. Nevertheless, the distance will be set correctly.

Parameters
 G Input graph source Start terminal isTerminal Incidence vector indicating terminal nodes distance Distance matrix result pred Resulting shortest path such that pred[s][t] contains last edge of an s-t-path

Definition at line 543 of file MinSteinerTreeModule.h.

## ◆ singleSourceShortestPathsStandard()

template<typename T >
 static void ogdf::MinSteinerTreeModule< T >::singleSourceShortestPathsStandard ( const EdgeWeightedGraph< T > & G, node source, const NodeArray< bool > & , NodeArray< T > & distance, NodeArray< edge > & pred )
inlinestatic

Standard single-source-shortest-paths algoritm (Dijkstra)

Definition at line 141 of file MinSteinerTreeModule.h.

## ◆ sortTerminals()

template<typename T >
 static void ogdf::MinSteinerTreeModule< T >::sortTerminals ( List< node > & terminals )
inlinestatic

Sort terminals by index.

Definition at line 317 of file MinSteinerTreeModule.h.

## ◆ ssspInit()

template<typename T >
 void ogdf::MinSteinerTreeModule< T >::ssspInit ( const EdgeWeightedGraph< T > & G, node source, PrioritizedMapQueue< node, T > & queue, NodeArray< T > & distance, NodeArray< edge > & pred )
staticprivate

Common initialization routine for SSSP algorithms.

Definition at line 530 of file MinSteinerTreeModule.h.

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