Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MinSteinerTreeTakahashi< T > Class Template Reference

This class implements the minimum Steiner tree 2-approximation algorithm by Takahashi and Matsuyama with improvements proposed by Poggi de Aragao et al. More...

#include <ogdf/graphalg/MinSteinerTreeTakahashi.h>

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

Public Member Functions

 MinSteinerTreeTakahashi ()
 
virtual ~MinSteinerTreeTakahashi ()
 
virtual T call (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const NodeArray< bool > &isOriginalTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree)
 An extended call method with intermediate and final (original) terminals. More...
 
virtual T call (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const NodeArray< bool > &isOriginalTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree, const node startNode)
 An extended call method with intermediate and final (original) terminal nodes and a specific start node. More...
 
virtual T call (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree, const node startNode)
 An extended call method with specific start node. More...
 
- Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
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...
 

Protected Member Functions

virtual T computeSteinerTree (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree) override
 Computes the actual Steiner tree. More...
 
terminalDijkstra (const EdgeWeightedGraph< T > &wG, EdgeWeightedGraphCopy< T > &intermediateTerminalSpanningTree, const node s, int numberOfTerminals, const NodeArray< bool > &isTerminal)
 Modified Dijkstra algorithm to solve the Minimum Steiner Tree problem. 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::MinSteinerTreeTakahashi< T >

This class implements the minimum Steiner tree 2-approximation algorithm by Takahashi and Matsuyama with improvements proposed by Poggi de Aragao et al.

This implementation is based on:

(H. Takahashi and A. Matsuyama, An approximate solution for the Steiner problem in graphs, Math. Japonica, volume 24, number 6, pages 573-577, 1980)

(M. Poggi de Aragao, C. Riberiro, E. Uchoa, R. Werneck, Hybrid Local Search for the Steiner Problem in Graphs, MIC 2001, pages 429-433, 2001)

Definition at line 57 of file MinSteinerTreeTakahashi.h.

Constructor & Destructor Documentation

◆ MinSteinerTreeTakahashi()

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

Definition at line 59 of file MinSteinerTreeTakahashi.h.

◆ ~MinSteinerTreeTakahashi()

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

Definition at line 61 of file MinSteinerTreeTakahashi.h.

Member Function Documentation

◆ call() [1/3]

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

An extended call method with intermediate and final (original) terminals.

You should only call this method when there is more than one terminal.

See also
MinSteinerTreeModule::call

Definition at line 86 of file MinSteinerTreeTakahashi.h.

◆ call() [2/3]

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

An extended call method with intermediate and final (original) terminal nodes and a specific start node.

You should only call this method when there is more than one terminal.

See also
MinSteinerTreeModule::call

Definition at line 139 of file MinSteinerTreeTakahashi.h.

◆ call() [3/3]

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

An extended call method with specific start node.

You should only call this method when there is more than one terminal.

See also
MinSteinerTreeModule::call

Definition at line 70 of file MinSteinerTreeTakahashi.h.

◆ computeSteinerTree()

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

Computes the actual Steiner tree.

Returns
The total cost of the final Steiner tree

Implements ogdf::MinSteinerTreeModule< T >.

Definition at line 113 of file MinSteinerTreeTakahashi.h.

◆ terminalDijkstra()

template<typename T >
T ogdf::MinSteinerTreeTakahashi< T >::terminalDijkstra ( const EdgeWeightedGraph< T > &  wG,
EdgeWeightedGraphCopy< T > &  intermediateTerminalSpanningTree,
const node  s,
int  numberOfTerminals,
const NodeArray< bool > &  isTerminal 
)
protected

Modified Dijkstra algorithm to solve the Minimum Steiner Tree problem.

Parameters
wGthe original graph
intermediateTerminalSpanningTreeintermediate terminal spanning tree
ssource node to start from
numberOfTerminalsnumber of terminal nodes
isTerminalterminal incivende vector
Returns
the weight of the intermediateTerminalSpanningTree

Definition at line 166 of file MinSteinerTreeTakahashi.h.


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