This class implements the 11/6-approximation algorithm by Zelikovsky for the minimum Steiner tree problem along with variants and practical improvements. More...

#include <ogdf/graphalg/MinSteinerTreeZelikovsky.h>

Inheritance diagram for ogdf::MinSteinerTreeZelikovsky< T >:

Public Types
enum class	Pass { one , multi }
	Enables a heuristic version (for TG exhaustive and voronoi only) More...

template<typename TYPE >
using	Save = steiner_tree::Save< TYPE >

enum class	SaveCalculation { staticEnum , staticLCATree , dynamicLCATree , hybrid }
	Different methods for obtaining save edges. More...

template<typename TYPE >
using	Triple = steiner_tree::Triple< TYPE >

enum class	TripleGeneration { exhaustive , voronoi , ondemand }
	Choice of triple generation. More...

enum class	TripleReduction { on , off }
	Switches immediate triple dropping. More...

enum class	WinCalculation { absolute , relative }
	Choice of objective function. More...

Public Member Functions
	MinSteinerTreeZelikovsky (WinCalculation wc=WinCalculation::absolute, TripleGeneration tg=TripleGeneration::voronoi, SaveCalculation sc=SaveCalculation::hybrid, TripleReduction tr=TripleReduction::on, Pass pass=Pass::multi)

virtual	~MinSteinerTreeZelikovsky ()

virtual T	call (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree) override
	Calls the Steiner tree algorithm for nontrivial cases but handles trivial cases directly.

void	forceAPSP (bool force=true)
	For the 3-restricted case, it is sufficient to compute an SSSP from every terminal instead of doing a full APSP.

long	numberOfContractedTriples () const
	Returns the number of contracted triples.

long	numberOfGeneratedTriples () const
	Returns the number of generated triples.

long	numberOfTripleLookUps () const
	Returns the number of triple lookups during execution time.

Pass	pass () const
	Returns type of pass currently in use.

void	pass (Pass p)
	Sets type of pass.

SaveCalculation	saveCalculation () const
	Returns type of save calculation currently in use.

void	saveCalculation (SaveCalculation sv)
	Sets type of save calculation.

TripleGeneration	tripleGeneration () const
	Returns type of triple generation currently in use.

void	tripleGeneration (TripleGeneration tg)
	Sets type of triple generation.

TripleReduction	tripleReduction () const
	Returns type of triple reduction currently in use.

void	tripleReduction (TripleReduction tr)
	Sets type of triple reduction.

WinCalculation	winCalculation () const
	Returns type of gain calculation currently in use.

void	winCalculation (WinCalculation wc)
	Sets type of gain calculation.

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

Protected Member Functions
double	calcWin (double gain, T cost) const
	Calculate the win.

void	computeDistanceMatrix ()
	Computes the distance matrix for the original graph.

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	contractTriple (const Triple< T > &triple, Save< T > &save, NodeArray< bool > &isNewTerminal)
	Contracts a triple and updates the save data structure.

bool	findBestTripleForCenter (node center, const Save< T > &save, Triple< T > &maxTriple) const
	Find the best triple for a given nonterminal center.

void	generateInitialTerminalSpanningTree (EdgeWeightedGraphCopy< T > &steinerTree)

void	generateTriple (node u, node v, node w, node center, const T &minCost, const Save< T > &save)
	Add a found triple to the triples list.

void	generateTriples (const Save< T > &save)
	Generates triples according to the chosen option.

void	generateTriples (const Save< T > &save, const steiner_tree::Full3ComponentGeneratorModule< T > &fcg)
	Generates triples using the given full 3-component generator.

void	multiPass (Save< T > &save, NodeArray< bool > &isNewTerminal)
	Contraction phase for the original version of the algorithm.

void	onePass (Save< T > &save, NodeArray< bool > &isNewTerminal)
	Contraction phase for the one pass heuristic.

void	tripleOnDemand (Save< T > &save, NodeArray< bool > &isNewTerminal)
	Contraction phase for algorithm generating triples on demand.

Private Attributes
NodeArray< NodeArray< T > >	m_distance
	The distance matrix.

const NodeArray< bool > *	m_isTerminal
	Incidence vector for terminal nodes.

