paal::detail Namespace Reference

Detail namespace. More...

## Classes

struct  upper_tag

struct  lower_tag

struct  Knapsack_0_1_get_position_range
For 0/1 knapsack dynamic algorithm for given element the table has to be traversed from the highest to the lowest element. More...

class  Knapsack_0_1
This class helps solving 0/1 knapsack problem. Function solve returns the optimal value Function Retrieve solution returns chosen elements. More...

struct  knapsack_get_position_range
For knapsack dynamic algorithm for given element the table has to be traversed from the lowest to highest element. More...

struct  get_max_element_on_value_indexed_collection

struct  get_max_element_on_capacity_indexed_collection

struct  is_range_const

class  nearest_recorder

class  multiway_cut_lp

struct  lightweight_tag

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

struct  tail

class  infinity
if the sign = true, class represents plus_infinity: object bigger than everything if the sign = false, class represents minus_infinity More...

struct  knapsack_base

struct  integral_value_and_size_tag

struct  integral_value_tag

struct  integral_size_tag

struct  non_integral_value_and_size_tag

struct  arithmetic_size_tag

struct  Nonarithmetic_size_tag

struct  zero_one_tag

struct  unbounded_tag

struct  retrieve_solution_tag

struct  no_retrieve_solution_tag

class  knapsack_data

class  svm_row
class that can read single svm row More...

struct  k_tuple

struct  k_tuple< T, 1 >

## Typedefs

template<typename SizeType , typename ValueType >
using GetIntegralTag = typename std::conditional< std::is_integral< SizeType >::value &&std::is_integral< ValueType >::value, integral_value_and_size_tag, typename std::conditional< std::is_integral< SizeType >::value, integral_size_tag, typename std::conditional< std::is_integral< ValueType >::value, integral_value_tag, non_integral_value_and_size_tag >::type >::type >::type

template<typename SizeType >
using Getarithmetic_size_tag = typename std::conditional< std::is_arithmetic< SizeType >::value, arithmetic_size_tag, Nonarithmetic_size_tag >::type

template<class Graph >
using CostType = typename boost::property_traits< puretype(get(boost::edge_weight, std::declval< Graph >()))>::value_type

template<typename Functor , typename Range >
using FunctorOnRangePValue = puretype(std::declval< Functor >()(*std::begin(std::declval< Range >())))

## Functions

template<typename KnapsackData >
KnapsackData::value get_density_based_value_upper_bound (KnapsackData knap_data)
upper bound is computed as biggest density times capacity + values for all elements with size 0. It is correct upper bound for 0/1. For unbounded case there will be no elements with size 0.

template<typename KnapsackData , typename Is_0_1_Tag >
KnapsackData::value get_value_bound (KnapsackData knap_data, Nonarithmetic_size_tag, Is_0_1_Tag, upper_tag)

template<typename KnapsackData , typename Is_0_1_Tag >
KnapsackData::value get_value_bound (KnapsackData knap_data, arithmetic_size_tag, Is_0_1_Tag is_0_1_Tag, upper_tag)

template<typename KnapsackData , typename Is_0_1_Tag >
KnapsackData::value get_value_bound (KnapsackData knap_data, Nonarithmetic_size_tag, Is_0_1_Tag, lower_tag)

template<typename KnapsackData , typename Is_0_1_Tag >
KnapsackData::value get_value_bound (KnapsackData knap_data, arithmetic_size_tag, Is_0_1_Tag is_0_1_Tag, lower_tag)

template<typename KnapsackData , typename Is_0_1_Tag , typename BoundType >
KnapsackData::value get_value_bound (KnapsackData knap_data, Is_0_1_Tag is_0_1_tag, BoundType bound_type_tag)

template<typename KnapsackData , typename Is_0_1_Tag , typename RetrieveSolution = retrieve_solution_tag, typename Value = typename KnapsackData::value, typename Size = typename KnapsackData::size>
KnapsackData::return_type knapsack_check_integrality (KnapsackData knap_data, Is_0_1_Tag is_0_1_Tag, RetrieveSolution retrieve_solutionTag=RetrieveSolution{})

template<typename KnapsackData , typename IntegralTag , typename RetrieveSolution , typename Is_0_1_Tag , typename = typename std::enable_if<std::is_same< non_integral_value_and_size_tag, IntegralTag>::value>::type>
KnapsackData::return_type knapsack (KnapsackData, Is_0_1_Tag is_0_1_Tag, IntegralTag, RetrieveSolution retrieve_solution)

template<typename KnapsackData , typename Is_0_1_Tag , typename RetrieveSolution >
KnapsackData::return_type knapsack (KnapsackData knap_data, Is_0_1_Tag is_0_1_Tag, integral_value_and_size_tag, RetrieveSolution retrieve_solutionTag)
Solution to Knapsack problem overload for integral Size and Value case.

template<typename Objects , typename Functor >
boost::optional< double > get_multiplier (Objects &&objects, double epsilon, double lowerBound, Functor, detail::zero_one_tag)
computes multiplier for FPTAS, version for 0/1

template<typename Objects , typename Functor >
boost::optional< double > get_multiplier (Objects &&objects, double epsilon, double lowerBound, Functor f, detail::unbounded_tag)
computes multiplier for FPTAS, unbounded version

template<typename KnapsackData , typename IsZeroOne , typename RetrieveSolution , typename ReturnType = typename KnapsackData::return_type>
ReturnType knapsack_general_on_value_fptas (double epsilon, KnapsackData knap_data, IsZeroOne is_0_1_Tag, RetrieveSolution retrieve_solution)

template<typename KnapsackData , typename IsZeroOne , typename RetrieveSolution , typename ReturnType = typename KnapsackData::return_type>
ReturnType knapsack_general_on_size_fptas (double epsilon, KnapsackData knap_data, IsZeroOne is_0_1_Tag, RetrieveSolution retrieve_solution)

template<typename KnapsackData , typename IsZeroOne >
KnapsackData::return_type knapsack_general_on_value_fptas_retrieve (double epsilon, KnapsackData knap_data, IsZeroOne is_0_1_Tag)

template<typename KnapsackData , typename IsZeroOne , typename ReturnType = typename KnapsackData::return_type>
ReturnType knapsack_general_on_size_fptas_retrieve (double epsilon, KnapsackData knap_data, IsZeroOne is_0_1_Tag)

template<typename Objects , typename ObjectSizeFunctor , typename ObjectValueFunctor , typename Comparator >
Knapsack_0_1< Objects,
ObjectSizeFunctor,
ObjectValueFunctor, Comparator >
make_knapsack_0_1 (ObjectSizeFunctor size, ObjectValueFunctor value, Comparator comp)

template<typename Knapsack , typename IndexType , typename ValueType , typename Objects , typename OutputIterator >
void retrieve_solution (const Knapsack &knapsack, ValueType maxValue, IndexType size, Objects &&objects, OutputIterator &out, retrieve_solution_tag)

template<typename Knapsack , typename IndexType , typename ValueType , typename Objects , typename OutputIterator >
void retrieve_solution (const Knapsack &knapsack, ValueType maxValue, IndexType size, Objects &&objects, OutputIterator &out, no_retrieve_solution_tag)

template<typename KnapsackData , typename retrieve_solution_tag >
auto knapsack (KnapsackData knap_data, zero_one_tag, integral_size_tag, retrieve_solution_tag retrieve_solutionTag)
Solution to Knapsack 0/1 problem overload for integral Size case.

template<typename KnapsackData , typename retrieve_solution_tag >
auto knapsack (KnapsackData knap_data, zero_one_tag, integral_value_tag, retrieve_solution_tag retrieve_solutionTag)
Solution to Knapsack 0/1 problem overload for integral Value case.

template<typename KnapsackData , typename GetBestElement , typename ValuesComparator , typename ReturnType = typename KnapsackData::return_type>
ReturnType knapsack_unbounded_dynamic (KnapsackData knap_data, GetBestElement getBest, ValuesComparator compareValues)

template<typename KnapsackData , typename ReturnType = typename KnapsackData::return_type, typename Size = typename KnapsackData::size>
ReturnType knapsack (KnapsackData knap_data, unbounded_tag, integral_value_tag, retrieve_solution_tag)
Solution to the knapsack problem. More...

template<typename KnapsackData >
KnapsackData::return_type knapsack (KnapsackData knap_data, unbounded_tag, integral_size_tag, retrieve_solution_tag)
Solution to the knapsack problem. More...

template<typename KnapsackData , typename Is_0_1_Tag , typename Value = typename KnapsackData::value, typename Size = typename KnapsackData::size>
KnapsackData::return_type knapsack_general_two_app (KnapsackData knapsack_data, Is_0_1_Tag is_0_1_Tag)

template<typename KnapsackData , typename ObjectIter = typename KnapsackData::object_iter, typename ObjectRef = typename KnapsackData::object_ref, typename Size = typename KnapsackData::size, typename Value = typename KnapsackData::value>
std::tuple< Value, Size,
boost::iterator_range
< ObjectIter > >
get_greedy_fill (KnapsackData knap_data, zero_one_tag)

template<typename ObjectsRange , typename OutputIter >
void greedy_to_output (ObjectsRange range, OutputIter &out, zero_one_tag)

template<typename KnapsackData , typename ObjectIter = typename KnapsackData::object_iter, typename Size = typename KnapsackData::size, typename Value = typename KnapsackData::value>
std::tuple< Value, Size,
std::pair< ObjectIter,
unsigned > >
get_greedy_fill (KnapsackData knap_data, unbounded_tag)

template<typename ObjectsIterAndNr , typename OutputIter >
void greedy_to_output (ObjectsIterAndNr most_dense_iter_and_nr, OutputIter &out, unbounded_tag)

template<typename NearestMap , typename LastEdgeMap , typename Tag >
nearest_recorder< NearestMap,
LastEdgeMap, Tag >
make_nearest_recorder (NearestMap &nearest_map, LastEdgeMap &vpred, Tag)

int vertices_column_index (int vertex, int dimentions, int column)

template<typename Graph , typename VertexIndexMap , typename EdgeWeightMap , typename Dist , typename Rand , typename LP >
auto make_cut (const Graph &graph, int k, const VertexIndexMap &index_map, const EdgeWeightMap &weight_map, Dist &dist, Rand &&random_engine, multiway_cut_lp< LP > &mc_lp, std::vector< int > &vertex_to_part) -> detail::CostType< Graph >

template<typename Rand = std::default_random_engine, typename Distribution = std::uniform_real_distribution<double>, typename LP = lp::glp, typename Graph , typename OutputIterator , typename VertexIndexMap , typename EdgeWeightMap , typename VertexColorMap >
auto multiway_cut_dispatch (const Graph &graph, OutputIterator result, Rand &&random_engine, int iterations, VertexIndexMap index_map, EdgeWeightMap weight_map, VertexColorMap color_map) -> typename boost::property_traits< EdgeWeightMap >::value_type

template<typename Rand = std::default_random_engine, typename Distribution = std::uniform_real_distribution<double>, typename LP = lp::glp, typename Graph , typename OutputIterator , typename VertexIndexMap , typename EdgeWeightMap , typename VertexColorMap >
auto multiway_cut_dispatch (const Graph &graph, OutputIterator result, Rand &&random_engine, boost::param_not_found, VertexIndexMap index_map, EdgeWeightMap weight_map, VertexColorMap color_map) -> typename boost::property_traits< EdgeWeightMap >::value_type

template<typename Fun , typename Point >
auto call (Fun const &f, Point &&p, detail::lightweight_tag)

template<typename Function , typename Point >
auto call (hash_function_tuple< Function > const &f, Point &&p, detail::lightweight_tag tag)

template<typename InputRow , typename DestRow , typename Dummy >
void copy_row_to_matrix (InputRow &&input_row, DestRow &dest_matrix_row, Dummy, std::true_type)

template<typename InputRow , typename DestRow >
void copy_row_to_matrix (InputRow &&input_row, DestRow &dest_matrix_row, std::false_type, std::false_type)

template<typename InputRow , typename DestRow >
void copy_row_to_matrix (InputRow &&input_row, DestRow &dest_matrix_row, std::true_type, std::false_type)

template<typename InputRow , typename DestRow >
void copy_row_to_matrix (InputRow &&input_row, DestRow &dest_matrix_row)

