All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
Namespaces | Functions
paal::greedy Namespace Reference

Greedy namespace. More...

Namespaces

 detail
 Detail of Greedy namespace.
 

Functions

template<typename Metric , class OutputIterator , typename ItemIterator >
data_structures::metric_traits
< Metric >::DistanceType 
kCenter (const Metric &metric, unsigned int numberOfClusters, const ItemIterator iBegin, const ItemIterator iEnd, OutputIterator result)
 this is solve K Center problem and return radius example:

#include <iostream>
#include <vector>
int main() {
// sample data
const int parts = 2;
m(0, 1) = 3;
m(0, 2) = 4;
m(1, 2) = 5;
m(1, 0) = 3;
m(2, 0) = 4;
m(2, 1) = 5;
auto vertices = paal::irange(3);
std::vector<int> centers;
// solution
std::cout << paal::greedy::kCenter(m, parts, vertices.begin(),
vertices.end(), back_inserter(centers))
<< std::endl;
}
More...
 
template<typename InGraph , class OutputIterator , typename VertexIndexMap , typename EdgeWeightMap >
auto k_cut (const InGraph &graph, unsigned int number_of_parts, OutputIterator result, VertexIndexMap index_map, EdgeWeightMap weight_map) -> typename boost::property_traits< EdgeWeightMap >::value_type
 this is solve k_cut problem and return cut_cost example:

#include <boost/graph/adjacency_list.hpp>
#include <iostream>
int main() {
// sample data
std::vector<std::pair<int,int>> edges_p {{1,2},{1,5},{2,3},{2,5},{2,6},
{3,4},{3,7},{4,7},{4,0},{5,6},{6,7},{7,0}};
std::vector<int> costs{2,3,3,2,2,4,2,2,2,3,1,3};
boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
boost::no_property,
boost::property<boost::edge_index_t, std::size_t>
> graph(8);
for (std::size_t i = 0; i < edges_p.size(); ++i) {
add_edge(edges_p[i].first, edges_p[i].second, i, graph);
}
const int parts = 3;
auto edge_id = get(boost::edge_index, graph);
auto weight = make_iterator_property_map(costs.begin(), edge_id);
// solve
int cost_cut;
std::vector<std::pair<int,int>> vertices_parts;
cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts),
boost::weight_map(weight));
// alternative form
// cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts));
// this works if the graph has and internal edge weight property map
// print result
std::cout << "cost cut:" << cost_cut << std::endl;
std::vector<int> vertices_to_parts;
for (auto i: vertices_parts) {
std::cout << i.first << "(" << i.second << "), ";
}
std::cout << std::endl;
}
More...
 
template<typename InGraph , class OutputIterator , typename T , typename P , typename R >
auto k_cut (const InGraph &graph, unsigned int number_of_parts, OutputIterator result, const boost::bgl_named_params< P, T, R > &params) -> typename boost::property_traits< puretype(boost::choose_const_pmap(get_param(params, boost::edge_weight), graph, boost::edge_weight)) >::value_type
 this is solve k_cut problem and return cut_cost example:

#include <boost/graph/adjacency_list.hpp>
#include <iostream>
int main() {
// sample data
std::vector<std::pair<int,int>> edges_p {{1,2},{1,5},{2,3},{2,5},{2,6},
{3,4},{3,7},{4,7},{4,0},{5,6},{6,7},{7,0}};
std::vector<int> costs{2,3,3,2,2,4,2,2,2,3,1,3};
boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
boost::no_property,
boost::property<boost::edge_index_t, std::size_t>
> graph(8);
for (std::size_t i = 0; i < edges_p.size(); ++i) {
add_edge(edges_p[i].first, edges_p[i].second, i, graph);
}
const int parts = 3;
auto edge_id = get(boost::edge_index, graph);
auto weight = make_iterator_property_map(costs.begin(), edge_id);
// solve
int cost_cut;
std::vector<std::pair<int,int>> vertices_parts;
cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts),
boost::weight_map(weight));
// alternative form
// cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts));
// this works if the graph has and internal edge weight property map
// print result
std::cout << "cost cut:" << cost_cut << std::endl;
std::vector<int> vertices_to_parts;
for (auto i: vertices_parts) {
std::cout << i.first << "(" << i.second << "), ";
}
std::cout << std::endl;
}
More...
 
template<typename InGraph , class OutputIterator >
auto k_cut (const InGraph &graph, unsigned int number_of_parts, OutputIterator result) -> typename boost::property_traits< puretype(get(boost::edge_weight, graph))>::value_type
 this is solve k_cut problem and return cut_cost example:

