# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
ogdf::SteinerTreePreprocessing< T > Class Template Reference

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)

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.

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

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

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)

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

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.

computeMinSteinerTreeUpperBound () const

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.

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< boolm_copyIsTerminal
The reduced form of isTerminal.

List< nodem_copyTerminals
The reduced form of terminals.

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< intm_edgeSonsListIndex
See m_nodeSonsListIndex but for edges.

const EpsilonTest m_eps

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

## ◆ 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

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.

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

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.

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

Definition at line 503 of file SteinerTreePreprocessing.h.

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.

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

Definition at line 1534 of file SteinerTreePreprocessing.h.

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.

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

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

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

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

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.

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

Short links test using Voronoi regions [PV01].

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

Definition at line 1033 of file SteinerTreePreprocessing.h.

## ◆ m_copyGraph

template<typename T >
 EdgeWeightedGraph 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 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 ogdf::SteinerTreePreprocessing< T >::m_copyTerminals
protected

The reduced form of terminals.

Definition at line 97 of file SteinerTreePreprocessing.h.

template<typename T >
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 > 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 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 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& 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& 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& 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 > 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: