Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

ogdf::MinSteinerTreeDualAscent< T > Class Template Reference

Dual ascent heuristic for the minimum Steiner tree problem. More...

#include <ogdf/graphalg/MinSteinerTreeDualAscent.h>

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

Protected Member Functions

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

Private Member Functions

List< edge > * computeCutSet (const node v) const
 Returns all incoming cut edges of the component of v. More...
 
int findActiveComponent (node *terminal) const
 Searches for the next active component. More...
 
int findComponent (const node v) const
 Returns the component of node v. More...
 
void init ()
 Intializes all relevant variables. More...
 
bool isActiveComponent (const node v) const
 Determines whether a strongly connected component is active (paper says "is root component"). More...
 
bool isTerminal (const node v, bool rootIsTerminal) const
 Returns whether this node is a terminal. More...
 
void updateComponents ()
 Re-establishes all strongly connected components for the Steiner graph. More...
 

Private Attributes

NodeArray< int > m_componentMapping
 maps each node to its component More...
 
GraphCopy m_diGraph
 the directed graph More...
 
EdgeArray< bool > m_edgeInclusions
 stores the resulting Steiner tree More...
 
EdgeArray< T > m_edgeSlacks
 slack variables for each directed edge representing the adjusted weight More...
 
EdgeArray< edgem_origMapping
 maps each directed edge to its undirected original More...
 
const NodeArray< bool > * m_pIsTerminal
 terminal incidence vector passed to the module More...
 
const EdgeWeightedGraph< T > * m_pOrigGraph
 original graph passed to the module More...
 
const List< node > * m_pTerminals
 list of terminals passed to the module More...
 
node m_rootTerminal
 root node More...
 
GraphCopy m_steinerGraph
 the to-be constructed "almost" Steiner tree More...
 
const T MAX_VALUE = std::numeric_limits<T>::max()
 

Additional Inherited Members

- 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...
 
- 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::MinSteinerTreeDualAscent< T >

Dual ascent heuristic for the minimum Steiner tree problem.

The algorithm is implemented following the paper by Richard T. Wong, "A Dual Ascent Approach for Steiner Tree Problems on a Directed Graph", Mathematical Programming 28, pages 271-287, 1984.

Definition at line 65 of file MinSteinerTreeDualAscent.h.

Member Function Documentation

◆ computeCutSet()

template<typename T >
List< edge > * ogdf::MinSteinerTreeDualAscent< T >::computeCutSet ( const node  v) const
private

Returns all incoming cut edges of the component of v.

Parameters
vrepresentative of the component
Returns
a list of edges containing each incoming cut edge once

Definition at line 266 of file MinSteinerTreeDualAscent.h.

◆ computeSteinerTree()

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

Creates 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 358 of file MinSteinerTreeDualAscent.h.

◆ findActiveComponent()

template<typename T >
int ogdf::MinSteinerTreeDualAscent< T >::findActiveComponent ( node terminal) const
private

Searches for the next active component.

Parameters
terminalWill hold an arbitrary terminal of the returned component.
Returns
the index of the found componennt or -1 if none is found

Definition at line 228 of file MinSteinerTreeDualAscent.h.

◆ findComponent()

template<typename T >
int ogdf::MinSteinerTreeDualAscent< T >::findComponent ( const node  v) const
private

Returns the component of node v.

Parameters
vthe node of the component
Returns
the found component

Definition at line 208 of file MinSteinerTreeDualAscent.h.

◆ init()

template<typename T >
void ogdf::MinSteinerTreeDualAscent< T >::init
private

Intializes all relevant variables.

Creates the respectiv graph copies.

Definition at line 163 of file MinSteinerTreeDualAscent.h.

◆ isActiveComponent()

template<typename T >
bool ogdf::MinSteinerTreeDualAscent< T >::isActiveComponent ( const node  v) const
private

Determines whether a strongly connected component is active (paper says "is root component").

A component is active if and only if it has no dangling terminal node and includes at least one component.

Parameters
vrepresentative of the component
Returns
true if active, false otherwise

Definition at line 309 of file MinSteinerTreeDualAscent.h.

◆ isTerminal()

template<typename T >
bool ogdf::MinSteinerTreeDualAscent< T >::isTerminal ( const node  v,
bool  rootIsTerminal 
) const
private

Returns whether this node is a terminal.

If v is the root terminal, the second parameter will be returned.

Parameters
vthe node to be tested
rootIsTerminalwhether the root terminal should be considered as terminal
Returns
true if v is a terminal, false otherwise

Definition at line 220 of file MinSteinerTreeDualAscent.h.

◆ updateComponents()

template<typename T >
void ogdf::MinSteinerTreeDualAscent< T >::updateComponents
private

Re-establishes all strongly connected components for the Steiner graph.

Definition at line 215 of file MinSteinerTreeDualAscent.h.

Member Data Documentation

◆ m_componentMapping

template<typename T >
NodeArray<int> ogdf::MinSteinerTreeDualAscent< T >::m_componentMapping
private

maps each node to its component

Definition at line 83 of file MinSteinerTreeDualAscent.h.

◆ m_diGraph

template<typename T >
GraphCopy ogdf::MinSteinerTreeDualAscent< T >::m_diGraph
private

the directed graph

Definition at line 73 of file MinSteinerTreeDualAscent.h.

◆ m_edgeInclusions

template<typename T >
EdgeArray<bool> ogdf::MinSteinerTreeDualAscent< T >::m_edgeInclusions
private

stores the resulting Steiner tree

Definition at line 77 of file MinSteinerTreeDualAscent.h.

◆ m_edgeSlacks

template<typename T >
EdgeArray<T> ogdf::MinSteinerTreeDualAscent< T >::m_edgeSlacks
private

slack variables for each directed edge representing the adjusted weight

Definition at line 78 of file MinSteinerTreeDualAscent.h.

◆ m_origMapping

template<typename T >
EdgeArray<edge> ogdf::MinSteinerTreeDualAscent< T >::m_origMapping
private

maps each directed edge to its undirected original

Definition at line 75 of file MinSteinerTreeDualAscent.h.

◆ m_pIsTerminal

template<typename T >
const NodeArray<bool>* ogdf::MinSteinerTreeDualAscent< T >::m_pIsTerminal
private

terminal incidence vector passed to the module

Definition at line 71 of file MinSteinerTreeDualAscent.h.

◆ m_pOrigGraph

template<typename T >
const EdgeWeightedGraph<T>* ogdf::MinSteinerTreeDualAscent< T >::m_pOrigGraph
private

original graph passed to the module

Definition at line 69 of file MinSteinerTreeDualAscent.h.

◆ m_pTerminals

template<typename T >
const List<node>* ogdf::MinSteinerTreeDualAscent< T >::m_pTerminals
private

list of terminals passed to the module

Definition at line 70 of file MinSteinerTreeDualAscent.h.

◆ m_rootTerminal

template<typename T >
node ogdf::MinSteinerTreeDualAscent< T >::m_rootTerminal
private

root node

Definition at line 80 of file MinSteinerTreeDualAscent.h.

◆ m_steinerGraph

template<typename T >
GraphCopy ogdf::MinSteinerTreeDualAscent< T >::m_steinerGraph
private

the to-be constructed "almost" Steiner tree

Definition at line 74 of file MinSteinerTreeDualAscent.h.

◆ MAX_VALUE

template<typename T >
const T ogdf::MinSteinerTreeDualAscent< T >::MAX_VALUE = std::numeric_limits<T>::max()
private

Definition at line 67 of file MinSteinerTreeDualAscent.h.


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