#include <boost/graph/adjacency_list.hpp>
#include <iostream>
int main() {
// sample data
std::vector<std::pair<int,int>> edges_p {{1,2},{1,5},{2,3},{2,5},{2,6},
{3,4},{3,7},{4,7},{4,0},{5,6},{6,7},{7,0}};
std::vector<int> costs{2,3,3,2,2,4,2,2,2,3,1,3};
boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
boost::no_property,
boost::property<boost::edge_index_t, std::size_t>
> graph(8);
for (std::size_t i = 0; i < edges_p.size(); ++i) {
add_edge(edges_p[i].first, edges_p[i].second, i, graph);
}
const int parts = 3;
auto edge_id = get(boost::edge_index, graph);
auto weight = make_iterator_property_map(costs.begin(), edge_id);
// solve
int cost_cut;
std::vector<std::pair<int,int>> vertices_parts;
cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts),
boost::weight_map(weight));
// alternative form
// cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts));
// this works if the graph has and internal edge weight property map
// print result
std::cout << "cost cut:" << cost_cut << std::endl;
std::vector<int> vertices_to_parts;
for (auto i: vertices_parts) {
std::cout << i.first << "(" << i.second << "), ";
}
std::cout << std::endl;
}
More...
 
template<class MachineIterator , class JobIterator , class OutputIterator , class GetSpeed , class GetLoad >
void schedule_deterministic (const MachineIterator mfirst, const MachineIterator mlast, const JobIterator jfirst, const JobIterator jlast, OutputIterator result, GetSpeed get_speed, GetLoad get_load)
 detail
 
template<class MachineIterator , class JobIterator , class OutputIterator , class GetSpeed , class GetLoad , class RandomNumberGenerator = std::default_random_engine>
void schedule_randomized (const MachineIterator mfirst, const MachineIterator mlast, const JobIterator jfirst, const JobIterator jlast, OutputIterator result, GetSpeed get_speed, GetLoad get_load, RandomNumberGenerator &&gen=std::default_random_engine(97345631u))
 
template<class InputIterator , class OutputIterator , class GetTime >
void scheduling_jobs_on_identical_parallel_machines (int n_machines, InputIterator first, InputIterator last, OutputIterator result, GetTime get_time)
 detail More...
 
template<class InputIterator , class OutputIterator , class GetTime , class GetDueDate , class GetReleaseDate >
auto scheduling_jobs_with_deadlines_on_a_single_machine (const InputIterator first, const InputIterator last, GetTime get_time, GetReleaseDate get_release_date, GetDueDate get_due_date, OutputIterator result)
 solve scheduling jobs on identical parallel machines problem and fill start time of all jobs example:

#include <iostream>
#include <utility>
int main() {
// sample data
typedef double Time;
std::vector<Time> time = { 2.1, 3.1, 4.1, 5.1, 6.1, 7.1, 8.1 };
std::vector<Time> release = { 1, 2, 3, 4, 5, 6, 7 };
std::vector<Time> due_date = { -1, 0, -2, -3, -4, -5, -6 };
auto jobs = paal::irange(time.size());
std::vector<std::pair<decltype(jobs)::iterator, Time>> jobs_to_start_dates;
Time delay =
jobs.begin(), jobs.end(), [&](int i) { return time[i]; },
[&](int i) { return release[i]; },
[&](int i) { return due_date[i]; },
back_inserter(jobs_to_start_dates));
for (auto job_start_time : jobs_to_start_dates) {
std::cout << "Job " << (*job_start_time.first)
<< " Start time: " << job_start_time.second << std::endl;
}
// print result
std::cout << "Solution: " << delay << std::endl;
return 0;
}

example file is scheduling_jobs_with_deadlines_on_a_single_machine_example.cpp More...

 
template<typename SetRange , class GetCostOfSet , class GetElementsOfSet , class OutputIterator , class ElementIndex , class Budget , class GetWeightOfElement = utils::return_one_functor>
auto budgeted_maximum_coverage (SetRange &&sets, GetCostOfSet set_to_cost, GetElementsOfSet set_to_elements, OutputIterator result, ElementIndex get_el_index, Budget budget, GetWeightOfElement element_to_weight=GetWeightOfElement(), const unsigned int initial_set_size=3)
 detail More...
 
