#include "paal/utils/functors.hpp"#include "paal/utils/type_functions.hpp"#include "paal/utils/irange.hpp"#include <boost/graph/adjacency_list.hpp>#include <boost/graph/copy.hpp>#include <boost/graph/iteration_macros.hpp>#include <boost/graph/one_bit_color_map.hpp>#include <boost/graph/stoer_wagner_min_cut.hpp>#include <boost/graph/subgraph.hpp>#include <boost/range/as_array.hpp>#include <queue>Go to the source code of this file.
Namespaces | |
| paal | |
| global namespace of project. | |
| paal::greedy | |
| Greedy namespace. | |
Functions | |
| 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 "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 | paal::greedy::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 | 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 "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;
}
| |
1.8.5