# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
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.

virtualcall (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.

## Protected Member Functions

virtualcomputeSteinerTree (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.

constMAX_WEIGHT

## Private Member Functions

bnbInternal (T prevCost, List< edge > &currentEdges)
Calculates the optimal Steinter tree recursivly.

edge deleteEdge (edge e)
Removes the specified edge from the graph.

edge determineBranchingEdge (T prevCost) const
Decides which edge to branch on.

bool isTerminal (const node v) const
Returns whether this node is a terminal or a Steiner node.

edge lookupEdge (const node u, const node v) const
Retrieves the edge incident to both node u and v.

void moveSource (edge e, node v)
Moves the source of the edge to the specified node.

void moveTarget (edge e, node v)
Moves the target of the edge to the specified node.

edge newEdge (node source, node target, const edge originalEdge)
Creates a new edge.

void printSVG ()
Prints the current recursion status as a SVG image of the current reduced STP.

void setEdgeLookup (const node u, const node v, const edge e)
Sets the edge incident to both node u and v.

void setTerminal (const node v, bool makeTerminal)
Updates the status of the given node to either terminal or Steiner node.

solve (List< edge > &chosenEdges)
Solves the current STP instance.

bool validateMapping () const
Used to validate the current mapping of edges to orignal edges Used solely for debugging.

weightOf (edge e) const
Returns the cost of the specified edge.

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

Static Public Member Functions inherited from ogdf::MinSteinerTreeModule< T >
static void getNonterminals (ArrayBuffer< node > &nonterminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
Generates a list (as ArrayBuffer<node>) of all nonterminals.

static void getTerminals (List< node > &terminals, const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
Generates a list (as List<node>) of all terminals.

static bool isQuasiBipartite (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal)
Checks in O(n + m) time if a given Steiner tree problem instance is quasi-bipartite.

static bool isSteinerTree (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, const EdgeWeightedGraphCopy< T > &steinerTree)
Checks in O(n) time if a given tree is acually a Steiner Tree.

static void sortTerminals (List< node > &terminals)
Sort terminals by index.

staticpruneAllDanglingSteinerPaths (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
Prunes nonterminal leaves and their paths to terminal or branching nodes.

staticpruneDanglingSteinerPathFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, node start)
Prunes the dangling Steiner path beginning at a given nonterminal leaf only.

staticpruneDanglingSteinerPathsFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const List< node > &start)
Prunes dangling Steiner paths beginning at given nonterminal leaves only.

staticremoveCyclesFrom (EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal)
Remove remaining cycles from a Steiner "almost" tree.

static void singleSourceShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &isTerminal, NodeArray< T > &distance, NodeArray< edge > &pred)
Modified single-source-shortest-paths (Dijkstra) with heuristic to prefer paths over terminals.

static void singleSourceShortestPathsStandard (const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &, NodeArray< T > &distance, NodeArray< edge > &pred)
Standard single-source-shortest-paths algoritm (Dijkstra)

static void singleSourceShortestPaths (const EdgeWeightedGraph< T > &G, node source, const NodeArray< bool > &isTerminal, NodeArray< T > &distance, NodeArray< edge > &pred)
The default single-source-shortest-paths algorithm.

static void allTerminalShortestPathsStandard (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Runs singleSourceShortestPathsStandard from all terminals.

static void allTerminalShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Runs singleSourceShortestPathsPreferringTerminals from all terminals.

static void allTerminalShortestPaths (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc=singleSourceShortestPaths)
Runs a given (or the default) single-source-shortest-paths function from all terminals.

static void allNodeShortestPathsStandard (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Runs singleSourceShortestPathsStandard from all nodes.

static void allNodeShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Runs singleSourceShortestPathsPreferringTerminals from all nodes.

static void allNodeShortestPaths (const EdgeWeightedGraph< T > &G, const List< node > &terminals, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred, std::function< void(const EdgeWeightedGraph< T > &, node, const NodeArray< bool > &, NodeArray< T > &, NodeArray< edge > &)> ssspFunc=singleSourceShortestPaths)
Runs a given (or the default) single-source-shortest-paths function from all nodes.

static void allPairShortestPathsPreferringTerminals (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Modified all-pair-shortest-paths algorithm (Floyd-Warshall) with heuristic to prefer paths over terminals.

static void allPairShortestPathsStandard (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
Standard all-pair-shortest-paths algorithm (Floyd-Warshall)

static void allPairShortestPaths (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, NodeArray< NodeArray< T > > &distance, NodeArray< NodeArray< edge > > &pred)
The default all-pair-shortest-paths algorithm.

static void drawSVG (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const EdgeWeightedGraphCopy< T > &steinerTree, const char *filename)
Writes an SVG file of a minimum Steiner tree in the original graph.

static void drawSVG (const EdgeWeightedGraph< T > &G, const NodeArray< bool > &isTerminal, const char *filename)
Writes an SVG file of the instance graph.

static void drawSteinerTreeSVG (const EdgeWeightedGraphCopy< T > &steinerTree, const NodeArray< bool > &isTerminal, const char *filename)
Writes a SVG that shows only the given Steiner tree.

## Detailed Description

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

## ◆ MinSteinerTreeShore()

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

Definition at line 65 of file MinSteinerTreeShore.h.

## ◆ ~MinSteinerTreeShore()

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

Definition at line 66 of file MinSteinerTreeShore.h.

## ◆ bnbInternal()

template<typename T >
 T ogdf::MinSteinerTreeShore< T >::bnbInternal ( T 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
 prevCost the cost accumulated in previous recursion steps (previously included edges) currentEdges the 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 499 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
 G The weighted input graph terminals The list of terminal nodes isTerminal A bool array of terminals finalSteinerTree The final Steiner tree
Returns
The objective value (sum of edge costs) of the final Steiner tree

Implements ogdf::MinSteinerTreeModule< T >.

Definition at line 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 359 of file MinSteinerTreeShore.h.

## ◆ determineBranchingEdge()

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

Decides which edge to branch on.

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

Parameters
 prevCost the 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 423 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
 v the node to check
Returns
true if v is a terminal false otherwise

Definition at line 394 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
 u one of the nodes of the undirected edge v the opposite node of u
Returns
the edge between u and v nullptr if it does not exist

Definition at line 349 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
 e the edge to be moved v the new source of e

Definition at line 378 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
 e the edge to be moved v the new target of e

Definition at line 386 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
 source the source node of the new edge target the target node of the new edge originalEdge the corresponding edge in the original graph

Definition at line 369 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 688 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
 u one of the nodes of the undirected edge v the opposite node of u e the incident edge

Definition at line 354 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
 v the node to be updated makeTerminal true to set it to terminal false to set it to nonterminal

Definition at line 399 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
 chosenEdges will hold the included edges

Definition at line 408 of file MinSteinerTreeShore.h.

## ◆ validateMapping()

template<typename T >
 bool ogdf::MinSteinerTreeShore< T >::validateMapping ( ) const
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 340 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.

## ◆ m_chosenEdges

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

Definition at line 98 of file MinSteinerTreeShore.h.

## ◆ m_edges

template<typename T >
 Array2D 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 ogdf::MinSteinerTreeShore< T >::m_mapping
private

Definition at line 95 of file MinSteinerTreeShore.h.

## ◆ m_originalGraph

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

Definition at line 90 of file MinSteinerTreeShore.h.

## ◆ m_originalTerminals

template<typename T >
 const List* 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 > 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 87 of file MinSteinerTreeShore.h.

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