All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
Classes | Typedefs | Functions
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
 
struct  radix_pass
 
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
objectsgiven objects
outthe result is returned using output iterator
sizefunctor that for given object returns its size
valuefunctor 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
oBegingiven objects
oEnd
outthe result is returned using output iterator
sizefunctor that for given object returns its size
valuefunctor 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
SAplace for suffix_array
max_letteroptional parameter max_letter in alphabet

Definition at line 110 of file suffix_array.hpp.

Generated on Tue Jan 31 2017 00:31:03 by   doxygen 1.8.5