paal::dreyfus_wagner< Metric, Terminals, NonTerminals, TerminalsLimit > Class Template Reference

#include <dreyfus_wagner.hpp>

Public Types
using	MT = data_structures::metric_traits< Metric >

using	Vertex = typename MT::VertexType

using	Dist = typename MT::DistanceType

using	Edge = typename std::pair< Vertex, Vertex >

using	TerminalsBitSet = typename std::bitset< TerminalsLimit >

using	State = std::pair< Vertex, TerminalsBitSet >

using	steiner_elements = std::unordered_set< Vertex, boost::hash< Vertex >>

Public Member Functions
	dreyfus_wagner (const Metric &cost_map, const Terminals &term, const NonTerminals &non_terminals)

void	solve (int start=0)

Dist	get_cost () const

const std::vector< Edge > &	get_edges () const

const steiner_elements &	get_steiner_elements () const

Detailed Description

template<typename Metric, typename Terminals, typename NonTerminals, unsigned int TerminalsLimit = 32>
class paal::dreyfus_wagner< Metric, Terminals, NonTerminals, TerminalsLimit >

Implements Dreyfus-Wagner algorithm. The algorithm finds optimal Steiner Tree in exponential time, 3^k * n.

Definition at line 33 of file dreyfus_wagner.hpp.

Constructor & Destructor Documentation

template<typename Metric, typename Terminals, typename NonTerminals, unsigned int TerminalsLimit = 32>

paal::dreyfus_wagner< Metric, Terminals, NonTerminals, TerminalsLimit >::dreyfus_wagner	(	const Metric &	cost_map,
		const Terminals &	term,
		const NonTerminals &	non_terminals
	)

inline

Constructor used for solving Steiner Tree problem.

Definition at line 46 of file dreyfus_wagner.hpp.

Member Function Documentation

template<typename Metric, typename Terminals, typename NonTerminals, unsigned int TerminalsLimit = 32>

Dist paal::dreyfus_wagner< Metric, Terminals, NonTerminals, TerminalsLimit >::get_cost ( ) const

inline

Gets the optimal Steiner Tree cost.

Definition at line 78 of file dreyfus_wagner.hpp.

template<typename Metric, typename Terminals, typename NonTerminals, unsigned int TerminalsLimit = 32>

const std::vector<Edge>& paal::dreyfus_wagner< Metric, Terminals, NonTerminals, TerminalsLimit >::get_edges ( ) const

inline

Gets edges belonging to optimal tree.

Definition at line 83 of file dreyfus_wagner.hpp.

template<typename Metric, typename Terminals, typename NonTerminals, unsigned int TerminalsLimit = 32>

const steiner_elements& paal::dreyfus_wagner< Metric, Terminals, NonTerminals, TerminalsLimit >::get_steiner_elements ( ) const

inline

Gets selected Steiner vertices.

Definition at line 88 of file dreyfus_wagner.hpp.

template<typename Metric, typename Terminals, typename NonTerminals, unsigned int TerminalsLimit = 32>

void paal::dreyfus_wagner< Metric, Terminals, NonTerminals, TerminalsLimit >::solve ( int start = 0 )

inline

Finds optimal Steiner Tree.

Parameters

start Vertex to start the recurrence from.

Definition at line 61 of file dreyfus_wagner.hpp.

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

include/paal/steiner_tree/dreyfus_wagner.hpp