template<typename SetRange , class GetElementsOfSet , class OutputIterator , class GetElementIndex , class GetWeightOfElement = paal::utils::return_one_functor>
auto maximum_coverage (SetRange &&sets, GetElementsOfSet set_to_elements, OutputIterator result, GetElementIndex get_el_index, unsigned int number_of_sets_to_select, GetWeightOfElement get_weight_of_element=GetWeightOfElement{})
 this is solve Set Cover problem and return set cover cost example:

#include <iostream>
#include <vector>
#include <iterator>
#include <boost/range/irange.hpp>
int main() {
std::vector<std::vector<int>> set_to_elements = {
{ 1, 2 },
{ 3, 4, 5, 6 },
{ 7, 8, 9, 10, 11, 12, 13, 0 },
{ 1, 3, 5, 7, 9, 11, 13 },
{ 2, 4, 6, 8, 10, 12, 0 }
};
std::vector<int> costs = { 1, 1, 1, 1, 1 };
auto sets = boost::irange(0, 5);
std::vector<int> result;
auto element_index = [](int el){return el;};
auto cost = paal::greedy::set_cover(sets,
[&](int set){return costs[set];},
[&](int set){return set_to_elements[set];},
back_inserter(result),
element_index);
std::cout << "Cost: " << cost << std::endl;
}
More...
 
template<typename SetRange , class GetCostOfSet , class GetElementsOfSet , class OutputIterator , class GetElementIndex >
auto set_cover (SetRange &&sets, GetCostOfSet set_to_cost, GetElementsOfSet set_to_elements, OutputIterator result, GetElementIndex get_el_index)
 detail More...
 
template<typename Words >
auto shortestSuperstring (const Words &words) -> decltype(std::declval< detail::shortest_superstring< Words >>().get_solution())
 detail More...
 

Detailed Description

Greedy namespace.

Function Documentation

template<typename SetRange , class GetCostOfSet , class GetElementsOfSet , class OutputIterator , class ElementIndex , class Budget , class GetWeightOfElement = utils::return_one_functor>
auto paal::greedy::budgeted_maximum_coverage ( SetRange &&  sets,
GetCostOfSet  set_to_cost,
GetElementsOfSet  set_to_elements,
OutputIterator  result,
ElementIndex  get_el_index,
Budget  budget,
GetWeightOfElement  element_to_weight = GetWeightOfElement(),
const unsigned int  initial_set_size = 3 
)

detail

this is solve Set Cover problem and return set cover cost example:

#include <iostream>
#include <vector>
#include <iterator>
#include <boost/range/irange.hpp>
int main() {
std::vector<std::vector<int>> set_to_elements = {
{ 1, 2 },
{ 3, 4, 5, 6 },
{ 7, 8, 9, 10, 11, 12, 13, 0 },
{ 1, 3, 5, 7, 9, 11, 13 },
{ 2, 4, 6, 8, 10, 12, 0 }
};
std::vector<int> costs = { 1, 1, 1, 1, 1 };
auto sets = boost::irange(0, 5);
std::vector<int> result;
auto element_index = [](int el){return el;};
auto cost = paal::greedy::set_cover(sets,
[&](int set){return costs[set];},
[&](int set){return set_to_elements[set];},
back_inserter(result),
element_index);
std::cout << "Cost: " << cost << std::endl;
}

complete example is set_cover_example.cpp

Parameters
sets
set_to_cost
set_to_elements
resultset iterators of chosen sets
get_el_index
budget
element_to_weight
initial_set_size
Template Parameters
SetRange
GetCostOfSet
GetElementsOfSet
OutputIterator
ElementIndex
Budget
GetWeightOfElement

Definition at line 264 of file budgeted_maximum_coverage.hpp.

template<typename InGraph , class OutputIterator , typename VertexIndexMap , typename EdgeWeightMap >
auto paal::greedy::k_cut ( const InGraph &  graph,
unsigned int  number_of_parts,
OutputIterator  result,
VertexIndexMap  index_map,
EdgeWeightMap  weight_map 
) -> typename boost::property_traits<EdgeWeightMap>::value_type

this is solve k_cut problem and return cut_cost example:

