paal::detail::steiner_tree< Metric, Voronoi > Class Template Reference

This is Alexander Zelikovsky 11/6 approximation algorithm for steiner tree. More...

#include <zelikovsky_11_per_6.hpp>

## Public Types

using MT = data_structures::metric_traits< Metric >

using Dist = typename MT::DistanceType

using VertexType = typename MT::VertexType

using ThreeTuple = k_tuple_t< Idx, SUBSET_SIZE >

using Move = boost::tuple< ThreeTuple, Dist >

using ResultSteinerVertices = std::vector< VertexType >

## Public Member Functions

steiner_tree (const Metric &m, const Voronoi &vor)

template<typename OutputIterator >
void get_result_steiner_vertices (OutputIterator out)

## Static Public Attributes

static const int SUBSET_SIZE = 3

## Detailed Description

### template<typename Metric, typename Voronoi> class paal::detail::steiner_tree< Metric, Voronoi >

This is Alexander Zelikovsky 11/6 approximation algorithm for steiner tree.

class steiner_tree Example:

#include "test/test_utils/sample_graph.hpp"
#include <iostream>
int main() {
// sample metric
typedef sample_graphs_metrics SGM;
auto gm = SGM::get_graph_metric_steiner();
typedef decltype(gm) Metric;
// sample voronoi
typedef paal::data_structures::voronoi<Metric> voronoiT;
typedef paal::data_structures::voronoi_traits<voronoiT> VT;
typedef VT::VerticesSet VSet;
voronoiT voronoi(GSet{ SGM::A, SGM::B, SGM::C, SGM::D }, VSet{ SGM::E },
gm);
// run algorithm
std::vector<int> steiner_points;
gm, voronoi, std::back_inserter(steiner_points));
// print result
std::cout << "Steiner points:" << std::endl;
boost::copy(steiner_points, std::ostream_iterator<int>(std::cout, "\n"));
return 0;
}

example file is steiner_tree_example.cpp

Template Parameters
 Metric we only use this metric for distances (Steiner, Terminal) and (Terminal, Terminal) Voronoi models WeakVoronoi (see Voronoi). This is a Voronoi division where generators are terminals of the steiner tree.

Definition at line 66 of file zelikovsky_11_per_6.hpp.

## Constructor & Destructor Documentation

template<typename Metric, typename Voronoi>
 paal::detail::steiner_tree< Metric, Voronoi >::steiner_tree ( const Metric & m, const Voronoi & vor )
inline
Parameters
 m vor

Definition at line 85 of file zelikovsky_11_per_6.hpp.

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