Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::MinSteinerTreeShore< T > Class Template Reference

Implementation of Shore, Foulds and Gibbons exact branch and bound algorithm for solving Steiner tree problems. More...

#include <ogdf/graphalg/MinSteinerTreeShore.h>

+ Inheritance diagram for ogdf::MinSteinerTreeShore< T >:

Public Member Functions

 MinSteinerTreeShore ()
 
virtual ~MinSteinerTreeShore ()
 
- Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
virtual ~MinSteinerTreeModule ()
 Do nothing on destruction. More...
 
virtual T call (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree)
 Calls the Steiner tree algorithm for nontrivial cases but handles trivial cases directly. More...
 

Protected Member Functions

virtual T computeSteinerTree (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, EdgeWeightedGraphCopy< T > *&finalSteinerTree) override
 Builds a minimum Steiner tree given a weighted graph and a list of terminals. More...
 

Protected Attributes

const T MAX_WEIGHT
 

Private Member Functions

bnbInternal (T prevCost, List< edge > &currentEdges)
 Calculates the optimal Steinter tree recursivly. More...
 
edge deleteEdge (edge e)
 Removes the specified edge from the graph. More...
 
edge determineBranchingEdge (T prevCost) const
 Decides which edge to branch on. More...
 
bool isTerminal (const node v) const
 Returns whether this node is a terminal or a Steiner node. More...
 
edge lookupEdge (const node u, const node v) const
 Retrieves the edge incident to both node u and v. More...
 
void moveSource (edge e, node v)
 Moves the source of the edge to the specified node. More...
 
void moveTarget (edge e, node v)
 Moves the target of the edge to the specified node. More...
 
edge newEdge (node source, node target, const edge originalEdge)
 Creates a new edge. More...
 
void printSVG ()
 Prints the current recursion status as a SVG image of the current reduced STP. More...
 
void setEdgeLookup (const node u, const node v, const edge e)
 Sets the edge incident to both node u and v. More...
 
void setTerminal (const node v, bool makeTerminal)
 Updates the status of the given node to either terminal or Steiner node. More...
 
solve (List< edge > &chosenEdges)
 Solves the current STP instance. More...
 
bool validateMapping () const
 Used to validate the current mapping of edges to orignal edges Used solely for debugging. More...
 
weightOf (edge e) const
 Returns the cost of the specified edge. More...
 

Private Attributes

List< edgem_chosenEdges
 
Array2D< edgem_edges
 
Graph m_graph
 
EdgeArray< edgem_mapping
 
const EdgeWeightedGraph< T > * m_originalGraph
 
const List< node > * m_originalTerminals
 
int m_recursionDepth
 
std::unique_ptr< NodeSet<> > m_terminals
 
m_upperBound
 

Additional Inherited Members

