This class implements preprocessing strategies for the Steiner tree problem. More...

#include <ogdf/graphalg/SteinerTreePreprocessing.h>

Public Member Functions
	SteinerTreePreprocessing (const EdgeWeightedGraph< T > &wg, const List< node > &terminals, const NodeArray< bool > &isTerminal)

T	solve (MinSteinerTreeModule< T > &mst, EdgeWeightedGraphCopy< T > *&finalSteinerTree)
	A shortcut to get the solution of a reduced instance.

Methods on Steiner tree instances
These methods reference to the reduced (preprocessed) instance.
const EdgeWeightedGraph< T > &	getReducedGraph () const
	Returns the reduced form of the graph.

const List< node > &	getReducedTerminals () const
	Returns the list of the terminals corresponding to the reduced graph.

void	shuffleReducedTerminals ()
	Shuffles the list of reduced terminals. This can have an effect on some tests.

const NodeArray< bool > &	getReducedIsTerminal () const
	Returns the NodeArray<bool> isTerminal corresponding to the reduced graph.

Methods for Steiner tree solutions
These methods allow retrieval of solution information about the original instance using a solution of a preprocessed instance.
T	costEdgesAlreadyInserted () const
	Returns the cost of the edges already inserted in solution during the reductions.

void	computeOriginalSolution (const EdgeWeightedGraphCopy< T > &reducedGraphSolution, EdgeWeightedGraphCopy< T > &correspondingOriginalSolution)
	Computes the solution for the original graph, given a solution on the reduction.

Combined reduction sets
Each method applies several reductions iteratively.
bool	reduceTrivial ()
	Apply trivial (hence amazingly fast) reductions iteratively, that is degree2Test(), makeSimple(), deleteLeaves().

bool	reduceFast ()
	Apply fast reductions iteratively (includes trivial reductions).

bool	reduceFastAndDualAscent ()
	Apply fast reductions and the dual-ascent-based tests iteratively.

Single reductions
Each method applies a single reduction to the Steiner tree instance.
bool	deleteLeaves ()
	Deletes the leaves of the graph.

bool	makeSimple ()
	Deletes parallel edges keeping only the minimum cost one, and deletes self-loops.

bool	deleteComponentsWithoutTerminals ()
	Deletes connected components with no terminals.

bool	leastCostTest ()
	Performs a least cost test [DV89] computing the whole shortest path matrix.

bool	degree2Test ()
	deletes degree-2 nodes and replaces them with one edge with the adjacent edges' sum

bool	PTmTest (const int k=3)
	"Paths with many terminals" test, efficient on paths with many terminals.

bool	terminalDistanceTest ()
	Simple terminal distance test [PV01].

bool	longEdgesTest ()
	Long-Edges test from [DV89].

bool	NTDkTest (const int maxTestedDegree=5, const int k=3)
	Non-terminals of degree k test [DV89, PV01].

bool	nearestVertexTest ()
	Nearest vertex test using Voronoi regions [DV89, PV01].

bool	shortLinksTest ()
	Short links test using Voronoi regions [PV01].

bool	lowerBoundBasedTest (T upperBound)
	Computes for each non-terminal a lower bound of the cost of the minimum Steiner tree containing it.

bool	lowerBoundBasedTest ()
	Like lowerBoundBasedTest(T upperBound) but the upper bound is computed by computeMinSteinerTreeUpperBound.

bool	dualAscentBasedTest (int repetitions, T upperBound)
	Like lowerBoundBasedTest(T upperBound) but uses ogdf::SteinerTreeLowerBoundDualAscent to compute lower bounds.

bool	dualAscentBasedTest (int repetitions=1)
	Like dualAscentBasedTest(int repetitions, T upperBound) but the upper bound is computed by computeMinSteinerTreeUpperBound.

bool	reachabilityTest (int maxDegreeTest=0, const int k=3)
	Performs a reachability test [DV89].

bool	cutReachabilityTest ()
	Performs a cut reachability test [DV89].

Miscellaneous methods
These methods allow retrieval of solution information about the original instance using a solution of a preprocessed instance.
void	setCostUpperBoundAlgorithm (MinSteinerTreeModule< T > *pMinSteinerTreeModule)
	Set the module option for the algorithm used for computing the MinSteinerTree cost upper bound.

Static Public Member Functions
static bool	repeat (std::function< bool()> f)
	Auxiliary function: Repeats a function until it returns false (used for iteratively applying reductions)

Protected Member Functions
bool	addEdgesToSolution (const List< edge > &edgesToBeAddedInSolution)
	The function adds a set of edges in the solution.

