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.

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

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.

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.

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.

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.

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.

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)=0
	Computes the actual Steiner tree.

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

static void	apspInit (const EdgeWeightedGraph< T > &G, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
	Common initialization routine for APSP algorithms.

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.

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.

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

T	The type of the edge costs of the Steiner tree instance

Definition at line 72 of file MinSteinerTreeModule.h.

Constructor & Destructor Documentation

◆ ~MinSteinerTreeModule()

template<typename T >

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

inlinevirtual

Do nothing on destruction.

Definition at line 75 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 384 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 214 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 206 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 198 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 242 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

G	Input graph
isTerminal	Incidence vector indicating terminal nodes
distance	Distance matrix result
pred	Resulting 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 647 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 188 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 180 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 172 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 631 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 368 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

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

Returns: The total cost of the final Steiner tree

Reimplemented in ogdf::MinSteinerTreePrimalDual< T >, and ogdf::MinSteinerTreeZelikovsky< T >.

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

Computes the actual Steiner tree.

Returns: The total cost of the final Steiner tree

Implemented in ogdf::MinSteinerTreeDualAscent< T >, ogdf::MinSteinerTreeDirectedCut< T >, ogdf::MinSteinerTreeGoemans139< T >, ogdf::MinSteinerTreeKou< T >, ogdf::MinSteinerTreeMehlhorn< T >, ogdf::MinSteinerTreePrimalDual< T >, ogdf::MinSteinerTreeRZLoss< T >, ogdf::MinSteinerTreeShore< T >, ogdf::MinSteinerTreeTakahashi< T >, and ogdf::MinSteinerTreeZelikovsky< T >.

◆ 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

steinerTree	The Steiner tree to be drawn
isTerminal	Incidence vector indicating terminal nodes
filename	The name of the output file

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

G	The weighted graph instance
isTerminal	Incidence vector indicating terminal nodes
filename	The name of the output file

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

G	The original weighted graph
isTerminal	Incidence vector indicating terminal nodes
steinerTree	The Steiner tree of the given graph
filename	The name of the output file

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

nonterminals	The returned list (nonterminals are appended)
G	The weighted input graph
isTerminal	A bool array of terminals

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

terminals	The returned list (terminals are appended)
G	The weighted input graph
isTerminal	A bool array of terminals

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

G	The original graph
isTerminal	A bool array of terminals

Returns: true iff the given Steiner tree problem instance is quasi-bipartite

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

G	The original graph
terminals	The list of terminal nodes
isTerminal	A bool array of terminals
steinerTree	The Steiner tree to be checked

Returns: true iff the given Steiner tree is actually one, false otherwise

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

steinerTree	The given Steiner tree
isTerminal	Incidence vector indicating terminal nodes

Returns: The total cost of the removed edges (achieved improvement)

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

steinerTree	The given Steiner tree
isTerminal	Incidence vector indicating terminals
start	A nonterminal leaf to start pruning at

Returns: The total cost of the removed edges (achieved improvement)

Definition at line 475 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 491 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 162 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

G	Input graph
source	Start terminal
isTerminal	Incidence vector indicating terminal nodes
distance	Distance matrix result
pred	Resulting shortest path such that `pred`[s][t] contains last edge of an s-t-path

Definition at line 556 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 154 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 330 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 543 of file MinSteinerTreeModule.h.

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

include/ogdf/graphalg/MinSteinerTreeModule.h

OpenGraph DrawingFramework

Public Member Functions

Static Public Member Functions

Protected Member Functions

Static Private Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ ~MinSteinerTreeModule()

Member Function Documentation

◆ allNodesByListShortestPaths()

◆ allNodeShortestPaths()

◆ allNodeShortestPathsPreferringTerminals()

◆ allNodeShortestPathsStandard()

◆ allPairShortestPaths()

◆ allPairShortestPathsPreferringTerminals()

◆ allPairShortestPathsStandard()

◆ allTerminalShortestPaths()

◆ allTerminalShortestPathsPreferringTerminals()

◆ allTerminalShortestPathsStandard()

◆ apspInit()

◆ apspInnerLoop()

◆ call()

◆ computeSteinerTree()

◆ drawSteinerTreeSVG()

◆ drawSVG() [1/2]

◆ drawSVG() [2/2]

◆ getNonterminals()

◆ getTerminals()

◆ isQuasiBipartite()

◆ isSteinerTree()

◆ pruneAllDanglingSteinerPaths()

◆ pruneDanglingSteinerPathFrom()

◆ pruneDanglingSteinerPathsFrom()

◆ removeCyclesFrom()

◆ singleSourceShortestPaths()

◆ singleSourceShortestPathsPreferringTerminals()

◆ singleSourceShortestPathsStandard()

◆ sortTerminals()

◆ ssspInit()

Open
Graph Drawing
Framework