Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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. More...
 
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. More...
 
const List< node > & getReducedTerminals () const
 Returns the list of the terminals corresponding to the reduced graph. More...
 
void shuffleReducedTerminals ()
 Shuffles the list of reduced terminals. This can have an effect on some tests. More...
 
const NodeArray< bool > & getReducedIsTerminal () const
 Returns the NodeArray<bool> isTerminal corresponding to the reduced graph. More...
 
Methods for Steiner tree solutions

These methods allow retrieval of solution information about the original instance using a solution of a preprocessed instance.

costEdgesAlreadyInserted () const
 Returns the cost of the edges already inserted in solution during the reductions. More...
 
void computeOriginalSolution (const EdgeWeightedGraphCopy< T > &reducedGraphSolution, EdgeWeightedGraphCopy< T > &correspondingOriginalSolution)
 Computes the solution for the original graph, given a solution on the reduction. More...
 
Combined reduction sets

Each method applies several reductions iteratively.

bool reduceTrivial ()
 Apply trivial (hence amazingly fast) reductions iteratively, that is degree2Test(), makeSimple(), deleteLeaves(). More...
 
bool reduceFast ()
 Apply fast reductions iteratively (includes trivial reductions). More...
 
bool reduceFastAndDualAscent ()
 Apply fast reductions and the dual-ascent-based tests iteratively. More...
 
Single reductions

Each method applies a single reduction to the Steiner tree instance.

bool deleteLeaves ()
 Deletes the leaves of the graph. More...
 
bool makeSimple ()
 Deletes parallel edges keeping only the minimum cost one, and deletes self-loops. More...
 
bool deleteComponentsWithoutTerminals ()
 Deletes connected components with no terminals. More...
 
bool leastCostTest ()
 Performs a least cost test [DV89] computing the whole shortest path matrix. More...
 
bool degree2Test ()
 deletes degree-2 nodes and replaces them with one edge with the adjacent edges' sum More...
 
bool PTmTest (const int k=3)
 "Paths with many terminals" test, efficient on paths with many terminals. More...
 
bool terminalDistanceTest ()
 Simple terminal distance test [PV01]. More...
 
bool longEdgesTest ()
 Long-Edges test from [DV89]. More...
 
bool NTDkTest (const int maxTestedDegree=5, const int k=3)
 Non-terminals of degree k test [DV89, PV01]. More...
 
bool nearestVertexTest ()
 Nearest vertex test using Voronoi regions [DV89, PV01]. More...
 
bool shortLinksTest ()
 Short links test using Voronoi regions [PV01]. More...
 
bool lowerBoundBasedTest (T upperBound)
 Computes for each non-terminal a lower bound of the cost of the minimum Steiner tree containing it. More...
 
bool lowerBoundBasedTest ()
 Like lowerBoundBasedTest(T upperBound) but the upper bound is computed by computeMinSteinerTreeUpperBound. More...
 
bool dualAscentBasedTest (int repetitions, T upperBound)
 Like lowerBoundBasedTest(T upperBound) but uses ogdf::SteinerTreeLowerBoundDualAscent to compute lower bounds. More...
 
bool dualAscentBasedTest (int repetitions=1)
 Like dualAscentBasedTest(int repetitions, T upperBound) but the upper bound is computed by computeMinSteinerTreeUpperBound. More...
 
bool reachabilityTest (int maxDegreeTest=0, const int k=3)
 Performs a reachability test [DV89]. More...
 
bool cutReachabilityTest ()
 Performs a cut reachability test [DV89]. More...
 

Protected Attributes

EdgeWeightedGraph< T > m_copyGraph
 Copy of the original graph; this copy will actually be reduced. More...
 
NodeArray< bool > m_copyIsTerminal
 The reduced form of isTerminal. More...
 
List< nodem_copyTerminals
 The reduced form of terminals. More...
 
m_costAlreadyInserted
 The cost of the already inserted in solution edges. More...
 
std::unique_ptr< MinSteinerTreeModule< T > > m_costUpperBoundAlgorithm
 Algorithm used for computing the upper bound for the cost of a minimum Steiner tree. More...
 
