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 "paal/greedy/k_center/k_center.hpp"
#include "paal/utils/irange.hpp"
#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;
}
| |
| 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 "paal/greedy/k_cut/k_cut.hpp"
#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;
}
| |
| 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 > ¶ms) -> 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 "paal/greedy/k_cut/k_cut.hpp"
#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;
}
| |
| 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 "paal/greedy/k_cut/k_cut.hpp"
#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;
}
| |
| 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 "paal/utils/irange.hpp"
#include <iostream>
#include <utility>
int main() {
// sample data
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>
#include "paal/greedy/set_cover/set_cover.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;
}
| |
| 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... | |
Greedy namespace.
| 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:
complete example is set_cover_example.cpp
| sets | |
| set_to_cost | |
| set_to_elements | |
| result | set iterators of chosen sets |
| get_el_index | |
| budget | |
| element_to_weight | |
| initial_set_size |
| SetRange | |
| GetCostOfSet | |
| GetElementsOfSet | |
| OutputIterator | |
| ElementIndex | |
| Budget | |
| GetWeightOfElement |
Definition at line 264 of file budgeted_maximum_coverage.hpp.
| 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:
example file is k_cut_example.cpp
| graph | |
| number_of_parts | |
| result | pairs of vertex_descriptor and number form (1,2, ... ,k) id of part |
| index_map | |
| weight_map |
| InGraph | |
| OutputIterator | |
| VertexIndexMap | |
| EdgeWeightMap |
| 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:
example file is k_cut_example.cpp
| graph | |
| number_of_parts | |
| result | pairs of vertex_descriptor and number form (1,2, ... ,k) id of part |
| params |
| InGraph | |
| OutputIterator | |
| T | |
| P | |
| R |
| 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:
example file is k_cut_example.cpp
| graph | |
| number_of_parts | |
| result | pairs of vertex_descriptor and number form (1,2, ... ,k) id of part |
| InGraph | |
| OutputIterator |
| 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:
example file is k_center_example.cpp
| metric | |
| numberOfClusters | |
| result | ItemIterators |
| iBegin | |
| iEnd |
| array_metric | |
| OutputIterator | |
| ItemIterator |
Definition at line 43 of file k_center.hpp.
| 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:
complete example is set_cover_example.cpp
| sets | |
| set_to_elements | |
| result | set iterators of chosen sets |
| get_el_index | |
| number_of_sets_to_select | |
| get_weight_of_element |
| SetRange | |
| GetElementsOfSet | |
| OutputIterator | |
| GetElementIndex | |
| GetWeightOfElement |
Definition at line 38 of file maximum_coverage.hpp.
| 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:
example file is scheduling_jobs_on_identical_parallel_machines_example.cpp
| n_machines | |
| first | |
| last | |
| result | |
| get_time |
Definition at line 58 of file scheduling_jobs_on_identical_parallel_machines.hpp.
| 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:
example file is scheduling_jobs_with_deadlines_on_a_single_machine_example.cpp
| first | - jobs begin |
| last | - jobs end |
| get_time | |
| get_release_date | |
| get_due_date | |
| result |
| Time | |
| InputIterator | |
| OutputIterator | |
| GetTime | |
| GetDueDate | |
| GetReleaseDate |
Definition at line 55 of file scheduling_jobs_with_deadlines_on_a_single_machine.hpp.
| 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:
complete example is set_cover_example.cpp
| sets | |
| set_to_cost | |
| set_to_elements | |
| result | set iterators of chosen sets |
| get_el_index |
| SetRange | |
| GetCostOfSet | |
| GetElementsOfSet | |
| OutputIterator | |
| GetElementIndex |
Definition at line 48 of file set_cover.hpp.
| auto paal::greedy::shortestSuperstring | ( | const Words & | words | ) | -> decltype( std::declval<detail::shortest_superstring<Words>>().get_solution()) |
detail
| words | return 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;
}
|
| Words |
Definition at line 233 of file shortest_superstring.hpp.
1.8.5
