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.

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.

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.

Protected Attributes
const T	MAX_WEIGHT

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

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

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

Private Attributes
List< edge >	m_chosenEdges

Array2D< edge >	m_edges

Graph	m_graph

EdgeArray< edge >	m_mapping

const EdgeWeightedGraph< T > *	m_originalGraph

const List< node > *	m_originalTerminals

int	m_recursionDepth

std::unique_ptr< NodeSet<> >	m_terminals

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

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::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 65 of file MinSteinerTreeShore.h.

◆ ~MinSteinerTreeShore()

template<typename T >

virtual ogdf::MinSteinerTreeShore< T >::~MinSteinerTreeShore ( )

inlinevirtual

Definition at line 66 of file MinSteinerTreeShore.h.

Member Function Documentation

◆ 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

protected

Definition at line 87 of file MinSteinerTreeShore.h.

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

include/ogdf/graphalg/MinSteinerTreeShore.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ MinSteinerTreeShore()

◆ ~MinSteinerTreeShore()

Member Function Documentation

◆ bnbInternal()

◆ computeSteinerTree()

◆ deleteEdge()

◆ determineBranchingEdge()

◆ isTerminal()

◆ lookupEdge()

◆ moveSource()

◆ moveTarget()

◆ newEdge()

◆ printSVG()

◆ setEdgeLookup()

◆ setTerminal()

◆ solve()

◆ validateMapping()

◆ weightOf()

Member Data Documentation

◆ m_chosenEdges

◆ m_edges

◆ m_graph

◆ m_mapping

◆ m_originalGraph

◆ m_originalTerminals

◆ m_recursionDepth

◆ m_terminals

◆ m_upperBound

◆ MAX_WEIGHT

Open
Graph Drawing
Framework