paal::ir::steiner_tree< OrigMetric, Terminals, Result, Strategy, Oracle > Class Template Reference

The class for solving the Steiner Tree problem using Iterative Rounding. More...

#include <steiner_tree.hpp>

Public Types
using	MT = data_structures::metric_traits< OrigMetric >
using	Vertex = typename MT::VertexType
using	Vertices = std::vector< Vertex >
using	Dist = typename MT::DistanceType
using	Edge = typename std::pair< Vertex, Vertex >
using	Compare = utils::compare< double >
using	VertexIndex = data_structures::bimap< Vertex >
using	MetricIdx = data_structures::array_metric< Dist >
using	Metric = data_structures::metric_on_idx< MetricIdx &, const VertexIndex &, data_structures::read_values_tag >

Public Member Functions
	steiner_tree (const OrigMetric &metric, const Terminals &terminals, const Terminals &steiner_vertices, Result result, const Strategy &strategy=Strategy{}, Oracle oracle=Oracle{})
template<typename LP >
auto	get_find_violation (LP &lp)
void	gen_components ()
const steiner_components < Vertex, Dist > &	get_components () const
const Terminals &	get_terminals () const
auto	get_terminal_idx (Vertex v) const -> decltype(m_terminals_index.get_idx(v))
void	add_column_lp (int id, lp::col_id col)
lp::col_id	find_column_lp (int id) const
void	add_to_solution (const std::vector< Vertex > &steiner_elements)
void	set_solution ()
void	update_graph (const steiner_component< Vertex, Dist > &selected)
utils::compare< double >	get_compare () const

Detailed Description

template<typename OrigMetric, typename Terminals, typename Result, typename Strategy = steiner_tree_all_generator, typename Oracle = lp::random_violated_separation_oracle>
class paal::ir::steiner_tree< OrigMetric, Terminals, Result, Strategy, Oracle >

The class for solving the Steiner Tree problem using Iterative Rounding.

Template Parameters

OrigMetric
Terminals
Result
Strategy
Oracle	separation oracle

Definition at line 67 of file steiner_tree.hpp.

Constructor & Destructor Documentation

template<typename OrigMetric, typename Terminals, typename Result, typename Strategy = steiner_tree_all_generator, typename Oracle = lp::random_violated_separation_oracle>

paal::ir::steiner_tree< OrigMetric, Terminals, Result, Strategy, Oracle >::steiner_tree ( const OrigMetric &  metric, const Terminals &  terminals, const Terminals &  steiner_vertices, Result  result, const Strategy &  strategy = Strategy{}, Oracle  oracle = Oracle{}  )

inline

Constructor.

Definition at line 106 of file steiner_tree.hpp.

Member Function Documentation

template<typename OrigMetric, typename Terminals, typename Result, typename Strategy = steiner_tree_all_generator, typename Oracle = lp::random_violated_separation_oracle>

void paal::ir::steiner_tree< OrigMetric, Terminals, Result, Strategy, Oracle >::add_column_lp ( int  id, lp::col_id  col  )

inline

Adds map entry from component id to LP lp::col_id.

Definition at line 164 of file steiner_tree.hpp.

template<typename OrigMetric, typename Terminals, typename Result, typename Strategy = steiner_tree_all_generator, typename Oracle = lp::random_violated_separation_oracle>

void paal::ir::steiner_tree< OrigMetric, Terminals, Result, Strategy, Oracle >::add_to_solution ( const std::vector< Vertex > &  steiner_elements )

inline

Adds elements to solution.

Definition at line 177 of file steiner_tree.hpp.

template<typename OrigMetric, typename Terminals, typename Result, typename Strategy = steiner_tree_all_generator, typename Oracle = lp::random_violated_separation_oracle>

lp::col_id paal::ir::steiner_tree< OrigMetric, Terminals, Result, Strategy, Oracle >::find_column_lp ( int  id ) const

inline

Finds LP lp::col_id based on component id.

Definition at line 172 of file steiner_tree.hpp.

template<typename OrigMetric, typename Terminals, typename Result, typename Strategy = steiner_tree_all_generator, typename Oracle = lp::random_violated_separation_oracle>

void paal::ir::steiner_tree< OrigMetric, Terminals, Result, Strategy, Oracle >::gen_components ( )

inline

Generates all the components using specified strategy.

Definition at line 137 of file steiner_tree.hpp.

template<typename OrigMetric, typename Terminals, typename Result, typename Strategy = steiner_tree_all_generator, typename Oracle = lp::random_violated_separation_oracle>

utils::compare<double> paal::ir::steiner_tree< OrigMetric, Terminals, Result, Strategy, Oracle >::get_compare ( ) const

inline

Gets comparison method.

Definition at line 212 of file steiner_tree.hpp.

template<typename OrigMetric, typename Terminals, typename Result, typename Strategy = steiner_tree_all_generator, typename Oracle = lp::random_violated_separation_oracle>

const steiner_components<Vertex, Dist>& paal::ir::steiner_tree< OrigMetric, Terminals, Result, Strategy, Oracle >::get_components ( ) const

inline

Gets reference to all the components.

Definition at line 145 of file steiner_tree.hpp.

template<typename OrigMetric, typename Terminals, typename Result, typename Strategy = steiner_tree_all_generator, typename Oracle = lp::random_violated_separation_oracle>

template<typename LP >

auto paal::ir::steiner_tree< OrigMetric, Terminals, Result, Strategy, Oracle >::get_find_violation ( LP &  lp )

inline

Template Parameters

LP

Parameters

lp

Returns

Definition at line 127 of file steiner_tree.hpp.

template<typename OrigMetric, typename Terminals, typename Result, typename Strategy = steiner_tree_all_generator, typename Oracle = lp::random_violated_separation_oracle>

auto paal::ir::steiner_tree< OrigMetric, Terminals, Result, Strategy, Oracle >::get_terminal_idx ( Vertex  v ) const -> decltype(m_terminals_index.get_idx(v))

inline

Returns the index of a terminal.

Definition at line 157 of file steiner_tree.hpp.

template<typename OrigMetric, typename Terminals, typename Result, typename Strategy = steiner_tree_all_generator, typename Oracle = lp::random_violated_separation_oracle>

const Terminals& paal::ir::steiner_tree< OrigMetric, Terminals, Result, Strategy, Oracle >::get_terminals ( ) const

inline

Gets reference to all the terminals.

Definition at line 152 of file steiner_tree.hpp.

template<typename OrigMetric, typename Terminals, typename Result, typename Strategy = steiner_tree_all_generator, typename Oracle = lp::random_violated_separation_oracle>

void paal::ir::steiner_tree< OrigMetric, Terminals, Result, Strategy, Oracle >::set_solution ( )

inline

Removes duplicates and sets the final solution.

Definition at line 184 of file steiner_tree.hpp.

template<typename OrigMetric, typename Terminals, typename Result, typename Strategy = steiner_tree_all_generator, typename Oracle = lp::random_violated_separation_oracle>

void paal::ir::steiner_tree< OrigMetric, Terminals, Result, Strategy, Oracle >::update_graph ( const steiner_component< Vertex, Dist > &  selected )

inline

Merges a component into its sink.

Definition at line 192 of file steiner_tree.hpp.

---

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

• include/paal/iterative_rounding/steiner_tree/steiner_tree.hpp