template<typename TWhat , typename TWhatArray >
void	addNew (TWhat x, const std::vector< node > &replacedNodes, const std::vector< edge > &replacedEdges, bool deleteReplacedElements, TWhatArray &whatSonsListIndex)
	Update internal data structures to let a (new) node or edge represent replaced nodes and/or edges.

void	addNewEdge (edge e, const std::vector< node > &replacedNodes, const std::vector< edge > &replacedEdges, bool deleteReplacedElements)
	The function is called after a new edge is added to the copy graph during the reductions.

void	addNewNode (node v, const std::vector< node > &replacedNodes, const std::vector< edge > &replacedEdges, bool deleteReplacedElements)
	Calls addNew() for a node.

void	addToSolution (const int listIndex, Array< bool, int > &isInSolution) const
	Helper method for computeOriginalSolution.

T	computeBottleneckDistance (node x, node y, const EdgeWeightedGraphCopy< T > &tprime, const steiner_tree::HeavyPathDecomposition< T > &tprimeHPD, const NodeArray< List< std::pair< node, T > > > &closestTerminals) const
	Heuristic computation [PV01] of the bottleneck Steiner distance between two nodes in a graph.

void	computeClosestKTerminals (const int k, NodeArray< List< std::pair< node, T > > > &closestTerminals) const
	Computes for every non-terminal the closest k terminals such that there is no other terminal on the path.

T	computeMinSteinerTreeUpperBound () const

T	computeMinSteinerTreeUpperBound (EdgeWeightedGraphCopy< T > *&finalSteinerTree) const

template<typename LAMBDA >
void	computeOptimalTerminals (node v, LAMBDA dist, node &optimalTerminal1, node &optimalTerminal2, NodeArray< T > &distance) const
	Compute first and second best terminals according to function `dist`.

void	computeRadiusOfTerminals (NodeArray< T > &terminalRadius) const
	Compute radius of terminals.

T	computeRadiusSum () const
	Compute the sum of all radii except the two largest.

void	computeShortestPathMatrix (NodeArray< NodeArray< T > > &shortestPath) const
	Computes the shortest path matrix corresponding to the m_copyGraph.

bool	deleteEdgesAboveUpperBound (const EdgeArray< T > &lowerBoundWithEdge, const T upperBound)
	Deletes the edges whose lowerBoundWithEdge exceeds upperBound.

bool	deleteNodesAboveUpperBound (const NodeArray< T > &lowerBoundWithNode, const T upperBound)
	Deletes the nodes whose lowerBoundWithNode exceeds upperBound.

void	deleteSteinerDegreeTwoNode (node v, const EdgeWeightedGraphCopy< T > &tprime, const steiner_tree::HeavyPathDecomposition< T > &tprimeHPD, const NodeArray< List< std::pair< node, T > > > &closestTerminals)
	Deletes a node that is known to have degree 2 in at least one minimum Steiner tree.

void	findClosestNonTerminals (node source, List< node > &reachedNodes, NodeArray< T > &distance, T maxDistance, int expandedEdges) const
	Heuristic approach to computing the closest non-terminals for one node, such that there is no terminal on the path from it to a "close non-terminal" and a maximum constant number of expandedEdges are expanded during the computation.

void	findTwoMinimumCostEdges (node v, edge &first, edge &second) const
	Finds the `first` and `second` smallest edges incident to `v`.

void	floydWarshall (NodeArray< NodeArray< T > > &shortestPath) const
	Applies the Floyd-Warshall algorithm on the m_copyGraph. The shortestPath matrix has to be already initialized.

void	markSuccessors (node currentNode, const Voronoi< T > &voronoiRegions, NodeArray< bool > &isSuccessorOfMinCostEdge) const
	Mark successors of `currentNode` in its shortest-path tree in `voronoiRegions`.

void	recomputeTerminalsList ()
	Used by reductions to recompute the m_copyTerminals list, according to m_copyIsTerminal; useful when "online" updates to m_copyTerminals are inefficient.

Protected Attributes
EdgeWeightedGraph< T >	m_copyGraph
	Copy of the original graph; this copy will actually be reduced.

NodeArray< bool >	m_copyIsTerminal
	The reduced form of isTerminal.

List< node >	m_copyTerminals
	The reduced form of terminals.

T	m_costAlreadyInserted
	The cost of the already inserted in solution edges.

std::unique_ptr< MinSteinerTreeModule< T > >	m_costUpperBoundAlgorithm
	Algorithm used for computing the upper bound for the cost of a minimum Steiner tree.

EdgeArray< int >	m_edgeSonsListIndex
	See m_nodeSonsListIndex but for edges.

const EpsilonTest	m_eps

