This class implements the Minimum Steiner Tree 2-approximation algorithm by Mehlhorn. More...

#include <ogdf/graphalg/MinSteinerTreeMehlhorn.h>

Inheritance diagram for ogdf::MinSteinerTreeMehlhorn< T >:

Classes
struct	MehlhornTriple
	Represents a triple as specified in the algorithms description (see paper) More...

class	MehlhornTripleBucketMaxFunc
	Helper class to sort MehlhornTriples lexicographically. More...

class	MehlhornTripleBucketMinFunc
	Helper class to sort MehlhornTriples lexicographically. More...

Public Member Functions
	MinSteinerTreeMehlhorn ()

virtual	~MinSteinerTreeMehlhorn ()

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.

Static Public Member Functions
static void	calculateCompleteGraph (const EdgeWeightedGraph< T > &wG, const List< node > &terminals, const Voronoi< T > &voronoi, EdgeArray< edge > &bridges, EdgeWeightedGraphCopy< T > &completeTerminalGraph)
	Builds a complete terminal graph.

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.

Protected Member Functions
virtual T	computeSteinerTree (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 (node u, const Voronoi< T > &voronoi, EdgeWeightedGraphCopy< T > &finalSteinerTree, const EdgeWeightedGraph< T > &wG)
	Inserts a shortest path corresponding to an edge in the complete terminal graph.

void	reinsertShortestPaths (EdgeWeightedGraphCopy< T > &completeTerminalGraph, const Voronoi< T > &voronoi, const NodeArray< edge > &mstPred, const EdgeArray< edge > &bridges, EdgeWeightedGraphCopy< T > &finalSteinerTree, const EdgeWeightedGraph< T > &wG)
	Swaps an edge in the complete terminal graph with the corresponding shortest path in the original graph.

Detailed Description

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

This class implements the Minimum Steiner Tree 2-approximation algorithm by Mehlhorn.

This implementation is based on:

(K. Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs, Information Processing Letters, volume 27, number 3, pages 125-128, 1998)

Definition at line 53 of file MinSteinerTreeMehlhorn.h.

Constructor & Destructor Documentation

◆ MinSteinerTreeMehlhorn()

template<typename T >

ogdf::MinSteinerTreeMehlhorn< T >::MinSteinerTreeMehlhorn ( )

inline

Definition at line 55 of file MinSteinerTreeMehlhorn.h.

◆ ~MinSteinerTreeMehlhorn()

template<typename T >

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

inlinevirtual

Definition at line 57 of file MinSteinerTreeMehlhorn.h.

Member Function Documentation

◆ calculateCompleteGraph()

template<typename T >

void ogdf::MinSteinerTreeMehlhorn< T >::calculateCompleteGraph	(	const EdgeWeightedGraph< T > &	wG,
		const List< node > &	terminals,
		const Voronoi< T > &	voronoi,
		EdgeArray< edge > &	bridges,
		EdgeWeightedGraphCopy< T > &	completeTerminalGraph
	)

static

Builds a complete terminal graph.

Parameters

wG	the original graph
terminals	list of terminals
voronoi	Voronoi regions (providing a mapping from each edge in the complete terminal graph to the shortest path in the original graph)
bridges	list of edges connecting terminal nodes by voronoi regions
completeTerminalGraph	the resulting complete terminal graph

Definition at line 182 of file MinSteinerTreeMehlhorn.h.

◆ computeSteinerTree()

template<typename T >

T ogdf::MinSteinerTreeMehlhorn< 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

G	The weighted input graph
terminals	The list of terminal nodes
isTerminal	A bool array of terminals
finalSteinerTree	The final Steiner tree

Returns: The objective value (sum of edge costs) of the final Steiner tree

Implements ogdf::MinSteinerTreeModule< T >.

Definition at line 158 of file MinSteinerTreeMehlhorn.h.

◆ insertPath()

template<typename T >

void ogdf::MinSteinerTreeMehlhorn< T >::insertPath	(	node	u,
		const Voronoi< T > &	voronoi,
		EdgeWeightedGraphCopy< T > &	finalSteinerTree,
		const EdgeWeightedGraph< T > &	wG
	)

protected

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

Parameters

u	terminal node needed to access the according predecessor edge in the minimum terminal spanning tree
voronoi	Voronoi regions (contains shortest paths)
finalSteinerTree	the resulting Steiner tree
wG	the original graph

Definition at line 265 of file MinSteinerTreeMehlhorn.h.

◆ reinsertShortestPaths()

template<typename T >

void ogdf::MinSteinerTreeMehlhorn< T >::reinsertShortestPaths	(	EdgeWeightedGraphCopy< T > &	completeTerminalGraph,
		const Voronoi< T > &	voronoi,
		const NodeArray< edge > &	mstPred,
		const EdgeArray< edge > &	bridges,
		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

completeTerminalGraph	the complete terminal graph
voronoi	Voronoi regions (providing a mapping from each edge in the complete terminal graph to the shortest path in the original graph)
mstPred	predecessor data structure of a minimum terminal spanning tree
bridges	list of edges connecting terminal nodes by voronoi regions
finalSteinerTree	the resulting Steiner tree
wG	the original graph

Definition at line 247 of file MinSteinerTreeMehlhorn.h.

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

include/ogdf/graphalg/MinSteinerTreeMehlhorn.h

OpenGraph DrawingFramework

Classes

Public Member Functions

Static Public Member Functions

Protected Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ MinSteinerTreeMehlhorn()

◆ ~MinSteinerTreeMehlhorn()

Member Function Documentation

◆ calculateCompleteGraph()

◆ computeSteinerTree()

◆ insertPath()

◆ reinsertShortestPaths()

Open
Graph Drawing
Framework