Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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. More...
 
virtual T call (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. More...
 

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

Protected Member Functions

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

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. More...
 
static void apspInit (const EdgeWeightedGraph< T > &G, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
 Common initialization routine for APSP algorithms. More...
 
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. More...
 
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. More...
 

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
TThe type of the edge costs of the Steiner tree instance

Definition at line 58 of file MinSteinerTreeModule.h.

Constructor & Destructor Documentation

◆ ~MinSteinerTreeModule()

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

Do nothing on destruction.

Definition at line 61 of file MinSteinerTreeModule.h.

Member Function Documentation

◆ 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 372 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 207 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 197 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 187 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.

See also
allPairShortestPathsPreferringTerminals, allPairShortestPathsStandard

Definition at line 233 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
GInput graph
isTerminalIncidence vector indicating terminal nodes
distanceDistance matrix result
predResulting shortest path such that pred[s][t] contains last edge of an s-t-path

Definition at line 602 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 646 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 176 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 165 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 154 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 630 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 356 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
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 in ogdf::MinSteinerTreePrimalDual< T >, and ogdf::MinSteinerTreeZelikovsky< T >.

Definition at line 389 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

◆ 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
steinerTreeThe Steiner tree to be drawn
isTerminalIncidence vector indicating terminal nodes
filenameThe name of the output file

Definition at line 665 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
GThe weighted graph instance
isTerminalIncidence vector indicating terminal nodes
filenameThe name of the output file

Definition at line 262 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
GThe original weighted graph
isTerminalIncidence vector indicating terminal nodes
steinerTreeThe Steiner tree of the given graph
filenameThe name of the output file

Definition at line 708 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
nonterminalsThe returned list (nonterminals are appended)
GThe weighted input graph
isTerminalA 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
terminalsThe returned list (terminals are appended)
GThe weighted input graph
isTerminalA bool array of terminals

Definition at line 306 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
GThe original graph
isTerminalA bool array of terminals
Returns
true iff the given Steiner tree problem instance is quasi-bipartite

Definition at line 458 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
GThe original graph
terminalsThe list of terminal nodes
isTerminalA bool array of terminals
steinerTreeThe Steiner tree to be checked
Returns
true iff the given Steiner tree is actually one, false otherwise

Definition at line 427 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
steinerTreeThe given Steiner tree
isTerminalIncidence vector indicating terminal nodes
Returns
The total cost of the removed edges (achieved improvement)

Definition at line 500 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
steinerTreeThe given Steiner tree
isTerminalIncidence vector indicating terminals
startA nonterminal leaf to start pruning at
Returns
The total cost of the removed edges (achieved improvement)

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

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

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

See also
singleSourceShortestPathsPreferringTerminals, singleSourceShortestPathsStandard

Definition at line 144 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
GInput graph
sourceStart terminal
isTerminalIncidence vector indicating terminal nodes
distanceDistance matrix result
predResulting shortest path such that pred[s][t] contains last edge of an s-t-path

Definition at line 555 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 137 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 316 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 542 of file MinSteinerTreeModule.h.


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