#include <boost/graph/adjacency_list.hpp>
#include <iostream>
int main() {
// sample data
std::vector<std::pair<int,int>> edges_p {{1,2},{1,5},{2,3},{2,5},{2,6},
{3,4},{3,7},{4,7},{4,0},{5,6},{6,7},{7,0}};
std::vector<int> costs{2,3,3,2,2,4,2,2,2,3,1,3};
boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
boost::no_property,
boost::property<boost::edge_index_t, std::size_t>
> graph(8);
for (std::size_t i = 0; i < edges_p.size(); ++i) {
add_edge(edges_p[i].first, edges_p[i].second, i, graph);
}
const int parts = 3;
auto edge_id = get(boost::edge_index, graph);
auto weight = make_iterator_property_map(costs.begin(), edge_id);
// solve
int cost_cut;
std::vector<std::pair<int,int>> vertices_parts;
cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts),
boost::weight_map(weight));
// alternative form
// cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts));
// this works if the graph has and internal edge weight property map
// print result
std::cout << "cost cut:" << cost_cut << std::endl;
std::vector<int> vertices_to_parts;
for (auto i: vertices_parts) {
std::cout << i.first << "(" << i.second << "), ";
}
std::cout << std::endl;
}

example file is k_cut_example.cpp

Parameters
graph
number_of_parts
resultpairs of vertex_descriptor and number form (1,2, ... ,k) id of part
index_map
weight_map
Template Parameters
InGraph
OutputIterator
VertexIndexMap
EdgeWeightMap

Definition at line 54 of file k_cut.hpp.

template<typename InGraph , class OutputIterator , typename T , typename P , typename R >
auto paal::greedy::k_cut ( const InGraph &  graph,
unsigned int  number_of_parts,
OutputIterator  result,
const boost::bgl_named_params< P, T, R > &  params 
) -> typename boost::property_traits< puretype(boost::choose_const_pmap(get_param(params, boost::edge_weight), graph, boost::edge_weight)) >::value_type

this is solve k_cut problem and return cut_cost example:

#include <boost/graph/adjacency_list.hpp>
#include <iostream>
int main() {
// sample data
std::vector<std::pair<int,int>> edges_p {{1,2},{1,5},{2,3},{2,5},{2,6},
{3,4},{3,7},{4,7},{4,0},{5,6},{6,7},{7,0}};
std::vector<int> costs{2,3,3,2,2,4,2,2,2,3,1,3};
boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
boost::no_property,
boost::property<boost::edge_index_t, std::size_t>
> graph(8);
for (std::size_t i = 0; i < edges_p.size(); ++i) {
add_edge(edges_p[i].first, edges_p[i].second, i, graph);
}
const int parts = 3;
auto edge_id = get(boost::edge_index, graph);
auto weight = make_iterator_property_map(costs.begin(), edge_id);
// solve
int cost_cut;
std::vector<std::pair<int,int>> vertices_parts;
cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts),
boost::weight_map(weight));
// alternative form
// cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts));
// this works if the graph has and internal edge weight property map
// print result
std::cout << "cost cut:" << cost_cut << std::endl;
std::vector<int> vertices_to_parts;
for (auto i: vertices_parts) {
std::cout << i.first << "(" << i.second << "), ";
}
std::cout << std::endl;
}

example file is k_cut_example.cpp

Parameters
graph
number_of_parts
resultpairs of vertex_descriptor and number form (1,2, ... ,k) id of part
params
Template Parameters
InGraph
OutputIterator
T
P
R

Definition at line 174 of file k_cut.hpp.

template<typename InGraph , class OutputIterator >
auto paal::greedy::k_cut ( const InGraph &  graph,
unsigned int  number_of_parts,
OutputIterator  result 
) -> typename boost::property_traits<puretype(get(boost::edge_weight,graph))>::value_type

this is solve k_cut problem and return cut_cost example:

#include <boost/graph/adjacency_list.hpp>
#include <iostream>
int main() {
// sample data
std::vector<std::pair<int,int>> edges_p {{1,2},{1,5},{2,3},{2,5},{2,6},
{3,4},{3,7},{4,7},{4,0},{5,6},{6,7},{7,0}};
std::vector<int> costs{2,3,3,2,2,4,2,2,2,3,1,3};
boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
boost::no_property,
boost::property<boost::edge_index_t, std::size_t>
> graph(8);
for (std::size_t i = 0; i < edges_p.size(); ++i) {
add_edge(edges_p[i].first, edges_p[i].second, i, graph);
}
const int parts = 3;
auto edge_id = get(boost::edge_index, graph);
auto weight = make_iterator_property_map(costs.begin(), edge_id);
// solve
int cost_cut;
std::vector<std::pair<int,int>> vertices_parts;
cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts),
boost::weight_map(weight));
// alternative form
// cost_cut = paal::greedy::k_cut(graph, parts, back_inserter(vertices_parts));
// this works if the graph has and internal edge weight property map
// print result
std::cout << "cost cut:" << cost_cut << std::endl;
std::vector<int> vertices_to_parts;
for (auto i: vertices_parts) {
std::cout << i.first << "(" << i.second << "), ";
}
std::cout << std::endl;
}