const EdgeWeightedGraph< T > *	m_originalGraph
	The original edge-weighted graph.

Pass	m_pass
	Chosen option for pass.

NodeArray< NodeArray< edge > >	m_pred
	The predecessor matrix.

SaveCalculation	m_saveCalculation
	Chosen option for save calculation.

bool	m_ssspDistances
	True iff we only compute SSSP from terminals instead of APSP for full component construction.

const List< node > *	m_terminals
	List of terminal nodes.

TripleGeneration	m_tripleGeneration
	Chosen option for triple generation.

long	m_tripleLookUps
	Number of triple lookups.

TripleReduction	m_tripleReduction
	Chosen option for triple reduction.

List< Triple< T > >	m_triples
	The list of triples during the algorithm.

long	m_triplesContracted
	Number of contracted triples.

long	m_triplesGenerated
	Number of generated triples.

WinCalculation	m_winCalculation
	Chosen option for gain calculation.

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::MinSteinerTreeZelikovsky< T >

This class implements the 11/6-approximation algorithm by Zelikovsky for the minimum Steiner tree problem along with variants and practical improvements.

This implementation is based on:

(A. Zelikovsky, An 11/6-Approximation Algorithm for the Network Steiner Problem, Algorithmica, volume 9, number 5, pages 463-470, Springer, 1993)

(A. Zelikovsky, A faster approximation algorithm for the Steiner problem in graphs, Information Processing Letters, volume 46, number 2, pages 79-83, 1993)

(A. Zelikovsky, Better approximation bound for the network and euclidean Steiner tree problems, Technical Report, 2006)

Definition at line 66 of file MinSteinerTreeZelikovsky.h.

Member Typedef Documentation

◆ Save

template<typename T >

template<typename TYPE >

using ogdf::MinSteinerTreeZelikovsky< T >::Save = steiner_tree::Save<TYPE>

Definition at line 69 of file MinSteinerTreeZelikovsky.h.

◆ Triple

template<typename T >

template<typename TYPE >

using ogdf::MinSteinerTreeZelikovsky< T >::Triple = steiner_tree::Triple<TYPE>

Definition at line 71 of file MinSteinerTreeZelikovsky.h.

Member Enumeration Documentation

◆ Pass

template<typename T >

enum class ogdf::MinSteinerTreeZelikovsky::Pass

strong

Enables a heuristic version (for TG exhaustive and voronoi only)

Enumerator
one	heuristic: evaluate all triples, sort them descending by gain, traverse sorted triples once, contract when possible
multi	normal, greedy version

Definition at line 110 of file MinSteinerTreeZelikovsky.h.

◆ SaveCalculation

template<typename T >

enum class ogdf::MinSteinerTreeZelikovsky::SaveCalculation

strong

Different methods for obtaining save edges.

