All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
prune_restrictions_to_tree.hpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c) 2013 Piotr Wygocki
3 //
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
15 #ifndef PAAL_PRUNE_RESTRICTIONS_TO_TREE_HPP
16 #define PAAL_PRUNE_RESTRICTIONS_TO_TREE_HPP
17 
18 #include "paal/utils/functors.hpp"
19 #include "paal/utils/irange.hpp"
20 
21 #include <boost/function_output_iterator.hpp>
22 #include <boost/graph/adjacency_list.hpp>
23 #include <boost/graph/kruskal_min_spanning_tree.hpp>
24 
25 namespace paal {
26 
27 using RestrictionsVector = std::vector<std::pair<unsigned, unsigned>>;
28 
40 template <typename Restrictions>
41 RestrictionsVector prune_restrictions_to_tree(Restrictions res, int N) {
42  using Dist = decltype(std::declval<Restrictions>()(0, 0));
43  using EdgeProp = boost::property<boost::edge_weight_t, Dist>;
44  using TGraph =
45  boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS,
46  boost::no_property, EdgeProp>;
47  using Edge = typename boost::graph_traits<TGraph>::edge_descriptor;
48 
49  RestrictionsVector res_vec;
50  TGraph g(N);
51  for (auto i : irange(N)) {
52  for (auto j : irange(i + 1, N)) {
53  add_edge(i, j, EdgeProp(-std::max(res(i, j), res(j, i))), g);
54  }
55  }
56 
57  auto add_edge_to_graph = [&](Edge e) {
58  res_vec.push_back(std::make_pair(source(e, g), target(e, g)));
59  };
60 
61  boost::kruskal_minimum_spanning_tree(
62  g, boost::make_function_output_iterator(
63  utils::make_assignable_functor(add_edge_to_graph)));
64  return res_vec;
65 }
66 }
67 
68 #endif // PAAL_PRUNE_RESTRICTIONS_TO_TREE_HPP
auto irange(T begin, T end)
irange
Definition: irange.hpp:22
auto make_assignable_functor(Functor &f)
make function for assignable_functor
Definition: functors.hpp:421
This file contains set of simple useful functors or functor adapters.
RestrictionsVector prune_restrictions_to_tree(Restrictions res, int N)
Returns a list of restrictions, made of the edges of a maximum spanning tree in a clique with edge we...