NodeArray< int >	m_nodeSonsListIndex
	It contains for each node an index i.

const EdgeWeightedGraph< T > &	m_origGraph
	Const reference to the original graph.

const NodeArray< bool > &	m_origIsTerminal
	Const reference to the original isTerminal.

const List< node > &	m_origTerminals
	Const reference to the original list of terminals.

std::vector< std::vector< int > >	m_sonsList
	List with lists (corresponding to nodes and containing the indexes of their sons)

Detailed Description

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

This class implements preprocessing strategies for the Steiner tree problem.

It contains a subset of strategies from [DV89] and [PV01].

References:

[DV89] C. W. Duin, A. Volgenant: Reduction tests for the Steiner problem in graphs, Networks 19(5), pp. 549-567, 1989
[PV01] T. Polzin, S. V. Daneshmand: Improved algorithms for the Steiner problem in networks, Discrete Applied Mathematics 112, pp. 263-300, 2001

Definition at line 89 of file SteinerTreePreprocessing.h.

Constructor & Destructor Documentation

◆ SteinerTreePreprocessing()

template<typename T >

ogdf::SteinerTreePreprocessing< T >::SteinerTreePreprocessing	(	const EdgeWeightedGraph< T > &	wg,
		const List< node > &	terminals,
		const NodeArray< bool > &	isTerminal
	)

Parameters

wg	The initial graph that will be reduced.
terminals	The list of terminals of the initial graph.
isTerminal	True if a node is terminal in the initial graph, false otherwise.

Definition at line 608 of file SteinerTreePreprocessing.h.

Member Function Documentation

◆ addEdgesToSolution()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::addEdgesToSolution ( const List< edge > & edgesToBeAddedInSolution )

protected

The function adds a set of edges in the solution.

It assumes that after the insertion of one edge the next ones can still be added.

Parameters

edgesToBeAddedInSolution The list containing the edges that are going to be added in solution.

Returns: True iff the graph is changed

Definition at line 1391 of file SteinerTreePreprocessing.h.

◆ addNew()

template<typename T >

template<typename TWhat , typename TWhatArray >

void ogdf::SteinerTreePreprocessing< T >::addNew	(	TWhat	x,
		const std::vector< node > &	replacedNodes,
		const std::vector< edge > &	replacedEdges,
		bool	deleteReplacedElements,
		TWhatArray &	whatSonsListIndex
	)

protected

Update internal data structures to let a (new) node or edge represent replaced nodes and/or edges.

Parameters

x	The node or edge that represents the replaced entities. Note that its existing information will be overwritten.
replacedNodes	The deleted nodes that have to appear in solution iff x appears.
replacedEdges	The deleted edges that have to appear in solution iff x appears.
deleteReplacedElements	True iff the replaced nodes and edges should be deleted.
whatSonsListIndex	An internal data structure (depending on whether you wish to use nodes or edges)

Definition at line 654 of file SteinerTreePreprocessing.h.

◆ addNewEdge()

template<typename T >

void ogdf::SteinerTreePreprocessing< T >::addNewEdge	(	edge	e,
		const std::vector< node > &	replacedNodes,
		const std::vector< edge > &	replacedEdges,
		bool	deleteReplacedElements
	)

inlineprotected

The function is called after a new edge is added to the copy graph during the reductions.

Definition at line 509 of file SteinerTreePreprocessing.h.

◆ addNewNode()

template<typename T >

void ogdf::SteinerTreePreprocessing< T >::addNewNode	(	node	v,
		const std::vector< node > &	replacedNodes,
		const std::vector< edge > &	replacedEdges,
		bool	deleteReplacedElements
	)

inlineprotected

Calls addNew() for a node.

Definition at line 503 of file SteinerTreePreprocessing.h.

◆ addToSolution()

template<typename T >

void ogdf::SteinerTreePreprocessing< T >::addToSolution	(	const int	listIndex,
		Array< bool, int > &	isInSolution
	)		const

protected

Helper method for computeOriginalSolution.

Definition at line 679 of file SteinerTreePreprocessing.h.

◆ computeBottleneckDistance()

template<typename T >

T ogdf::SteinerTreePreprocessing< T >::computeBottleneckDistance	(	node	x,
		node	y,
		const EdgeWeightedGraphCopy< T > &	tprime,
		const steiner_tree::HeavyPathDecomposition< T > &	tprimeHPD,
		const NodeArray< List< std::pair< node, T > > > &	closestTerminals
	)		const

protected

Heuristic computation [PV01] of the bottleneck Steiner distance between two nodes in a graph.

Time: O(log n)

Definition at line 788 of file SteinerTreePreprocessing.h.