Enumerator
staticEnum	Stores explicitly the save edge for every pair of terminals. Needs O(n^2) space but has fast query times.
staticLCATree	Builds a "weight tree" (save edges are inner nodes, terminals are leaves and searches save edges via LCA calculation of two nodes.
dynamicLCATree	Same as staticLCATree but each time a triple has been contracted the "weight tree" is updated dynamically rather than completely new from scratch. Has the fastest update time.
hybrid	Uses staticEnum for the triple generation phase (many queries) and dynamicLCATree during the contraction phase (few updates)

Definition at line 93 of file MinSteinerTreeZelikovsky.h.

◆ TripleGeneration

template<typename T >

enum class ogdf::MinSteinerTreeZelikovsky::TripleGeneration

strong

Choice of triple generation.

Enumerator
exhaustive	try all possibilities
voronoi	use voronoi regions
ondemand	generate triples "on the fly", only usable with WinCalculation::absolute

Definition at line 80 of file MinSteinerTreeZelikovsky.h.

◆ TripleReduction

template<typename T >

enum class ogdf::MinSteinerTreeZelikovsky::TripleReduction

strong

Switches immediate triple dropping.

Enumerator
on	removes triples as soon as their gain is known to be non positive
off	keeps triples all the time

Definition at line 87 of file MinSteinerTreeZelikovsky.h.

◆ WinCalculation

template<typename T >

enum class ogdf::MinSteinerTreeZelikovsky::WinCalculation

strong

Choice of objective function.

Enumerator
absolute	win=gain-cost
relative	win=gain/cost

Definition at line 74 of file MinSteinerTreeZelikovsky.h.

Constructor & Destructor Documentation

◆ MinSteinerTreeZelikovsky()

template<typename T >

ogdf::MinSteinerTreeZelikovsky< T >::MinSteinerTreeZelikovsky	(	WinCalculation	wc = `WinCalculation::absolute`,
		TripleGeneration	tg = `TripleGeneration::voronoi`,
		SaveCalculation	sc = `SaveCalculation::hybrid`,
		TripleReduction	tr = `TripleReduction::on`,
		Pass	pass = `Pass::multi`
	)

inline

Definition at line 118 of file MinSteinerTreeZelikovsky.h.

◆ ~MinSteinerTreeZelikovsky()

template<typename T >

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

inlinevirtual

Definition at line 129 of file MinSteinerTreeZelikovsky.h.

Member Function Documentation

◆ calcWin()

template<typename T >

double ogdf::MinSteinerTreeZelikovsky< T >::calcWin	(	double	gain,
		T	cost
	)		const

inlineprotected

Calculate the win.

Definition at line 354 of file MinSteinerTreeZelikovsky.h.

◆ call()

template<typename T >

virtual T ogdf::MinSteinerTreeZelikovsky< T >::call	(	const EdgeWeightedGraph< T > &	G,
		const List< node > &	terminals,
		const NodeArray< bool > &	isTerminal,
		EdgeWeightedGraphCopy< T > *&	finalSteinerTree
	)

inlineoverridevirtual

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 from ogdf::MinSteinerTreeModule< T >.

Definition at line 131 of file MinSteinerTreeZelikovsky.h.

◆ computeDistanceMatrix()

template<typename T >

void ogdf::MinSteinerTreeZelikovsky< T >::computeDistanceMatrix ( )

protected

Computes the distance matrix for the original graph.

Definition at line 469 of file MinSteinerTreeZelikovsky.h.

◆ computeSteinerTree()

template<typename T >

T ogdf::MinSteinerTreeZelikovsky< 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.

See also: MinSteinerTreeModule::call

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 400 of file MinSteinerTreeZelikovsky.h.

◆ contractTriple()

template<typename T >

void ogdf::MinSteinerTreeZelikovsky< T >::contractTriple	(	const Triple< T > &	triple,
		Save< T > &	save,
		NodeArray< bool > &	isNewTerminal
	)

inlineprotected

Contracts a triple and updates the save data structure.

Parameters

triple	triple to be contracted
save	save data structure
isNewTerminal	true for nodes to be interpreted as terminals

Definition at line 252 of file MinSteinerTreeZelikovsky.h.

◆ findBestTripleForCenter()

template<typename T >

bool ogdf::MinSteinerTreeZelikovsky< T >::findBestTripleForCenter	(	node	center,
		const Save< T > &	save,
		Triple< T > &	maxTriple
	)		const

inlineprotected

Find the best triple for a given nonterminal center.

Parameters

center	the center node we want to find a better triple for
save	save data structure
maxTriple	the improved triple (output parameter)

Returns: True iff maxTriple is updated

Definition at line 272 of file MinSteinerTreeZelikovsky.h.

◆ forceAPSP()

template<typename T >

void ogdf::MinSteinerTreeZelikovsky< T >::forceAPSP ( bool force = true )

inline

For the 3-restricted case, it is sufficient to compute an SSSP from every terminal instead of doing a full APSP.

In case a full APSP is faster, use this method.

Parameters

force True to force APSP instead of SSSP.

Definition at line 144 of file MinSteinerTreeZelikovsky.h.

◆ generateInitialTerminalSpanningTree()

template<typename T >

void ogdf::MinSteinerTreeZelikovsky< T >::generateInitialTerminalSpanningTree ( EdgeWeightedGraphCopy< T > & steinerTree )

inlineprotected

Definition at line 364 of file MinSteinerTreeZelikovsky.h.

◆ generateTriple()

template<typename T >

void ogdf::MinSteinerTreeZelikovsky< T >::generateTriple	(	node	u,
		node	v,
		node	w,
		node	center,
		const T &	minCost,
		const Save< T > &	save
	)

inlineprotected

Add a found triple to the triples list.

(Just a helper to avoid code duplication.)

Definition at line 205 of file MinSteinerTreeZelikovsky.h.

◆ generateTriples() [1/2]

template<typename T >

void ogdf::MinSteinerTreeZelikovsky< T >::generateTriples ( const Save< T > & save )

inlineprotected

Generates triples according to the chosen option.

See also: TripleGeneration

Parameters

save	data structure for calculation save edges

Definition at line 234 of file MinSteinerTreeZelikovsky.h.

◆ generateTriples() [2/2]

template<typename T >

void ogdf::MinSteinerTreeZelikovsky< T >::generateTriples	(	const Save< T > &	save,
		const steiner_tree::Full3ComponentGeneratorModule< T > &	fcg
	)

inlineprotected

Generates triples using the given full 3-component generator.

Parameters

save	data structure for calculation save edges
fcg	the chosen full 3-component generator

Definition at line 222 of file MinSteinerTreeZelikovsky.h.

◆ multiPass()

template<typename T >

void ogdf::MinSteinerTreeZelikovsky< T >::multiPass	(	Save< T > &	save,
		NodeArray< bool > &	isNewTerminal
	)

protected

Contraction phase for the original version of the algorithm.

See also: MinSteinerTreeZelikovsky::multi

Parameters

save	save data structure
isNewTerminal	true for nodes to be interpreted as terminals

Definition at line 512 of file MinSteinerTreeZelikovsky.h.

◆ numberOfContractedTriples()

template<typename T >

long ogdf::MinSteinerTreeZelikovsky< T >::numberOfContractedTriples ( ) const

inline

Returns the number of contracted triples.

Definition at line 180 of file MinSteinerTreeZelikovsky.h.

◆ numberOfGeneratedTriples()

template<typename T >

long ogdf::MinSteinerTreeZelikovsky< T >::numberOfGeneratedTriples ( ) const

inline

Returns the number of generated triples.

Definition at line 177 of file MinSteinerTreeZelikovsky.h.

◆ numberOfTripleLookUps()

template<typename T >

long ogdf::MinSteinerTreeZelikovsky< T >::numberOfTripleLookUps ( ) const

inline

Returns the number of triple lookups during execution time.

Definition at line 183 of file MinSteinerTreeZelikovsky.h.

◆ onePass()

template<typename T >

void ogdf::MinSteinerTreeZelikovsky< T >::onePass	(	Save< T > &	save,
		NodeArray< bool > &	isNewTerminal
	)

protected

Contraction phase for the one pass heuristic.

See also: MinSteinerTreeZelikovsky::one

Parameters

save	save data structure
isNewTerminal	true for nodes to be interpreted as terminals

Definition at line 499 of file MinSteinerTreeZelikovsky.h.

◆ pass() [1/2]

template<typename T >

Pass ogdf::MinSteinerTreeZelikovsky< T >::pass ( ) const

inline

Returns type of pass currently in use.

See also: MinSteinerTreeZelikovsky::Pass

Definition at line 174 of file MinSteinerTreeZelikovsky.h.

◆ pass() [2/2]

template<typename T >

void ogdf::MinSteinerTreeZelikovsky< T >::pass ( Pass p )

inline

Sets type of pass.

See also: MinSteinerTreeZelikovsky::Pass

Definition at line 171 of file MinSteinerTreeZelikovsky.h.

◆ saveCalculation() [1/2]

template<typename T >

SaveCalculation ogdf::MinSteinerTreeZelikovsky< T >::saveCalculation ( ) const

inline

Returns type of save calculation currently in use.

See also: MinSteinerTreeZelikovsky::SaveCalculation

Definition at line 168 of file MinSteinerTreeZelikovsky.h.

◆ saveCalculation() [2/2]

template<typename T >

void ogdf::MinSteinerTreeZelikovsky< T >::saveCalculation ( SaveCalculation sv )

inline

Sets type of save calculation.

See also: MinSteinerTreeZelikovsky::SaveCalculation

Definition at line 165 of file MinSteinerTreeZelikovsky.h.

◆ tripleGeneration() [1/2]

template<typename T >

TripleGeneration ogdf::MinSteinerTreeZelikovsky< T >::tripleGeneration ( ) const

inline

Returns type of triple generation currently in use.

See also: MinSteinerTreeZelikovsky::TripleGeneration

Definition at line 156 of file MinSteinerTreeZelikovsky.h.

◆ tripleGeneration() [2/2]

template<typename T >

void ogdf::MinSteinerTreeZelikovsky< T >::tripleGeneration ( TripleGeneration tg )

inline

Sets type of triple generation.

See also: MinSteinerTreeZelikovsky::TripleGeneration

Definition at line 153 of file MinSteinerTreeZelikovsky.h.

◆ tripleOnDemand()

template<typename T >

void ogdf::MinSteinerTreeZelikovsky< T >::tripleOnDemand	(	Save< T > &	save,
		NodeArray< bool > &	isNewTerminal
	)

protected

Contraction phase for algorithm generating triples on demand.

See also: MinSteinerTreeZelikovsky::ondemand

Parameters

save	save data structure
isNewTerminal	true for nodes to be interpreted as terminals

Definition at line 480 of file MinSteinerTreeZelikovsky.h.

◆ tripleReduction() [1/2]

template<typename T >

TripleReduction ogdf::MinSteinerTreeZelikovsky< T >::tripleReduction ( ) const

inline

Returns type of triple reduction currently in use.

See also: MinSteinerTreeZelikovsky::TripleReduction

Definition at line 162 of file MinSteinerTreeZelikovsky.h.

◆ tripleReduction() [2/2]

template<typename T >

void ogdf::MinSteinerTreeZelikovsky< T >::tripleReduction ( TripleReduction tr )

inline

Sets type of triple reduction.

See also: MinSteinerTreeZelikovsky::TripleReduction

Definition at line 159 of file MinSteinerTreeZelikovsky.h.

◆ winCalculation() [1/2]

template<typename T >

WinCalculation ogdf::MinSteinerTreeZelikovsky< T >::winCalculation ( ) const

inline

Returns type of gain calculation currently in use.

See also: MinSteinerTreeZelikovsky::WinCalculation

Definition at line 150 of file MinSteinerTreeZelikovsky.h.

◆ winCalculation() [2/2]

template<typename T >

void ogdf::MinSteinerTreeZelikovsky< T >::winCalculation ( WinCalculation wc )

inline

Sets type of gain calculation.

See also: MinSteinerTreeZelikovsky::WinCalculation

Definition at line 147 of file MinSteinerTreeZelikovsky.h.

Member Data Documentation

◆ m_distance

template<typename T >

NodeArray<NodeArray<T> > ogdf::MinSteinerTreeZelikovsky< T >::m_distance

private

The distance matrix.

Definition at line 390 of file MinSteinerTreeZelikovsky.h.

◆ m_isTerminal

template<typename T >

const NodeArray<bool>* ogdf::MinSteinerTreeZelikovsky< T >::m_isTerminal

private

Incidence vector for terminal nodes.

Definition at line 388 of file MinSteinerTreeZelikovsky.h.

◆ m_originalGraph

template<typename T >

const EdgeWeightedGraph<T>* ogdf::MinSteinerTreeZelikovsky< T >::m_originalGraph

private

The original edge-weighted graph.

Definition at line 387 of file MinSteinerTreeZelikovsky.h.

◆ m_pass

template<typename T >

Pass ogdf::MinSteinerTreeZelikovsky< T >::m_pass

private

Chosen option for pass.

See also: Pass

Definition at line 384 of file MinSteinerTreeZelikovsky.h.

◆ m_pred

template<typename T >

NodeArray<NodeArray<edge> > ogdf::MinSteinerTreeZelikovsky< T >::m_pred

private

The predecessor matrix.

Definition at line 391 of file MinSteinerTreeZelikovsky.h.

◆ m_saveCalculation

template<typename T >

SaveCalculation ogdf::MinSteinerTreeZelikovsky< T >::m_saveCalculation

private

Chosen option for save calculation.

See also: SaveCalculation

Definition at line 382 of file MinSteinerTreeZelikovsky.h.

◆ m_ssspDistances

template<typename T >

bool ogdf::MinSteinerTreeZelikovsky< T >::m_ssspDistances

private

True iff we only compute SSSP from terminals instead of APSP for full component construction.

Definition at line 385 of file MinSteinerTreeZelikovsky.h.

◆ m_terminals

template<typename T >

const List<node>* ogdf::MinSteinerTreeZelikovsky< T >::m_terminals

private

List of terminal nodes.

Definition at line 389 of file MinSteinerTreeZelikovsky.h.

◆ m_tripleGeneration

template<typename T >

TripleGeneration ogdf::MinSteinerTreeZelikovsky< T >::m_tripleGeneration

private

Chosen option for triple generation.

See also: TripleGeneration

Definition at line 381 of file MinSteinerTreeZelikovsky.h.

◆ m_tripleLookUps

template<typename T >

long ogdf::MinSteinerTreeZelikovsky< T >::m_tripleLookUps

private

Number of triple lookups.

Definition at line 396 of file MinSteinerTreeZelikovsky.h.

◆ m_tripleReduction

template<typename T >

TripleReduction ogdf::MinSteinerTreeZelikovsky< T >::m_tripleReduction

private

Chosen option for triple reduction.

See also: TripleReduction

Definition at line 383 of file MinSteinerTreeZelikovsky.h.

◆ m_triples

template<typename T >

List<Triple<T> > ogdf::MinSteinerTreeZelikovsky< T >::m_triples

private

The list of triples during the algorithm.

Definition at line 392 of file MinSteinerTreeZelikovsky.h.

◆ m_triplesContracted

template<typename T >

long ogdf::MinSteinerTreeZelikovsky< T >::m_triplesContracted

private

Number of contracted triples.

Definition at line 395 of file MinSteinerTreeZelikovsky.h.

◆ m_triplesGenerated

template<typename T >

long ogdf::MinSteinerTreeZelikovsky< T >::m_triplesGenerated

private

Number of generated triples.

Definition at line 394 of file MinSteinerTreeZelikovsky.h.

◆ m_winCalculation

template<typename T >

WinCalculation ogdf::MinSteinerTreeZelikovsky< T >::m_winCalculation

private

Chosen option for gain calculation.

See also: WinCalculation

Definition at line 380 of file MinSteinerTreeZelikovsky.h.

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

include/ogdf/graphalg/MinSteinerTreeZelikovsky.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Protected Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Save

◆ Triple

Member Enumeration Documentation

◆ Pass

◆ SaveCalculation

◆ TripleGeneration

◆ TripleReduction

◆ WinCalculation

Constructor & Destructor Documentation

◆ MinSteinerTreeZelikovsky()

◆ ~MinSteinerTreeZelikovsky()

Member Function Documentation

◆ calcWin()

◆ call()

◆ computeDistanceMatrix()

◆ computeSteinerTree()

◆ contractTriple()

◆ findBestTripleForCenter()

◆ forceAPSP()

◆ generateInitialTerminalSpanningTree()

◆ generateTriple()

◆ generateTriples() [1/2]

◆ generateTriples() [2/2]

◆ multiPass()

◆ numberOfContractedTriples()

◆ numberOfGeneratedTriples()

◆ numberOfTripleLookUps()

◆ onePass()

◆ pass() [1/2]

◆ pass() [2/2]

◆ saveCalculation() [1/2]

◆ saveCalculation() [2/2]

◆ tripleGeneration() [1/2]

◆ tripleGeneration() [2/2]

◆ tripleOnDemand()

◆ tripleReduction() [1/2]

◆ tripleReduction() [2/2]

◆ winCalculation() [1/2]

◆ winCalculation() [2/2]

Member Data Documentation

◆ m_distance

◆ m_isTerminal

◆ m_originalGraph

◆ m_pass

◆ m_pred

◆ m_saveCalculation

◆ m_ssspDistances

◆ m_terminals

◆ m_tripleGeneration

◆ m_tripleLookUps

◆ m_tripleReduction

◆ m_triples

◆ m_triplesContracted

◆ m_triplesGenerated

◆ m_winCalculation

Open
Graph Drawing
Framework