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

#include <ogdf/graphalg/MinSteinerTreeDualAscent.h>

Inheritance diagram for ogdf::MinSteinerTreeDualAscent< T >:

Protected Member Functions
T	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.

Private Member Functions
List< edge > *	computeCutSet (const node v) const
	Returns all incoming cut edges of the component of v.

int	findActiveComponent (node *terminal) const
	Searches for the next active component.

int	findComponent (const node v) const
	Returns the component of node v.

void	init ()
	Intializes all relevant variables.

bool	isActiveComponent (const node v) const
	Determines whether a strongly connected component is active (paper says "is root component").

bool	isTerminal (const node v, bool rootIsTerminal) const
	Returns whether this node is a terminal.

void	updateComponents ()
	Re-establishes all strongly connected components for the Steiner graph.

Private Attributes
NodeArray< int >	m_componentMapping
	maps each node to its component

GraphCopy	m_diGraph
	the directed graph

EdgeArray< bool >	m_edgeInclusions
	stores the resulting Steiner tree

EdgeArray< T >	m_edgeSlacks
	slack variables for each directed edge representing the adjusted weight

EdgeArray< edge >	m_origMapping
	maps each directed edge to its undirected original

const NodeArray< bool > *	m_pIsTerminal
	terminal incidence vector passed to the module

const EdgeWeightedGraph< T > *	m_pOrigGraph
	original graph passed to the module

const List< node > *	m_pTerminals
	list of terminals passed to the module

node	m_rootTerminal
	root node

GraphCopy	m_steinerGraph
	the to-be constructed "almost" Steiner tree

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.

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.

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.

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

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

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

static T	removeCyclesFrom (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::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 53 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

v	representative of the component

Returns: a list of edges containing each incoming cut edge once

Definition at line 254 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

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

◆ findActiveComponent()

template<typename T >

int ogdf::MinSteinerTreeDualAscent< T >::findActiveComponent ( node * terminal ) const

private

Searches for the next active component.

Parameters

terminal Will hold an arbitrary terminal of the returned component.

Returns: the index of the found componennt or -1 if none is found

Definition at line 216 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

v	the node of the component

Returns: the found component

Definition at line 196 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 151 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

v	representative of the component

Returns: true if active, false otherwise

Definition at line 297 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

v	the node to be tested
rootIsTerminal	whether the root terminal should be considered as terminal

Returns: true if v is a terminal, false otherwise

Definition at line 208 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 203 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 71 of file MinSteinerTreeDualAscent.h.

◆ m_diGraph

template<typename T >

GraphCopy ogdf::MinSteinerTreeDualAscent< T >::m_diGraph

private

the directed graph

Definition at line 61 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 65 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 66 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 63 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 59 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 57 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 58 of file MinSteinerTreeDualAscent.h.

◆ m_rootTerminal

template<typename T >

node ogdf::MinSteinerTreeDualAscent< T >::m_rootTerminal

private

root node

Definition at line 68 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 62 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 55 of file MinSteinerTreeDualAscent.h.

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

include/ogdf/graphalg/MinSteinerTreeDualAscent.h

OpenGraph DrawingFramework

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Function Documentation

◆ computeCutSet()

◆ computeSteinerTree()

◆ findActiveComponent()

◆ findComponent()

◆ init()

◆ isActiveComponent()

◆ isTerminal()

◆ updateComponents()

Member Data Documentation

◆ m_componentMapping

◆ m_diGraph

◆ m_edgeInclusions

◆ m_edgeSlacks

◆ m_origMapping

◆ m_pIsTerminal

◆ m_pOrigGraph

◆ m_pTerminals

◆ m_rootTerminal

◆ m_steinerGraph

◆ MAX_VALUE

Open
Graph Drawing
Framework