example file is k_cut_example.cpp

Parameters
graph
number_of_parts
resultpairs of vertex_descriptor and number form (1,2, ... ,k) id of part
Template Parameters
InGraph
OutputIterator

Definition at line 199 of file k_cut.hpp.

template<typename Metric , class OutputIterator , typename ItemIterator >
data_structures::metric_traits<Metric>::DistanceType paal::greedy::kCenter ( const Metric &  metric,
unsigned int  numberOfClusters,
const ItemIterator  iBegin,
const ItemIterator  iEnd,
OutputIterator  result 
)

this is solve K Center problem and return radius example:

#include <iostream>
#include <vector>
int main() {
// sample data
const int parts = 2;
m(0, 1) = 3;
m(0, 2) = 4;
m(1, 2) = 5;
m(1, 0) = 3;
m(2, 0) = 4;
m(2, 1) = 5;
auto vertices = paal::irange(3);
std::vector<int> centers;
// solution
std::cout << paal::greedy::kCenter(m, parts, vertices.begin(),
vertices.end(), back_inserter(centers))
<< std::endl;
}

example file is k_center_example.cpp

Parameters
metric
numberOfClusters
resultItemIterators
iBegin
iEnd
Template Parameters
array_metric
OutputIterator
ItemIterator

Definition at line 43 of file k_center.hpp.

template<typename SetRange , class GetElementsOfSet , class OutputIterator , class GetElementIndex , class GetWeightOfElement = paal::utils::return_one_functor>
auto paal::greedy::maximum_coverage ( SetRange &&  sets,
GetElementsOfSet  set_to_elements,
OutputIterator  result,
GetElementIndex  get_el_index,
unsigned int  number_of_sets_to_select,
GetWeightOfElement  get_weight_of_element = GetWeightOfElement{} 
)

this is solve Set Cover problem and return set cover cost example:

#include <iostream>
#include <vector>
#include <iterator>
#include <boost/range/irange.hpp>
int main() {
std::vector<std::vector<int>> set_to_elements = {
{ 1, 2 },
{ 3, 4, 5, 6 },
{ 7, 8, 9, 10, 11, 12, 13, 0 },
{ 1, 3, 5, 7, 9, 11, 13 },
{ 2, 4, 6, 8, 10, 12, 0 }
};
std::vector<int> costs = { 1, 1, 1, 1, 1 };
auto sets = boost::irange(0, 5);
std::vector<int> result;
auto element_index = [](int el){return el;};
auto cost = paal::greedy::set_cover(sets,
[&](int set){return costs[set];},
[&](int set){return set_to_elements[set];},
back_inserter(result),
element_index);
std::cout << "Cost: " << cost << std::endl;
}

complete example is set_cover_example.cpp

Parameters
sets
set_to_elements
resultset iterators of chosen sets
get_el_index
number_of_sets_to_select
get_weight_of_element
Template Parameters
SetRange
GetElementsOfSet
OutputIterator
GetElementIndex
GetWeightOfElement

Definition at line 38 of file maximum_coverage.hpp.

template<class InputIterator , class OutputIterator , class GetTime >
void paal::greedy::scheduling_jobs_on_identical_parallel_machines ( int  n_machines,
InputIterator  first,
InputIterator  last,
OutputIterator  result,
GetTime  get_time 
)

detail

this is solve scheduling jobs on identical parallel machines problem and return schedule example:

#include <iostream>
#include <utility>
int main() {
typedef double Time;
typedef std::pair<Time, char> Job;
auto returnJobTimeFunctor = [](Job job) { return job.first; };
// sample data
int numberOfMachines = 3;
std::vector<Job> jobs = { { 2.1, 'a' },
{ 3.1, 'b' },
{ 4.1, 'c' },
{ 5.1, 'd' },
{ 6.1, 'e' },
{ 7.1, 'f' },
{ 8.1, 'g' } };
std::vector<std::pair<int, decltype(jobs)::iterator>> result;
numberOfMachines, jobs.begin(), jobs.end(), back_inserter(result),
returnJobTimeFunctor);
std::vector<Time> sumOfMachine;
sumOfMachine.resize(numberOfMachines);
for (auto machineJobPair : result) {
auto machine = machineJobPair.first;
auto job = machineJobPair.second;
sumOfMachine[machine] += job->first;
std::cout << "On machine: " << machine << " do job: " << job->second
<< std::endl;
}
Time maximumLoad =
*std::max_element(sumOfMachine.begin(), sumOfMachine.end());
// print result
std::cout << "Solution:" << maximumLoad << std::endl;
return 0;
}