template<typename Letter >
bool leq (Letter a1, int a2, Letter b1, int b2)
return true if pair (a1,a2) is smaller than pair (b1,b2) in lexicographic order and false otherwise More...

template<typename Letter >
bool leq (Letter a1, Letter a2, int a3, Letter b1, Letter b2, int b3)
return true if triple (a1,a2,a3) is smaller than triple (b1,b2,b3) in lexicographic order and false otherwise More...

template<typename Letter >
void suffix_array (std::vector< Letter > &text, std::vector< int > &SA, Letter max_letter)
require text[n]=text[n+1]=text[n+2]=0, n>=2 fill suffix_array suffix_array[i] contains the starting position of the i-1'th smallest suffix in Word More...

template<bool sign>
bool operator< (infinity<!sign >, infinity< sign >)

template<bool sign>
bool operator> (infinity< sign >, infinity<!sign >)

template<bool sign>
bool operator<= (infinity<!sign > left, infinity< sign > right)

template<bool sign>
bool operator>= (infinity<!sign > left, infinity< sign > right)

template<typename GetSize , typename GetValue , typename Objects , typename OutputIterator , typename Size = FunctorOnRangePValue<GetSize, Objects>>
knapsack_data< GetSize,
GetValue, Objects,
OutputIterator >
make_knapsack_data (Objects &&objects, Size capacity, GetSize get_size, GetValue get_value, OutputIterator &out)

template<typename RowsRange , typename RowRefExtractor >
void resize_rows (RowsRange &&rows, RowRefExtractor row_ref_extractor, std::size_t new_size)
resize rows to have equal sizes More...

## Detailed Description

Detail namespace.

## Function Documentation

template<typename KnapsackData , typename ReturnType = typename KnapsackData::return_type, typename Size = typename KnapsackData::size>
 ReturnType paal::detail::knapsack ( KnapsackData knap_data, unbounded_tag , integral_value_tag , retrieve_solution_tag )

Solution to the knapsack problem.

Template Parameters
 OutputIterator
Parameters
 objects given objects out the result is returned using output iterator size functor that for given object returns its size value functor that for given object returns its value

Definition at line 110 of file knapsack_unbounded.hpp.

template<typename KnapsackData >
 KnapsackData::return_type paal::detail::knapsack ( KnapsackData knap_data, unbounded_tag , integral_size_tag , retrieve_solution_tag )

Solution to the knapsack problem.

Template Parameters
 OutputIterator
Parameters
 oBegin given objects oEnd out the result is returned using output iterator size functor that for given object returns its size value functor that for given object returns its value

Definition at line 143 of file knapsack_unbounded.hpp.

template<typename Letter >
 bool paal::detail::leq ( Letter a1, int a2, Letter b1, int b2 )
inline

return true if pair (a1,a2) is smaller than pair (b1,b2) in lexicographic order and false otherwise

Parameters
 a1 a2 b1 b2
Template Parameters
 Letter

Definition at line 46 of file suffix_array.hpp.

template<typename Letter >
 bool paal::detail::leq ( Letter a1, Letter a2, int a3, Letter b1, Letter b2, int b3 )
inline

return true if triple (a1,a2,a3) is smaller than triple (b1,b2,b3) in lexicographic order and false otherwise

Parameters
 a1 a2 a3 b1 b2 b3
Template Parameters
 Letter

Definition at line 63 of file suffix_array.hpp.

template<typename RowsRange , typename RowRefExtractor >
 void paal::detail::resize_rows ( RowsRange && rows, RowRefExtractor row_ref_extractor, std::size_t new_size )

resize rows to have equal sizes

Template Parameters
 RowsRange RowRefExtractor
Parameters
 rows row_ref_extractor new_size

Definition at line 45 of file read_svm.hpp.

template<typename Letter >
 void paal::detail::suffix_array ( std::vector< Letter > & text, std::vector< int > & SA, Letter max_letter )

require text[n]=text[n+1]=text[n+2]=0, n>=2 fill suffix_array suffix_array[i] contains the starting position of the i-1'th smallest suffix in Word

Template Parameters
 Letter
Parameters
 text - text SA place for suffix_array max_letter optional parameter max_letter in alphabet

Definition at line 110 of file suffix_array.hpp.