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 "paal/steiner_tree/zelikovsky_11_per_6.hpp"

#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::GeneratorsSet GSet;
    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;
    paal::steiner_tree_zelikovsky11per6approximation(
        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:

• include/paal/steiner_tree/zelikovsky_11_per_6.hpp