- Static Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
static void getNonterminals (ArrayBuffer< node > &nonterminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
 Generates a list (as ArrayBuffer<node>) of all nonterminals. More...
 
static void getTerminals (List< node > &terminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
 Generates a list (as List<node>) of all terminals. More...
 
static bool isQuasiBipartite (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
 Checks in O(n + m) time if a given Steiner tree problem instance is quasi-bipartite. More...
 
static bool isSteinerTree (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const EdgeWeightedGraphCopy< T > &steinerTree)
 Checks in O(n) time if a given tree is acually a Steiner Tree. More...
 
static void sortTerminals (List< node > &terminals)
 Sort terminals by index. More...
 
static T pruneAllDanglingSteinerPaths (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
 Prunes nonterminal leaves and their paths to terminal or branching nodes. More...
 
static T pruneDanglingSteinerPathFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, node start)
 Prunes the dangling Steiner path beginning at a given nonterminal leaf only. More...
 
static T pruneDanglingSteinerPathsFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const List< node > &start)
 Prunes dangling Steiner paths beginning at given nonterminal leaves only. More...
 
static T removeCyclesFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
 Remove remaining cycles from a Steiner "almost" tree. More...
 
static void singleSourceShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &isTerminal, NodeArray< T > &distance, NodeArray< edge > &pred)
 Modified single-source-shortest-paths (Dijkstra) with heuristic to prefer paths over terminals. More...
 
static void singleSourceShortestPathsStandard (const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &, NodeArray< T > &distance, NodeArray< edge > &pred)
 Standard single-source-shortest-paths algoritm (Dijkstra) More...
 
static void singleSourceShortestPaths (const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &isTerminal, NodeArray< T > &distance, NodeArray< edge > &pred)
 The default single-source-shortest-paths algorithm. More...
 
static void allTerminalShortestPathsStandard (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
 Runs singleSourceShortestPathsStandard from all terminals. More...
 
static void allTerminalShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
 Runs singleSourceShortestPathsPreferringTerminals from all terminals. More...
 
static void allTerminalShortestPaths (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc=singleSourceShortestPaths)
 Runs a given (or the default) single-source-shortest-paths function from all terminals. More...
 
static void allNodeShortestPathsStandard (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
 Runs singleSourceShortestPathsStandard from all nodes. More...
 
static void allNodeShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
 Runs singleSourceShortestPathsPreferringTerminals from all nodes. More...
 
static void allNodeShortestPaths (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc=singleSourceShortestPaths)
 Runs a given (or the default) single-source-shortest-paths function from all nodes. More...
 
static void allPairShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
 Modified all-pair-shortest-paths algorithm (Floyd-Warshall) with heuristic to prefer paths over terminals. More...
 
static void allPairShortestPathsStandard (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
 Standard all-pair-shortest-paths algorithm (Floyd-Warshall) More...
 
static void allPairShortestPaths (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T >> &distance, NodeArray< NodeArray< edge >> &pred)
 The default all-pair-shortest-paths algorithm. More...
 
static void drawSVG (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const EdgeWeightedGraphCopy< T > &steinerTree, const char *filename)
 Writes an SVG file of a minimum Steiner tree in the original graph. More...
 
static void drawSVG (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const char *filename)
 Writes an SVG file of the instance graph. More...
 
static void drawSteinerTreeSVG (const EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const char *filename)
 Writes a SVG that shows only the given Steiner tree. More...
 

Detailed Description

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

Implementation of Shore, Foulds and Gibbons exact branch and bound algorithm for solving Steiner tree problems.

(Shore M.L., Foulds, L.R., and Gibbons, P.B. An Algorithm for the Steiner Problem in Graphs Networks 10:323-333, 1982.)

Definition at line 63 of file MinSteinerTreeShore.h.

Constructor & Destructor Documentation

◆ MinSteinerTreeShore()

template<typename T >
ogdf::MinSteinerTreeShore< T >::MinSteinerTreeShore ( )
inline

Definition at line 66 of file MinSteinerTreeShore.h.

◆ ~MinSteinerTreeShore()

template<typename T >
virtual ogdf::MinSteinerTreeShore< T >::~MinSteinerTreeShore ( )
inlinevirtual

Definition at line 67 of file MinSteinerTreeShore.h.

Member Function Documentation

◆ bnbInternal()

template<typename T >
T ogdf::MinSteinerTreeShore< T >::bnbInternal ( prevCost,
List< edge > &  currentEdges 
)
private

Calculates the optimal Steinter tree recursivly.

Should not be called directly but by STPSolver::solve. Each edge is either included or excluded, which gives rise to up to two new branches in each step.

Parameters
prevCostthe cost accumulated in previous recursion steps (previously included edges)
currentEdgesthe current edges
Returns
the total weight of the optimal solution (including prevCost) note: This might be higher then the actual solution if no solution satisfying the upper bound can be found.

Definition at line 518 of file MinSteinerTreeShore.h.

◆ computeSteinerTree()

template<typename T >
T ogdf::MinSteinerTreeShore< T >::computeSteinerTree ( const EdgeWeightedGraph< T > &  G,
const List< node > &  terminals,
const NodeArray< bool > &  isTerminal,
EdgeWeightedGraphCopy< T > *&  finalSteinerTree 
)
overrideprotectedvirtual

Builds a minimum Steiner tree given a weighted graph and a list of terminals.

Parameters
GThe weighted input graph
terminalsThe list of terminal nodes
isTerminalA bool array of terminals
finalSteinerTreeThe final Steiner tree
Returns
The objective value (sum of edge costs) of the final Steiner tree

Implements ogdf::MinSteinerTreeModule< T >.

Definition at line 267 of file MinSteinerTreeShore.h.

◆ deleteEdge()

template<typename T >
edge ogdf::MinSteinerTreeShore< T >::deleteEdge ( edge  e)
private

Removes the specified edge from the graph.

The corresponding original edge is returned.

Returns
the original edge, according to m_mapping

Definition at line 364 of file MinSteinerTreeShore.h.

◆ determineBranchingEdge()

template<typename T >
edge ogdf::MinSteinerTreeShore< T >::determineBranchingEdge ( prevCost) const
private

Decides which edge to branch on.

Might return nullptr if current upper bound can not be reached with this graph.

Parameters
prevCostthe cost of previously chosen edges used for comparing to current upper bound
Returns
edge to branch on next might be nullptr if current upper bound is not reachable

Definition at line 435 of file MinSteinerTreeShore.h.

◆ isTerminal()

template<typename T >
bool ogdf::MinSteinerTreeShore< T >::isTerminal ( const node  v) const
private

Returns whether this node is a terminal or a Steiner node.

Parameters
vthe node to check
Returns
true if v is a terminal false otherwise

Definition at line 403 of file MinSteinerTreeShore.h.

◆ lookupEdge()

template<typename T >
edge ogdf::MinSteinerTreeShore< T >::lookupEdge ( const node  u,
const node  v 
) const
private

Retrieves the edge incident to both node u and v.

Parameters
uone of the nodes of the undirected edge
vthe opposite node of u
Returns
the edge between u and v nullptr if it does not exist

Definition at line 351 of file MinSteinerTreeShore.h.

◆ moveSource()

template<typename T >
void ogdf::MinSteinerTreeShore< T >::moveSource ( edge  e,
node  v 
)
private

Moves the source of the edge to the specified node.

Parameters
ethe edge to be moved
vthe new source of e

Definition at line 385 of file MinSteinerTreeShore.h.

◆ moveTarget()

template<typename T >
void ogdf::MinSteinerTreeShore< T >::moveTarget ( edge  e,
node  v 
)
private

Moves the target of the edge to the specified node.

Parameters
ethe edge to be moved
vthe new target of e

Definition at line 394 of file MinSteinerTreeShore.h.

◆ newEdge()

template<typename T >
edge ogdf::MinSteinerTreeShore< T >::newEdge ( node  source,
node  target,
const edge  originalEdge 
)
private

Creates a new edge.

Parameters
sourcethe source node of the new edge
targetthe target node of the new edge
originalEdgethe corresponding edge in the original graph

Definition at line 375 of file MinSteinerTreeShore.h.

◆ printSVG()

template<typename T >
void ogdf::MinSteinerTreeShore< T >::printSVG
private

Prints the current recursion status as a SVG image of the current reduced STP.

Definition at line 707 of file MinSteinerTreeShore.h.

◆ setEdgeLookup()

template<typename T >
void ogdf::MinSteinerTreeShore< T >::setEdgeLookup ( const node  u,
const node  v,
const edge  e 
)
private

Sets the edge incident to both node u and v.

Used for faster lookup.

Parameters
uone of the nodes of the undirected edge
vthe opposite node of u
ethe incident edge

Definition at line 357 of file MinSteinerTreeShore.h.

◆ setTerminal()

template<typename T >
void ogdf::MinSteinerTreeShore< T >::setTerminal ( const node  v,
bool  makeTerminal 
)
private

Updates the status of the given node to either terminal or Steiner node.

No side-effects occur even if status is already correct.

Parameters
vthe node to be updated
makeTerminaltrue to set it to terminal false to set it to nonterminal

Definition at line 409 of file MinSteinerTreeShore.h.

◆ solve()

template<typename T >
T ogdf::MinSteinerTreeShore< T >::solve ( List< edge > &  chosenEdges)
private

Solves the current STP instance.

Will return the total cost of the optimal solution.

Parameters
chosenEdgeswill hold the included edges

Definition at line 419 of file MinSteinerTreeShore.h.

◆ validateMapping()

template<typename T >
bool ogdf::MinSteinerTreeShore< T >::validateMapping
private

Used to validate the current mapping of edges to orignal edges Used solely for debugging.

The mapping is validated by using OGDF_ASSERT.

Returns
always returns true

Definition at line 341 of file MinSteinerTreeShore.h.

◆ weightOf()

template<typename T >
T ogdf::MinSteinerTreeShore< T >::weightOf ( edge  e) const
private

Returns the cost of the specified edge.

Looks up the corresponding edge in the original graph and retrieves its weight.

Returns
weight of e

Definition at line 326 of file MinSteinerTreeShore.h.

Member Data Documentation

◆ m_chosenEdges

template<typename T >
List<edge> ogdf::MinSteinerTreeShore< T >::m_chosenEdges
private

Definition at line 98 of file MinSteinerTreeShore.h.

◆ m_edges

template<typename T >
Array2D<edge> ogdf::MinSteinerTreeShore< T >::m_edges
private

Definition at line 97 of file MinSteinerTreeShore.h.

◆ m_graph

template<typename T >
Graph ogdf::MinSteinerTreeShore< T >::m_graph
private

Definition at line 93 of file MinSteinerTreeShore.h.

◆ m_mapping

template<typename T >
EdgeArray<edge> ogdf::MinSteinerTreeShore< T >::m_mapping
private

Definition at line 95 of file MinSteinerTreeShore.h.

◆ m_originalGraph

template<typename T >
const EdgeWeightedGraph<T>* ogdf::MinSteinerTreeShore< T >::m_originalGraph
private

Definition at line 90 of file MinSteinerTreeShore.h.

◆ m_originalTerminals

template<typename T >
const List<node>* ogdf::MinSteinerTreeShore< T >::m_originalTerminals
private

Definition at line 91 of file MinSteinerTreeShore.h.

◆ m_recursionDepth

template<typename T >
int ogdf::MinSteinerTreeShore< T >::m_recursionDepth
private

Definition at line 99 of file MinSteinerTreeShore.h.

◆ m_terminals

template<typename T >
std::unique_ptr<NodeSet<> > ogdf::MinSteinerTreeShore< T >::m_terminals
private

Definition at line 94 of file MinSteinerTreeShore.h.

◆ m_upperBound

template<typename T >
T ogdf::MinSteinerTreeShore< T >::m_upperBound
private

Definition at line 96 of file MinSteinerTreeShore.h.

◆ MAX_WEIGHT

template<typename T >
const T ogdf::MinSteinerTreeShore< T >::MAX_WEIGHT
protected

Definition at line 88 of file MinSteinerTreeShore.h.


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