◆ computeClosestKTerminals()

template<typename T >

void ogdf::SteinerTreePreprocessing< T >::computeClosestKTerminals	(	const int	k,
		NodeArray< List< std::pair< node, T > > > &	closestTerminals
	)		const

protected

Computes for every non-terminal the closest k terminals such that there is no other terminal on the path.

Parameters

k	The maximum number of close terminals to be computed for every non-terminal node.
closestTerminals	A reference to a NodeArray of lists where the solution will be saved.

Definition at line 1135 of file SteinerTreePreprocessing.h.

◆ computeMinSteinerTreeUpperBound() [1/2]

template<typename T >

T ogdf::SteinerTreePreprocessing< T >::computeMinSteinerTreeUpperBound ( ) const

inlineprotected

Definition at line 540 of file SteinerTreePreprocessing.h.

◆ computeMinSteinerTreeUpperBound() [2/2]

template<typename T >

T ogdf::SteinerTreePreprocessing< T >::computeMinSteinerTreeUpperBound ( EdgeWeightedGraphCopy< T > *& finalSteinerTree ) const

inlineprotected

Definition at line 533 of file SteinerTreePreprocessing.h.

◆ computeOptimalTerminals()

template<typename T >

template<typename LAMBDA >

void ogdf::SteinerTreePreprocessing< T >::computeOptimalTerminals	(	node	v,
		LAMBDA	dist,
		node &	optimalTerminal1,
		node &	optimalTerminal2,
		NodeArray< T > &	distance
	)		const

protected

Compute first and second best terminals according to function dist.

Definition at line 1833 of file SteinerTreePreprocessing.h.

◆ computeOriginalSolution()

template<typename T >

void ogdf::SteinerTreePreprocessing< T >::computeOriginalSolution	(	const EdgeWeightedGraphCopy< T > &	reducedGraphSolution,
		EdgeWeightedGraphCopy< T > &	correspondingOriginalSolution
	)

Computes the solution for the original graph, given a solution on the reduction.

Parameters

reducedGraphSolution	The already computed solution on the reduced graph.
correspondingOriginalSolution	The solution on the original graph, corresponding to the reducedGraphSolution.

Definition at line 692 of file SteinerTreePreprocessing.h.

◆ computeRadiusOfTerminals()

template<typename T >

void ogdf::SteinerTreePreprocessing< T >::computeRadiusOfTerminals ( NodeArray< T > & terminalRadius ) const

protected

Compute radius of terminals.

Definition at line 1534 of file SteinerTreePreprocessing.h.

◆ computeRadiusSum()

template<typename T >

T ogdf::SteinerTreePreprocessing< T >::computeRadiusSum ( ) const

protected

Compute the sum of all radii except the two largest.

Definition at line 1717 of file SteinerTreePreprocessing.h.

◆ computeShortestPathMatrix()

template<typename T >

void ogdf::SteinerTreePreprocessing< T >::computeShortestPathMatrix ( NodeArray< NodeArray< T > > & shortestPath ) const

inlineprotected

Computes the shortest path matrix corresponding to the m_copyGraph.

Definition at line 947 of file SteinerTreePreprocessing.h.

◆ costEdgesAlreadyInserted()

template<typename T >

T ogdf::SteinerTreePreprocessing< T >::costEdgesAlreadyInserted ( ) const

inline

Returns the cost of the edges already inserted in solution during the reductions.

Definition at line 213 of file SteinerTreePreprocessing.h.

◆ cutReachabilityTest()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::cutReachabilityTest ( )

Performs a cut reachability test [DV89].

Time: O(n * m * log n)
Memory: O(n)
Returns
True iff the graph is changed

Precondition
Graph must not contain non-terminal leaves (use deleteLeaves()) and be connected (use deleteComponentsWithoutTerminals()).

Definition at line 1864 of file SteinerTreePreprocessing.h.

◆ degree2Test()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::degree2Test ( )

deletes degree-2 nodes and replaces them with one edge with the adjacent edges' sum

Time: O(n)
Memory: O(1)
Returns
True iff the graph is changed

Definition at line 980 of file SteinerTreePreprocessing.h.

◆ deleteComponentsWithoutTerminals()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::deleteComponentsWithoutTerminals ( )

Deletes connected components with no terminals.

Time: O(n+m)
Memory: O(n)
Returns
True iff the graph is changed

Definition at line 1009 of file SteinerTreePreprocessing.h.

◆ deleteEdgesAboveUpperBound()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::deleteEdgesAboveUpperBound	(	const EdgeArray< T > &	lowerBoundWithEdge,
		const T	upperBound
	)

protected

