SteinerTree< UGraph, CostMap > Class Template Reference
[Approximation algorithms]

---

Detailed Description

template<typename UGraph, typename CostMap = typename UGraph:: template UEdgeMap<double>>
class lemon::SteinerTree< UGraph, CostMap >

The Steiner-tree problem is the next: Given a connected undirected graph, a cost function on the edges and a subset of the nodes. Construct a tree with minimum cost which covers the given subset of the nodes. The problem is NP-hard moreover it is APX-complete too.

Mehlhorn's approximation algorithm is implemented in this class, which gives a 2-approximation for the Steiner-tree problem. The algorithm's time complexity is O(nlog(n)+e). #include <lemon/steiner.h>

List of all members.

Public Member Functions
	SteinerTree (const UGraph &graph, const CostMap &cost)
	Constructor.
void	init ()
void	addTerminal (const Node &node)
	Adds a new terminal node.
void	start ()
	Executes the algorithm.
bool	tree (UEdge e)
	Checks if an edge is in the Steiner-tree or not.
bool	tree (Node n)
	Checks if the node is in the Steiner-tree or not.
bool	steiner (Node n)
	Checks if the node is a Steiner-node.
bool	terminal (Node n)
	Checks if the node is a terminal.
Value	treeValue () const
	The total cost of the tree.

---

Constructor & Destructor Documentation

SteinerTree	(	const UGraph &	graph,
		const CostMap &	cost
	)			[inline]

Constructor

---

Member Function Documentation

void init

(

)

[inline]

Initializes the internal data structures.

void addTerminal

(

const Node &

node

)

[inline]

Adds a new terminal node to the Steiner-tree problem.

void start

(

)

[inline]

Executes the algorithm.

Precondition:

init() must be called and at least some nodes should be added with addTerminal() before using this function.

This method constructs an approximation of the Steiner-Tree.

bool tree

(

UEdge

e

)

[inline]

Checks if an edge is in the Steiner-tree or not.

Parameters:

e

is the edge that will be checked

Returns:

true if e is in the Steiner-tree, false otherwise

bool tree

(

Node

n

)

[inline]

Checks if a node is in the Steiner-tree or not.

Parameters:

n

is the node that will be checked

Returns:

true if n is in the Steiner-tree, false otherwise

bool steiner

(

Node

n

)

[inline]

Checks if the node is a Steiner-node (i.e. a tree node but not terminal).

Parameters:

n

is the node that will be checked

Returns:

true if n is a Steiner-node, false otherwise

bool terminal

(

Node

n

)

[inline]

Checks if the node is a terminal.

Parameters:

n

is the node that will be checked

Returns:

true if n is a terminal, false otherwise

Value treeValue

(

)

const [inline]

The total cost of the constructed tree. The calculated value does not exceed the double of the optimal value.