EdgeArray< int > m_edgeSonsListIndex
 See m_nodeSonsListIndex but for edges. More...
 
const EpsilonTest m_eps
 
NodeArray< int > m_nodeSonsListIndex
 It contains for each node an index i. More...
 
const EdgeWeightedGraph< T > & m_origGraph
 Const reference to the original graph. More...
 
const NodeArray< bool > & m_origIsTerminal
 Const reference to the original isTerminal. More...
 
const List< node > & m_origTerminals
 Const reference to the original list of terminals. More...
 
std::vector< std::vector< int > > m_sonsList
 List with lists (corresponding to nodes and containing the indexes of their sons) More...
 

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. More...
 
static bool repeat (std::function< bool()> f)
 Auxiliary function: Repeats a function until it returns false (used for iteratively applying reductions) More...
 
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. More...
 
void addNewNode (node v, const std::vector< node > &replacedNodes, const std::vector< edge > &replacedEdges, bool deleteReplacedElements)
 Calls addNew() for a node. More...
 
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. More...
 
bool addEdgesToSolution (const List< edge > &edgesToBeAddedInSolution)
 The function adds a set of edges in the solution. More...
 
void recomputeTerminalsList ()
 Used by reductions to recompute the m_copyTerminals list, according to m_copyIsTerminal; useful when "online" updates to m_copyTerminals are inefficient. More...
 
void computeShortestPathMatrix (NodeArray< NodeArray< T >> &shortestPath) const
 Computes the shortest path matrix corresponding to the m_copyGraph. More...
 
void floydWarshall (NodeArray< NodeArray< T >> &shortestPath) const
 Applies the Floyd-Warshall algorithm on the m_copyGraph. The shortestPath matrix has to be already initialized. More...
 
computeMinSteinerTreeUpperBound (EdgeWeightedGraphCopy< T > *&finalSteinerTree) const
 
computeMinSteinerTreeUpperBound () const
 
void addToSolution (const int listIndex, Array< bool, int > &isInSolution) const
 Helper method for computeOriginalSolution. More...
 
bool deleteNodesAboveUpperBound (const NodeArray< T > &lowerBoundWithNode, const T upperBound)
 Deletes the nodes whose lowerBoundWithNode exceeds upperBound. More...
 
bool deleteEdgesAboveUpperBound (const EdgeArray< T > &lowerBoundWithEdge, const T upperBound)
 Deletes the edges whose lowerBoundWithEdge exceeds upperBound. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
void computeRadiusOfTerminals (NodeArray< T > &terminalRadius) const
 Compute radius of terminals. More...
 
computeRadiusSum () const
 Compute the sum of all radii except the two largest. More...
 
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. More...
 
void markSuccessors (node currentNode, const Voronoi< T > &voronoiRegions, NodeArray< bool > &isSuccessorOfMinCostEdge) const
 Mark successors of currentNode in its shortest-path tree in voronoiRegions. More...
 
void findTwoMinimumCostEdges (node v, edge &first, edge &second) const
 Finds the first and second smallest edges incident to v. More...
 

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 90 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
wgThe initial graph that will be reduced.
terminalsThe list of terminals of the initial graph.
isTerminalTrue if a node is terminal in the initial graph, false otherwise.

Definition at line 601 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
edgesToBeAddedInSolutionThe list containing the edges that are going to be added in solution.
Returns
True iff the graph is changed

Definition at line 1386 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
xThe node or edge that represents the replaced entities. Note that its existing information will be overwritten.
replacedNodesThe deleted nodes that have to appear in solution iff x appears.
replacedEdgesThe deleted edges that have to appear in solution iff x appears.
deleteReplacedElementsTrue iff the replaced nodes and edges should be deleted.
whatSonsListIndexAn internal data structure (depending on whether you wish to use nodes or edges)

Definition at line 650 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 505 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 499 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 678 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 784 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
kThe maximum number of close terminals to be computed for every non-terminal node.
closestTerminalsA reference to a NodeArray of lists where the solution will be saved.

Definition at line 1134 of file SteinerTreePreprocessing.h.