Deletes the edges whose lowerBoundWithEdge exceeds upperBound.

Definition at line 1703 of file SteinerTreePreprocessing.h.

◆ deleteLeaves()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::deleteLeaves ( )

Deletes the leaves of the graph.

The path to the terminal is included into the solution if the leaf is a terminal.

Time: O(n+m)
Memory: O(n)
Returns
True iff the graph is changed

Definition at line 812 of file SteinerTreePreprocessing.h.

◆ deleteNodesAboveUpperBound()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::deleteNodesAboveUpperBound	(	const NodeArray< T > &	lowerBoundWithNode,
		const T	upperBound
	)

protected

Deletes the nodes whose lowerBoundWithNode exceeds upperBound.

Definition at line 1558 of file SteinerTreePreprocessing.h.

◆ deleteSteinerDegreeTwoNode()

template<typename T >

void ogdf::SteinerTreePreprocessing< T >::deleteSteinerDegreeTwoNode	(	node	v,
		const EdgeWeightedGraphCopy< T > &	tprime,
		const steiner_tree::HeavyPathDecomposition< T > &	tprimeHPD,
		const NodeArray< List< std::pair< node, T > > > &	closestTerminals
	)

protected

Deletes a node that is known to have degree 2 in at least one minimum Steiner tree.

Definition at line 723 of file SteinerTreePreprocessing.h.

◆ dualAscentBasedTest() [1/2]

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::dualAscentBasedTest	(	int	repetitions,
		T	upperBound
	)

Like lowerBoundBasedTest(T upperBound) but uses ogdf::SteinerTreeLowerBoundDualAscent to compute lower bounds.

See [PV01, Section 3.2.2 on DA].

Time: O(m min(m, r*n) + n log n)
Returns
True iff the graph is changed

Precondition
Graph must be connected (use deleteComponentsWithoutTerminals())

Definition at line 1686 of file SteinerTreePreprocessing.h.

◆ dualAscentBasedTest() [2/2]

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::dualAscentBasedTest ( int repetitions = 1 )

inline

Like dualAscentBasedTest(int repetitions, T upperBound) but the upper bound is computed by computeMinSteinerTreeUpperBound.

Definition at line 439 of file SteinerTreePreprocessing.h.

◆ findClosestNonTerminals()

template<typename T >

void ogdf::SteinerTreePreprocessing< T >::findClosestNonTerminals	(	node	source,
		List< node > &	reachedNodes,
		NodeArray< T > &	distance,
		T	maxDistance,
		int	expandedEdges
	)		const

protected

Heuristic approach to computing the closest non-terminals for one node, such that there is no terminal on the path from it to a "close non-terminal" and a maximum constant number of expandedEdges are expanded during the computation.

Parameters

source	The source node.
reachedNodes	A list where the reached nodes are saved.
distance	A NodeArray where the minimum found distance is saved, infinity where no path is found.
maxDistance	Constant such that: any distance > maxDistance is not of interest.
expandedEdges	The maximum number of edges expanded during the computation.

Definition at line 1059 of file SteinerTreePreprocessing.h.

◆ findTwoMinimumCostEdges()

template<typename T >

void ogdf::SteinerTreePreprocessing< T >::findTwoMinimumCostEdges	(	node	v,
		edge &	first,
		edge &	second
	)		const

protected

Finds the first and second smallest edges incident to v.

Definition at line 1365 of file SteinerTreePreprocessing.h.

◆ floydWarshall()

template<typename T >

void ogdf::SteinerTreePreprocessing< T >::floydWarshall ( NodeArray< NodeArray< T > > & shortestPath ) const

protected

Applies the Floyd-Warshall algorithm on the m_copyGraph. The shortestPath matrix has to be already initialized.

Definition at line 922 of file SteinerTreePreprocessing.h.

◆ getReducedGraph()

template<typename T >

const EdgeWeightedGraph< T > & ogdf::SteinerTreePreprocessing< T >::getReducedGraph ( ) const

inline

Returns the reduced form of the graph.

Definition at line 194 of file SteinerTreePreprocessing.h.

◆ getReducedIsTerminal()

template<typename T >

const NodeArray< bool > & ogdf::SteinerTreePreprocessing< T >::getReducedIsTerminal ( ) const

inline

Returns the NodeArray<bool> isTerminal corresponding to the reduced graph.

Definition at line 203 of file SteinerTreePreprocessing.h.

◆ getReducedTerminals()

template<typename T >

const List< node > & ogdf::SteinerTreePreprocessing< T >::getReducedTerminals ( ) const

inline

Returns the list of the terminals corresponding to the reduced graph.

Definition at line 197 of file SteinerTreePreprocessing.h.

◆ leastCostTest()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::leastCostTest ( )

Performs a least cost test [DV89] computing the whole shortest path matrix.

Time: O(n^3)
Memory: O(n^2)
Returns
True iff the graph is changed

Definition at line 958 of file SteinerTreePreprocessing.h.

◆ longEdgesTest()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::longEdgesTest ( )

Long-Edges test from [DV89].

Returns: True iff the graph is changed

Precondition: Graph must be connected (use deleteComponentsWithoutTerminals())

Definition at line 1100 of file SteinerTreePreprocessing.h.

◆ lowerBoundBasedTest() [1/2]

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::lowerBoundBasedTest ( )

inline

Like lowerBoundBasedTest(T upperBound) but the upper bound is computed by computeMinSteinerTreeUpperBound.

Definition at line 420 of file SteinerTreePreprocessing.h.

◆ lowerBoundBasedTest() [2/2]

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::lowerBoundBasedTest ( T upperBound )

Computes for each non-terminal a lower bound of the cost of the minimum Steiner tree containing it.

Deletes the nodes and edges whose corresponding lower bounds exceed the upperBound. See [PV01, Observations 3.5, 3.6, and 3.8].

Time: O(m log n)
Memory: O(n)
Returns
True iff the graph is changed

Precondition
Graph must be connected (use deleteComponentsWithoutTerminals())

Definition at line 1573 of file SteinerTreePreprocessing.h.

◆ makeSimple()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::makeSimple ( )

Deletes parallel edges keeping only the minimum cost one, and deletes self-loops.

Time: O(n+m)
Memory: O(m)
Returns
True iff the graph is changed

Definition at line 884 of file SteinerTreePreprocessing.h.

◆ markSuccessors()

template<typename T >

void ogdf::SteinerTreePreprocessing< T >::markSuccessors	(	node	currentNode,
		const Voronoi< T > &	voronoiRegions,
		NodeArray< bool > &	isSuccessorOfMinCostEdge
	)		const

protected

Mark successors of currentNode in its shortest-path tree in voronoiRegions.

Definition at line 1347 of file SteinerTreePreprocessing.h.

◆ nearestVertexTest()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::nearestVertexTest ( )

Nearest vertex test using Voronoi regions [DV89, PV01].

Time: O(n log n)
Memory: O(n)
Returns
True iff the graph is changed

Precondition
Graph must be loop-free (use makeSimple()) and connected (use deleteComponentsWithoutTerminals())

Definition at line 1410 of file SteinerTreePreprocessing.h.

◆ NTDkTest()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::NTDkTest	(	const int	maxTestedDegree = `5`,
		const int	k = `3`
	)

Non-terminals of degree k test [DV89, PV01].

Time: O(m + n log n)
Memory: O(n)
Parameters

maxTestedDegree The reduction test is applied to all nodes with degree >= 3 and <= this value

k The parameter k for the internal PTmTest, applied to avoid adding useless edges

Returns
True iff the graph is changed

Precondition
Graph must be simple (use makeSimple()) and connected (use deleteComponentsWithoutTerminals())

Definition at line 1261 of file SteinerTreePreprocessing.h.

◆ PTmTest()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::PTmTest ( const int k = 3 )

"Paths with many terminals" test, efficient on paths with many terminals.

Heuristic approach, as suggested in [PV01].

Time: O(m + n log n)
Memory: O(n)
Parameters

k Consider the k nearest terminals to all non-terminals in the heuristic approach

Returns
True iff the graph is changed

Definition at line 1231 of file SteinerTreePreprocessing.h.

◆ reachabilityTest()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::reachabilityTest	(	int	maxDegreeTest = `0`,
		const int	k = `3`
	)

Performs a reachability test [DV89].

Time: O(n * m * log n)
Memory: O(n)
Parameters

maxDegreeTest Ignores nodes with degree larger than this. Ignores no node if non-positive (default).

k The parameter k for the internal PTmTest, applied to avoid adding useless edges

Returns
True iff the graph is changed

Precondition
Graph must be simple (use makeSimple()) and connected (use deleteComponentsWithoutTerminals())

Definition at line 1742 of file SteinerTreePreprocessing.h.

◆ recomputeTerminalsList()

template<typename T >

void ogdf::SteinerTreePreprocessing< T >::recomputeTerminalsList ( )

protected

Used by reductions to recompute the m_copyTerminals list, according to m_copyIsTerminal; useful when "online" updates to m_copyTerminals are inefficient.

Definition at line 778 of file SteinerTreePreprocessing.h.

◆ reduceFast()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::reduceFast ( )

inline

Apply fast reductions iteratively (includes trivial reductions).