example file is scheduling_jobs_on_identical_parallel_machines_example.cpp

Parameters
n_machines
first
last
result
get_time

Definition at line 58 of file scheduling_jobs_on_identical_parallel_machines.hpp.

template<class InputIterator , class OutputIterator , class GetTime , class GetDueDate , class GetReleaseDate >
auto paal::greedy::scheduling_jobs_with_deadlines_on_a_single_machine ( const InputIterator  first,
const InputIterator  last,
GetTime  get_time,
GetReleaseDate  get_release_date,
GetDueDate  get_due_date,
OutputIterator  result 
)

solve scheduling jobs on identical parallel machines problem and fill start time of all jobs example:

#include <iostream>
#include <utility>
int main() {
// sample data
typedef double Time;
std::vector<Time> time = { 2.1, 3.1, 4.1, 5.1, 6.1, 7.1, 8.1 };
std::vector<Time> release = { 1, 2, 3, 4, 5, 6, 7 };
std::vector<Time> due_date = { -1, 0, -2, -3, -4, -5, -6 };
auto jobs = paal::irange(time.size());
std::vector<std::pair<decltype(jobs)::iterator, Time>> jobs_to_start_dates;
Time delay =
jobs.begin(), jobs.end(), [&](int i) { return time[i]; },
[&](int i) { return release[i]; },
[&](int i) { return due_date[i]; },
back_inserter(jobs_to_start_dates));
for (auto job_start_time : jobs_to_start_dates) {
std::cout << "Job " << (*job_start_time.first)
<< " Start time: " << job_start_time.second << std::endl;
}
// print result
std::cout << "Solution: " << delay << std::endl;
return 0;
}

example file is scheduling_jobs_with_deadlines_on_a_single_machine_example.cpp

Parameters
first- jobs begin
last- jobs end
get_time
get_release_date
get_due_date
result
Template Parameters
Time
InputIterator
OutputIterator
GetTime
GetDueDate
GetReleaseDate

Definition at line 55 of file scheduling_jobs_with_deadlines_on_a_single_machine.hpp.

template<typename SetRange , class GetCostOfSet , class GetElementsOfSet , class OutputIterator , class GetElementIndex >
auto paal::greedy::set_cover ( SetRange &&  sets,
GetCostOfSet  set_to_cost,
GetElementsOfSet  set_to_elements,
OutputIterator  result,
GetElementIndex  get_el_index 
)

detail

this is solve Set Cover problem and return set cover cost example:

#include <iostream>
#include <vector>
#include <iterator>
#include <boost/range/irange.hpp>
int main() {
std::vector<std::vector<int>> set_to_elements = {
{ 1, 2 },
{ 3, 4, 5, 6 },
{ 7, 8, 9, 10, 11, 12, 13, 0 },
{ 1, 3, 5, 7, 9, 11, 13 },
{ 2, 4, 6, 8, 10, 12, 0 }
};
std::vector<int> costs = { 1, 1, 1, 1, 1 };
auto sets = boost::irange(0, 5);
std::vector<int> result;
auto element_index = [](int el){return el;};
auto cost = paal::greedy::set_cover(sets,
[&](int set){return costs[set];},
[&](int set){return set_to_elements[set];},
back_inserter(result),
element_index);
std::cout << "Cost: " << cost << std::endl;
}

complete example is set_cover_example.cpp

Parameters
sets
set_to_cost
set_to_elements
resultset iterators of chosen sets
get_el_index
Template Parameters
SetRange
GetCostOfSet
GetElementsOfSet
OutputIterator
GetElementIndex

Definition at line 48 of file set_cover.hpp.

template<typename Words >
auto paal::greedy::shortestSuperstring ( const Words &  words) -> decltype( std::declval<detail::shortest_superstring<Words>>().get_solution())

detail

Parameters
wordsreturn word contains all words as subwords, of lenght at most 3.5 larger than shortest superstring. words canot contains letter 0
#include <iostream>
#include <string>
int main() {
std::vector<std::string> words({ "ba", "ab", "aa", "bb" });
std::cout << paal::greedy::shortestSuperstring(words) << std::endl;
}
example file is shortest_superstring_example.cpp
Template Parameters
Words

Definition at line 233 of file shortest_superstring.hpp.