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.

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.

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.

Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
virtual	~MinSteinerTreeModule ()
	Do nothing on destruction.

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.

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.

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

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.

static T	pruneAllDanglingSteinerPaths (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
	Prunes nonterminal leaves and their paths to terminal or branching nodes.

static T	pruneDanglingSteinerPathFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, node start)
	Prunes the dangling Steiner path beginning at a given nonterminal leaf only.

static T	pruneDanglingSteinerPathsFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const List< node > &start)
	Prunes dangling Steiner paths beginning at given nonterminal leaves only.

static T	removeCyclesFrom (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::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 66 of file MinSteinerTreeTakahashi.h.

Constructor & Destructor Documentation

◆ MinSteinerTreeTakahashi()

template<typename T >

ogdf::MinSteinerTreeTakahashi< T >::MinSteinerTreeTakahashi ( )

inline

Definition at line 68 of file MinSteinerTreeTakahashi.h.

◆ ~MinSteinerTreeTakahashi()

template<typename T >

virtual ogdf::MinSteinerTreeTakahashi< T >::~MinSteinerTreeTakahashi ( )

inlinevirtual

Definition at line 70 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 92 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 134 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 79 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 114 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

wG	the original graph
intermediateTerminalSpanningTree	intermediate terminal spanning tree
s	source node to start from
numberOfTerminals	number of terminal nodes
isTerminal	terminal incivende vector

Returns: the weight of the intermediateTerminalSpanningTree

Definition at line 158 of file MinSteinerTreeTakahashi.h.

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

include/ogdf/graphalg/MinSteinerTreeTakahashi.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ MinSteinerTreeTakahashi()

◆ ~MinSteinerTreeTakahashi()

Member Function Documentation

◆ call() [1/3]

◆ call() [2/3]

◆ call() [3/3]

◆ computeSteinerTree()

◆ terminalDijkstra()

Open
Graph Drawing
Framework