Definition at line 243 of file SteinerTreePreprocessing.h.

◆ reduceFastAndDualAscent()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::reduceFastAndDualAscent ( )

inline

Apply fast reductions and the dual-ascent-based tests iteratively.

Definition at line 288 of file SteinerTreePreprocessing.h.

◆ reduceTrivial()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::reduceTrivial ( )

inline

Apply trivial (hence amazingly fast) reductions iteratively, that is degree2Test(), makeSimple(), deleteLeaves().

Definition at line 232 of file SteinerTreePreprocessing.h.

◆ repeat()

template<typename T >

static bool ogdf::SteinerTreePreprocessing< T >::repeat ( std::function< bool()> f )

inlinestatic

Auxiliary function: Repeats a function until it returns false (used for iteratively applying reductions)

Definition at line 480 of file SteinerTreePreprocessing.h.

◆ setCostUpperBoundAlgorithm()

template<typename T >

void ogdf::SteinerTreePreprocessing< T >::setCostUpperBoundAlgorithm ( MinSteinerTreeModule< T > * pMinSteinerTreeModule )

inline

Set the module option for the algorithm used for computing the MinSteinerTree cost upper bound.

Definition at line 473 of file SteinerTreePreprocessing.h.

◆ shortLinksTest()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::shortLinksTest ( )

Short links test using Voronoi regions [PV01].

Time: O(n log n)
Memory: O(n)
Returns
True iff the graph is changed

Precondition
Graph must be connected (use deleteComponentsWithoutTerminals())

Definition at line 1482 of file SteinerTreePreprocessing.h.

◆ shuffleReducedTerminals()

template<typename T >

void ogdf::SteinerTreePreprocessing< T >::shuffleReducedTerminals ( )

inline

Shuffles the list of reduced terminals. This can have an effect on some tests.

Definition at line 200 of file SteinerTreePreprocessing.h.

◆ solve()

template<typename T >

T ogdf::SteinerTreePreprocessing< T >::solve	(	MinSteinerTreeModule< T > &	mst,
		EdgeWeightedGraphCopy< T > *&	finalSteinerTree
	)

inline

A shortcut to get the solution of a reduced instance.

Note that you have to apply reductions first, e.g., reduceFast() or reduceFastAndDualAscent().

Parameters

mst	A MinSteinerTreeModule<T> instance that is used to solve the problem
finalSteinerTree	A pointer to the final Steiner tree (has to be freed)

Returns: The weight of the final Steiner tree

Definition at line 132 of file SteinerTreePreprocessing.h.

◆ terminalDistanceTest()

template<typename T >

bool ogdf::SteinerTreePreprocessing< T >::terminalDistanceTest ( )

Simple terminal distance test [PV01].

Time: O(m + n log n)
Memory: O(n)
Returns
True iff the graph is changed

Precondition
Graph must be connected (use deleteComponentsWithoutTerminals())

Definition at line 1033 of file SteinerTreePreprocessing.h.

Member Data Documentation

◆ m_copyGraph

template<typename T >

EdgeWeightedGraph<T> ogdf::SteinerTreePreprocessing< T >::m_copyGraph

protected

Copy of the original graph; this copy will actually be reduced.

Definition at line 96 of file SteinerTreePreprocessing.h.

◆ m_copyIsTerminal

template<typename T >

NodeArray<bool> ogdf::SteinerTreePreprocessing< T >::m_copyIsTerminal

protected

The reduced form of isTerminal.

Definition at line 98 of file SteinerTreePreprocessing.h.

◆ m_copyTerminals

template<typename T >

List<node> ogdf::SteinerTreePreprocessing< T >::m_copyTerminals

protected

The reduced form of terminals.

Definition at line 97 of file SteinerTreePreprocessing.h.

◆ m_costAlreadyInserted

template<typename T >

T ogdf::SteinerTreePreprocessing< T >::m_costAlreadyInserted

protected

The cost of the already inserted in solution edges.

Definition at line 100 of file SteinerTreePreprocessing.h.

◆ m_costUpperBoundAlgorithm

template<typename T >

std::unique_ptr<MinSteinerTreeModule<T> > ogdf::SteinerTreePreprocessing< T >::m_costUpperBoundAlgorithm

protected

Algorithm used for computing the upper bound for the cost of a minimum Steiner tree.

Definition at line 113 of file SteinerTreePreprocessing.h.

◆ m_edgeSonsListIndex

template<typename T >

EdgeArray<int> ogdf::SteinerTreePreprocessing< T >::m_edgeSonsListIndex

protected

See m_nodeSonsListIndex but for edges.

Definition at line 109 of file SteinerTreePreprocessing.h.

◆ m_eps

template<typename T >

const EpsilonTest ogdf::SteinerTreePreprocessing< T >::m_eps

protected

Definition at line 94 of file SteinerTreePreprocessing.h.

◆ m_nodeSonsListIndex

template<typename T >

NodeArray<int> ogdf::SteinerTreePreprocessing< T >::m_nodeSonsListIndex

protected

It contains for each node an index i.

If i is non-negative, m_sonsList[i] is a list containing the indices of the node's sons. A son of the current node is a node or edge that must appear in the solution if the current node appears. If i is negative, it means that the current node is original (i.e., was not created by the applied reductions). The corresponding node is the (-i)-th node of m_origGraph

Definition at line 102 of file SteinerTreePreprocessing.h.

◆ m_origGraph

template<typename T >

const EdgeWeightedGraph<T>& ogdf::SteinerTreePreprocessing< T >::m_origGraph

protected

Const reference to the original graph.

Definition at line 91 of file SteinerTreePreprocessing.h.

◆ m_origIsTerminal

template<typename T >

const NodeArray<bool>& ogdf::SteinerTreePreprocessing< T >::m_origIsTerminal

protected

Const reference to the original isTerminal.

Definition at line 93 of file SteinerTreePreprocessing.h.

◆ m_origTerminals

template<typename T >

const List<node>& ogdf::SteinerTreePreprocessing< T >::m_origTerminals

protected

Const reference to the original list of terminals.

Definition at line 92 of file SteinerTreePreprocessing.h.

◆ m_sonsList

template<typename T >

std::vector<std::vector<int> > ogdf::SteinerTreePreprocessing< T >::m_sonsList

protected

List with lists (corresponding to nodes and containing the indexes of their sons)

Definition at line 110 of file SteinerTreePreprocessing.h.

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

include/ogdf/graphalg/SteinerTreePreprocessing.h

maxTestedDegree	The reduction test is applied to all nodes with degree >= 3 and <= this value
k	The parameter k for the internal PTmTest, applied to avoid adding useless edges

maxDegreeTest	Ignores nodes with degree larger than this. Ignores no node if non-positive (default).
k	The parameter k for the internal PTmTest, applied to avoid adding useless edges

OpenGraph DrawingFramework

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ SteinerTreePreprocessing()

Member Function Documentation

◆ addEdgesToSolution()

◆ addNew()

◆ addNewEdge()

◆ addNewNode()

◆ addToSolution()

◆ computeBottleneckDistance()

◆ computeClosestKTerminals()

◆ computeMinSteinerTreeUpperBound() [1/2]

◆ computeMinSteinerTreeUpperBound() [2/2]

◆ computeOptimalTerminals()

◆ computeOriginalSolution()

◆ computeRadiusOfTerminals()

◆ computeRadiusSum()

◆ computeShortestPathMatrix()

◆ costEdgesAlreadyInserted()

◆ cutReachabilityTest()

◆ degree2Test()

◆ deleteComponentsWithoutTerminals()

◆ deleteEdgesAboveUpperBound()

◆ deleteLeaves()

◆ deleteNodesAboveUpperBound()

◆ deleteSteinerDegreeTwoNode()

◆ dualAscentBasedTest() [1/2]

◆ dualAscentBasedTest() [2/2]

◆ findClosestNonTerminals()

◆ findTwoMinimumCostEdges()

◆ floydWarshall()

◆ getReducedGraph()

◆ getReducedIsTerminal()

◆ getReducedTerminals()

◆ leastCostTest()

◆ longEdgesTest()

◆ lowerBoundBasedTest() [1/2]

◆ lowerBoundBasedTest() [2/2]

◆ makeSimple()

◆ markSuccessors()

◆ nearestVertexTest()

◆ NTDkTest()

◆ PTmTest()

◆ reachabilityTest()

◆ recomputeTerminalsList()

◆ reduceFast()

◆ reduceFastAndDualAscent()

◆ reduceTrivial()

◆ repeat()

◆ setCostUpperBoundAlgorithm()

◆ shortLinksTest()

◆ shuffleReducedTerminals()

◆ solve()

◆ terminalDistanceTest()

Member Data Documentation

◆ m_copyGraph

◆ m_copyIsTerminal

◆ m_copyTerminals

◆ m_costAlreadyInserted

◆ m_costUpperBoundAlgorithm

◆ m_edgeSonsListIndex

◆ m_eps

◆ m_nodeSonsListIndex

◆ m_origGraph

◆ m_origIsTerminal

◆ m_origTerminals

◆ m_sonsList

Open
Graph Drawing
Framework