#include "paal/lp/glp.hpp"#include "paal/utils/type_functions.hpp"#include "paal/utils/irange.hpp"#include "paal/utils/assign_updates.hpp"#include <boost/bimap.hpp>#include <boost/graph/breadth_first_search.hpp>#include <boost/graph/connected_components.hpp>#include <boost/graph/filtered_graph.hpp>#include <boost/graph/graph_traits.hpp>#include <boost/graph/graph_utility.hpp>#include <boost/graph/named_function_params.hpp>#include <boost/graph/stoer_wagner_min_cut.hpp>#include <boost/property_map/property_map.hpp>#include <boost/range/as_array.hpp>#include <fstream>#include <tuple>#include <utility>#include <vector>#include <random>Go to the source code of this file.
Classes | |
| class | paal::detail::multiway_cut_lp< LP > |
Namespaces | |
| paal | |
| global namespace of project. | |
| paal::detail | |
| Detail namespace. | |
Typedefs | |
| template<class Graph > | |
| using | paal::detail::CostType = typename boost::property_traits< puretype(get(boost::edge_weight, std::declval< Graph >()))>::value_type |
Functions | |
| int | paal::detail::vertices_column_index (int vertex, int dimentions, int column) |
| template<typename Graph , typename VertexIndexMap , typename EdgeWeightMap , typename Dist , typename Rand , typename LP > | |
| auto | paal::detail::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 | paal::detail::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 | paal::detail::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 Rand = std::default_random_engine, typename Distribution = std::uniform_real_distribution<double>, typename LP = lp::glp, typename Graph , typename OutputIterator , typename P , typename T , typename R > | |
| auto | paal::multiway_cut (const Graph &g, OutputIterator out, const boost::bgl_named_params< P, T, R > ¶ms, Rand &&random_engine=std::default_random_engine(5426u)) -> typename boost::property_traits< puretype(boost::choose_const_pmap(get_param(params, boost::edge_weight), g, boost::edge_weight))>::value_type |
| detail More... | |
| template<typename Rand = std::default_random_engine, typename Distribution = std::uniform_real_distribution<double>, typename LP = lp::glp, typename Graph , class OutputIterator > | |
| auto | paal::multiway_cut (const Graph &graph, OutputIterator result, Rand random_engine=std::default_random_engine(5426u)) -> detail::CostType< Graph > |
| this is solve multiway_cut problem and return cut_cost example:
#include "paal/multiway_cut/multiway_cut.hpp"
#include <boost/graph/adjacency_list.hpp>
int main() {
// sample data
std::vector<std::pair<int,int>> edges_p{{0,3},{1,3},
{0,4},{2,4},
{1,5},{2,5},
{3,6},{4,6},
{3,7},{5,7},
{4,8},{5,8},
{6,7},{6,8},{7,8}
};
const int vertices_num = 9;
std::vector<int> cost_edges{100,100,100,100,100,100,10,10,10,10,10,10,1,1,1};
std::vector<int> terminals = { 0, 1, 2 };
boost::adjacency_list<
boost::vecS, boost::vecS, boost::undirectedS,
boost::property<boost::vertex_index_t, int,
boost::property<boost::vertex_color_t, int>>,
boost::property<boost::edge_weight_t, int>
> graph(edges_p.begin(), edges_p.end(), cost_edges.begin(), vertices_num);
for (std::size_t i = 1; i <= terminals.size(); ++i) {
put(boost::vertex_color, graph, terminals[i - 1], i);
}
//solve
std::vector<std::pair<int,int>> vertices_parts;
auto cost_cut = paal::multiway_cut(graph, back_inserter(vertices_parts));
//print result
std::cout << "cost cut: " << cost_cut << std::endl;
std::cout << "vertices (part)" << std::endl;
for(auto i: vertices_parts) {
std::cout << " " << i.first << " ( " << i.second << " )" << std::endl;
}
paal::lp::glp::free_env();
}
| |
1.8.5