Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

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

This class implements the Minimum Steiner Tree 2-approximation algorithm by Kou et al. More...

#include <ogdf/graphalg/MinSteinerTreeKou.h>

+ Inheritance diagram for ogdf::MinSteinerTreeKou< T >:

Public Member Functions

 MinSteinerTreeKou ()
 
virtual ~MinSteinerTreeKou ()
 
- Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
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.
 

Protected Member Functions

void calculateCompleteGraph (const EdgeWeightedGraph< T > &wG, const List< node > &terminals, EdgeArray< List< edge > > &predecessor, EdgeWeightedGraphCopy< T > &completeTerminalGraph)
 Builds a complete terminal 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 insertPath (const List< edge > &ssspPred, EdgeWeightedGraphCopy< T > &finalSteinerTree, const EdgeWeightedGraph< T > &wG)
 Inserts a shortest path corresponding to an edge in the complete terminal graph.
 
void reinsertShortestPaths (const EdgeWeightedGraphCopy< T > &completeTerminalGraph, const EdgeArray< List< edge > > &ssspPred, const NodeArray< edge > &mstPred, EdgeWeightedGraphCopy< T > &finalSteinerTree, const EdgeWeightedGraph< T > &wG)
 Swaps an edge in the complete terminal graph with the corresponding shortest path in the original graph.
 

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.
 
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::MinSteinerTreeKou< T >

This class implements the Minimum Steiner Tree 2-approximation algorithm by Kou et al.

This implementation is based on:

(L. Kou, G. Markowsky, L. Berman, A fast algorithm for Steiner trees, Acta Informatica, volumne 15, number 2, pages 141-145, 1981)

Definition at line 54 of file MinSteinerTreeKou.h.

Constructor & Destructor Documentation

◆ MinSteinerTreeKou()

template<typename T >
ogdf::MinSteinerTreeKou< T >::MinSteinerTreeKou ( )
inline

Definition at line 56 of file MinSteinerTreeKou.h.

◆ ~MinSteinerTreeKou()

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

Definition at line 58 of file MinSteinerTreeKou.h.

Member Function Documentation

◆ calculateCompleteGraph()

template<typename T >
void ogdf::MinSteinerTreeKou< T >::calculateCompleteGraph ( const EdgeWeightedGraph< T > &  wG,
const List< node > &  terminals,
EdgeArray< List< edge > > &  predecessor,
EdgeWeightedGraphCopy< T > &  completeTerminalGraph 
)
protected

Builds a complete terminal graph.

Parameters
wGthe original graph
terminalslist of terminals
predecessorstores for each edge in the complete terminal graph the according path in the original graph
completeTerminalGraphthe resulting complete terminal graph

Definition at line 134 of file MinSteinerTreeKou.h.

◆ computeSteinerTree()

template<typename T >
T ogdf::MinSteinerTreeKou< 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.

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 105 of file MinSteinerTreeKou.h.

◆ insertPath()

template<typename T >
void ogdf::MinSteinerTreeKou< T >::insertPath ( const List< edge > &  ssspPred,
EdgeWeightedGraphCopy< T > &  finalSteinerTree,
const EdgeWeightedGraph< T > &  wG 
)
protected

Inserts a shortest path corresponding to an edge in the complete terminal graph.

Parameters
ssspPredcontains for each edge in the complete terminal graph the corresponding path in the original graph
finalSteinerTreethe resulting Steiner tree
wGthe original graph

Definition at line 164 of file MinSteinerTreeKou.h.

◆ reinsertShortestPaths()

template<typename T >
void ogdf::MinSteinerTreeKou< T >::reinsertShortestPaths ( const EdgeWeightedGraphCopy< T > &  completeTerminalGraph,
const EdgeArray< List< edge > > &  ssspPred,
const NodeArray< edge > &  mstPred,
EdgeWeightedGraphCopy< T > &  finalSteinerTree,
const EdgeWeightedGraph< T > &  wG 
)
protected

Swaps an edge in the complete terminal graph with the corresponding shortest path in the original graph.

Parameters
completeTerminalGraphthe complete terminal graph
ssspPredcontains for each edge in the complete terminal graph the corresponding path in the original graph
mstPredpredecessor data structure of a minimum terminal spanning tree
finalSteinerTreethe resulting Steiner tree
wGthe original graph

Definition at line 153 of file MinSteinerTreeKou.h.


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