◆ computeMinSteinerTreeUpperBound() [1/2]

template<typename T >
T ogdf::SteinerTreePreprocessing< T >::computeMinSteinerTreeUpperBound ( ) const
inlineprotected

Definition at line 534 of file SteinerTreePreprocessing.h.

◆ computeMinSteinerTreeUpperBound() [2/2]

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

Definition at line 527 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 1811 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
reducedGraphSolutionThe already computed solution on the reduced graph.
correspondingOriginalSolutionThe solution on the original graph, corresponding to the reducedGraphSolution.

Definition at line 691 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 1528 of file SteinerTreePreprocessing.h.

◆ computeRadiusSum()

template<typename T >
T ogdf::SteinerTreePreprocessing< T >::computeRadiusSum
protected

Compute the sum of all radii except the two largest.

Definition at line 1699 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 942 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 211 of file SteinerTreePreprocessing.h.

◆ cutReachabilityTest()

template<typename T >
bool ogdf::SteinerTreePreprocessing< T >::cutReachabilityTest

Performs a cut reachability test [DV89].

Definition at line 1842 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 976 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 1006 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 1685 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 807 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 1553 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 720 of file SteinerTreePreprocessing.h.

◆ dualAscentBasedTest() [1/2]

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

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

See [PV01, Section 3.2.2 on DA].

Definition at line 1668 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 436 of file SteinerTreePreprocessing.h.

◆ findClosestNonTerminals()

template<typename T >
void ogdf::SteinerTreePreprocessing< T >::findClosestNonTerminals ( node  source,
List< node > &  reachedNodes,
NodeArray< T > &  distance,
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
sourceThe source node.
reachedNodesA list where the reached nodes are saved.
distanceA NodeArray where the minimum found distance is saved, infinity where no path is found.
maxDistanceConstant such that: any distance > maxDistance is not of interest.
expandedEdgesThe maximum number of edges expanded during the computation.

Definition at line 1057 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 1359 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 918 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 193 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 202 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 196 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 953 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 1099 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 417 of file SteinerTreePreprocessing.h.

◆ lowerBoundBasedTest() [2/2]

template<typename T >
bool ogdf::SteinerTreePreprocessing< T >::lowerBoundBasedTest ( 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 1568 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 879 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 1341 of file SteinerTreePreprocessing.h.

◆ nearestVertexTest()

template<typename T >
bool ogdf::SteinerTreePreprocessing< T >::nearestVertexTest

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

Definition at line 1405 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
    maxTestedDegreeThe reduction test is applied to all nodes with degree >= 3 and <= this value
    kThe 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 1255 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
    kConsider the k nearest terminals to all non-terminals in the heuristic approach
    Returns
    True iff the graph is changed

Definition at line 1227 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
    maxDegreeTestIgnores nodes with degree larger than this. Ignores no node if non-positive (default).
    kThe 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 1724 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 773 of file SteinerTreePreprocessing.h.

◆ reduceFast()

template<typename T >
bool ogdf::SteinerTreePreprocessing< T >::reduceFast ( )
inline

Apply fast reductions iteratively (includes trivial reductions).

Definition at line 240 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 285 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 228 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 477 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 470 of file SteinerTreePreprocessing.h.

◆ shortLinksTest()

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

Short links test using Voronoi regions [PV01].

Definition at line 1475 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 199 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
mstA MinSteinerTreeModule<T> instance that is used to solve the problem
finalSteinerTreeA pointer to the final Steiner tree (has to be freed)
Returns
The weight of the final Steiner tree

Definition at line 131 of file SteinerTreePreprocessing.h.

◆ terminalDistanceTest()

template<typename T >
bool ogdf::SteinerTreePreprocessing< T >::terminalDistanceTest

Simple terminal distance test [PV01].

Definition at line 1032 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 97 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 99 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 98 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 101 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 110 of file SteinerTreePreprocessing.h.

◆ m_eps

template<typename T >
const EpsilonTest ogdf::SteinerTreePreprocessing< T >::m_eps
protected

Definition at line 95 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 103 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 92 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 94 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 93 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 111 of file SteinerTreePreprocessing.h.


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