All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
tree_augmentation.hpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c) 2013 Attila Bernath, Piotr Wygocki
3 // 2014 Piotr Godlewski, Piotr Smulewicz
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_TREE_AUGMENTATION_HPP
16 #define PAAL_TREE_AUGMENTATION_HPP
17 
18 
21 #include "paal/utils/hash.hpp"
22 
23 #include <boost/bimap.hpp>
24 #include <boost/graph/breadth_first_search.hpp>
25 #include <boost/graph/connected_components.hpp>
26 #include <boost/graph/filtered_graph.hpp>
27 #include <boost/graph/graph_traits.hpp>
28 #include <boost/graph/graph_utility.hpp>
29 #include <boost/graph/named_function_params.hpp>
30 #include <boost/graph/stoer_wagner_min_cut.hpp>
31 #include <boost/property_map/property_map.hpp>
32 #include <boost/range/as_array.hpp>
33 #include <boost/range/distance.hpp>
34 
35 #include <algorithm>
36 #include <utility>
37 
38 namespace paal {
39 namespace ir {
40 
41 namespace detail {
42 
47 template <class EdgeListGraph>
48 int filtered_num_edges(const EdgeListGraph & g) {
49  return boost::distance(edges(g));
50 }
51 
57 template <typename EdgeBoolMap> struct bool_map_to_tree_filter {
59 
60  bool_map_to_tree_filter(EdgeBoolMap m) : ebmap(m) {}
61 
62  template <typename Edge> bool operator()(const Edge &e) const {
63  return get(ebmap, e);
64  }
65 
66  EdgeBoolMap ebmap;
67 };
68 
69 template <typename EdgeBoolMap> struct bool_map_to_non_tree_filter {
71 
72  bool_map_to_non_tree_filter(EdgeBoolMap m) : ebmap(m) {}
73 
74  template <typename Edge> bool operator()(const Edge &e) const {
75  return !get(ebmap, e);
76  }
77 
78  EdgeBoolMap ebmap;
79 };
80 
82 template <typename KeyType, int num>
84  : public boost::put_get_helper<int, const_int_map<KeyType, num>> {
85  public:
86  using category = boost::readable_property_map_tag;
87  using value_type = int;
88  using reference = int;
89  using key_type = KeyType;
90  reference operator[](KeyType e) const { return num; }
91 };
92 
93 } // namespace detail
94 
95 namespace {
96 struct ta_compare_traits {
97  static const double EPSILON;
98 };
99 
100 const double ta_compare_traits::EPSILON = 1e-10;
101 }
102 
110  ta_round_condition(double epsilon = ta_compare_traits::EPSILON)
111  : m_round_half(epsilon) {}
112 
118  template <typename Problem, typename LP>
119  boost::optional<double> operator()(Problem &problem, LP &lp,
120  lp::col_id col) {
121  auto res = m_round_half(problem, lp, col);
122  if (res) {
123  problem.add_to_solution(col);
124  }
125  return res;
126  }
127 
128  private:
130 };
131 
139  ta_set_solution(double epsilon = ta_compare_traits::EPSILON)
140  : m_compare(epsilon) {}
141 
146  template <typename Problem, typename GetSolution>
147  void operator()(Problem &problem, const GetSolution &solution) {
148  for (auto e :
149  boost::as_array(edges(problem.get_links_graph()))) {
150  if (!problem.is_in_solution(e)) {
151  auto col = problem.edge_to_col(e);
152  if (m_compare.e(solution(col), 1)) {
153  problem.add_to_solution(col);
154  }
155  }
156  }
157  }
158 
159 private:
160  const utils::compare<double> m_compare;
161 };
162 
166 class ta_init {
167  public:
171  template <typename Problem, typename LP>
172  void operator()(Problem &problem, LP &lp) {
173  problem.init();
174  lp.set_lp_name("Tree augmentation");
175  lp.set_optimization_type(lp::MINIMIZE);
176 
177  add_variables(problem, lp);
178  add_cut_constraints(problem, lp);
179  }
180 
181  private:
186  template <typename Problem, typename LP>
187  void add_variables(Problem & problem, LP & lp) {
188  for (auto e : boost::as_array(edges(problem.get_links_graph()))) {
189  lp::col_id col_idx = lp.add_column(problem.get_cost(e), 0);
190  problem.bind_edge_to_col(e, col_idx);
191  }
192  }
193 
198  template <typename Problem, typename LP>
199  void add_cut_constraints(Problem &problem, LP &lp) {
200  for (auto e :
201  boost::as_array(edges(problem.get_tree_graph()))) {
202  lp::linear_expression expr;
203  for (auto pe : problem.get_covered_by(e)) {
204  expr += problem.edge_to_col(pe);
205  }
206 
207  lp::row_id row_idx = lp.add_row(std::move(expr) >= 1);
208  problem.bind_edge_to_row(e, row_idx);
209  }
210  }
211 };
212 
213 template <
214  typename Init = ta_init,
215  typename RoundCondition = ta_round_condition,
216  typename RelaxContition = utils::always_false,
217  typename SetSolution = ta_set_solution>
218  using tree_augmentation_ir_components = IRcomponents<Init, RoundCondition,
219  RelaxContition, SetSolution>;
220 
240 template <typename Graph, typename TreeMap, typename CostMap,
241  typename VertexIndex, typename EdgeSetOutputIterator>
242 class tree_aug {
243  public:
244  using Edge = typename boost::graph_traits<Graph>::edge_descriptor;
245  using Vertex = typename boost::graph_traits<Graph>::vertex_descriptor;
246  using CostValue = double;
247 
248  using TreeGraph =
249  boost::filtered_graph<Graph, detail::bool_map_to_tree_filter<TreeMap>>;
250  using NonTreeGraph = boost::filtered_graph<
252 
253  using EdgeList = std::vector<Edge>;
254  using CoverMap = std::unordered_map<Edge, EdgeList, edge_hash<Graph>>;
255 
256  // cross reference between links and columns
257  using EdgeToColId = boost::bimap<Edge, lp::col_id>;
258  using RowIdToEdge = std::unordered_map<lp::row_id, Edge>;
259 
260  using ErrorMessage = boost::optional<std::string>;
261 
271  tree_aug(const Graph & g, TreeMap tree_map, CostMap cost_map,
272  VertexIndex vertex_index, EdgeSetOutputIterator solution) :
273  m_g(g), m_tree_map(tree_map), m_cost_map(cost_map), m_index(vertex_index),
274  m_solution(solution),
275  m_tree(m_g, detail::bool_map_to_tree_filter<TreeMap>(m_tree_map)),
276  m_ntree(m_g, detail::bool_map_to_non_tree_filter<TreeMap>(m_tree_map)),
277  m_sol_cost(0)
278  {}
279 
281  ErrorMessage check_input_validity() {
282  // Num of edges == num of nodes-1 in the tree?
283  int n_v = num_vertices(m_g);
284  int n_e = filtered_num_edges(m_tree);
285 
286  if (n_e != n_v - 1) {
287  return "Incorrect number of edges in the spanning tree. "
288  + std::string("Should be ") + std::to_string(n_v - 1)
289  + ", but it is " + std::to_string(n_e) + ".";
290  }
291 
292  // Is the tree connected?
293  std::vector<int> component(num_vertices(m_g));
294  int num = boost::connected_components(m_tree, &component[0]);
295  if (num > 1) {
296  return ErrorMessage{ "The spanning tree is not connected." };
297  }
298 
299  // Is the graph 2-edge-connected?
300  detail::const_int_map<Edge, 1> const_1_edge_map;
301  // TODO This stoer-wagner algorithm is unnecessarily slow for some reason
302  int min_cut = boost::stoer_wagner_min_cut(m_g, const_1_edge_map);
303  if (min_cut < 2) {
304  return ErrorMessage{"The graph is not 2-edge-connected."};
305  }
306 
307  return ErrorMessage{};
308  }
309 
313  const NonTreeGraph &get_links_graph() const { return m_ntree; }
314 
318  const TreeGraph &get_tree_graph() const { return m_tree; }
319 
323  auto get_cost(Edge e)->decltype(get(std::declval<CostMap>(), e)) {
324  return get(m_cost_map, e);
325  }
326 
331  *m_solution = m_edge_to_col_id.right.at(col);
332  ++m_solution;
333  m_sol_cost += m_cost_map[m_edge_to_col_id.right.at(col)];
334  m_edge_to_col_id.right.erase(col);
335  }
336 
340  void bind_edge_to_col(Edge e, lp::col_id col) {
341  auto tmp =
342  m_edge_to_col_id.insert(typename EdgeToColId::value_type(e, col));
343  assert(tmp.second);
344  }
345 
349  void bind_edge_to_row(Edge e, lp::row_id row) {
350  auto tmp =
351  m_row_id_to_edge.insert(typename RowIdToEdge::value_type(row, e));
352  assert(tmp.second);
353  }
354 
358  void init() {
359  // We need to fill very useful auxiliary data structures:
360  //\c m_covered_by - containing lists of
361  // edges. For a tree edge \c t the list \c m_covered_by[t]
362  // contains the list of links covering \c t.
363 
364  std::vector<Edge> pred(num_vertices(m_g));
365  auto pred_map =
366  boost::make_iterator_property_map(pred.begin(), m_index);
367  std::set<Vertex> seen;
368  for (auto u : boost::as_array(vertices(m_g))) {
369  auto tmp = seen.insert(u);
370  assert(tmp.second);
371  boost::breadth_first_search(
372  m_tree, u, boost::visitor(boost::make_bfs_visitor(
373  boost::record_edge_predecessors(
374  pred_map, boost::on_tree_edge()))));
375 
376  for (auto e : boost::as_array(out_edges(u, m_ntree))) {
377  auto node = target(e, m_ntree);
378  if (!seen.count(node)) {
379  while (node != u) {
380  m_covered_by[get(pred_map, node)].push_back(e);
381  node = source(get(pred_map, node), m_tree);
382  }
383  }
384  }
385  }
386  }
387 
391  Edge row_to_edge(lp::row_id row) const { return m_row_id_to_edge.at(row); }
392 
396  lp::col_id edge_to_col(Edge e) const { return m_edge_to_col_id.left.at(e); }
397 
401  EdgeList &get_covered_by(Edge e) { return m_covered_by[e]; }
402 
406  bool is_in_solution(Edge e) const {
407  return m_edge_to_col_id.left.find(e) == m_edge_to_col_id.left.end();
408  }
409 
413  CostValue get_solution_cost() const { return m_sol_cost; }
414 
415  private:
416 
418  const Graph &m_g;
420  TreeMap m_tree_map;
422  CostMap m_cost_map;
424  VertexIndex m_index;
425 
427  EdgeSetOutputIterator m_solution;
428 
430  EdgeToColId m_edge_to_col_id;
431 
433  TreeGraph m_tree;
435  NonTreeGraph m_ntree;
437  CostValue m_sol_cost;
439  CoverMap m_covered_by;
441  RowIdToEdge m_row_id_to_edge;
442 };
443 
444 namespace detail {
461 template <typename Graph, typename TreeMap, typename CostMap,
462  typename VertexIndex, typename EdgeSetOutputIterator>
463 tree_aug<Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator>
464 make_tree_aug(const Graph & g, TreeMap tree_map, CostMap cost_map,
465  VertexIndex vertex_index, EdgeSetOutputIterator solution) {
466  return paal::ir::tree_aug<Graph, TreeMap, CostMap,
467  VertexIndex, EdgeSetOutputIterator>(g, tree_map, cost_map, vertex_index, solution);
468 }
469 
491 template <typename Graph, typename TreeMap, typename CostMap,
492  typename VertexIndex, typename EdgeSetOutputIterator,
493  typename IRcomponents = tree_augmentation_ir_components<>,
494  typename Visitor = trivial_visitor>
496  const Graph & g,
497  TreeMap tree_map,
498  CostMap cost_map,
499  VertexIndex vertex_index,
500  EdgeSetOutputIterator solution,
502  Visitor visitor = Visitor()) {
503  auto treeaug = make_tree_aug(g, tree_map, cost_map, vertex_index, solution);
504  return solve_iterative_rounding(treeaug, std::move(components), std::move(visitor));
505 }
506 } // detail
507 
525 template <typename Graph, typename EdgeSetOutputIterator, typename P,
526  typename T, typename R>
527 auto make_tree_aug(const Graph &g,
528  const boost::bgl_named_params<P, T, R> &params,
529  EdgeSetOutputIterator solution)
530  ->tree_aug<
531  Graph,
532  decltype(choose_const_pmap(get_param(params, boost::edge_color), g,
533  boost::edge_color)),
534  decltype(choose_const_pmap(get_param(params, boost::edge_weight), g,
535  boost::edge_weight)),
536  decltype(choose_const_pmap(get_param(params, boost::vertex_index), g,
537  boost::vertex_index)),
538  EdgeSetOutputIterator> {
539  return detail::make_tree_aug(
540  g, choose_const_pmap(get_param(params, boost::edge_color), g,
541  boost::edge_color),
542  choose_const_pmap(get_param(params, boost::edge_weight), g,
543  boost::edge_weight),
544  choose_const_pmap(get_param(params, boost::vertex_index), g,
545  boost::vertex_index),
546  solution);
547 }
548 
562 template <typename Graph, typename EdgeSetOutputIterator>
563 auto make_tree_aug(const Graph &g, EdgeSetOutputIterator solution)
564  ->decltype(make_tree_aug(g, boost::no_named_parameters(), solution)) {
565  return make_tree_aug(g, boost::no_named_parameters(), solution);
566 }
567 
587 template <typename Graph, typename EdgeSetOutputIterator,
588  typename IRcomponents = tree_augmentation_ir_components<>,
589  typename Visitor = trivial_visitor, typename P, typename T,
590  typename R>
592  const Graph &g, const boost::bgl_named_params<P, T, R> &params,
593  EdgeSetOutputIterator solution, IRcomponents components = IRcomponents(),
594  Visitor visitor = Visitor()) {
596  g, choose_const_pmap(get_param(params, boost::edge_color), g,
597  boost::edge_color),
598  choose_const_pmap(get_param(params, boost::edge_weight), g,
599  boost::edge_weight),
600  choose_const_pmap(get_param(params, boost::vertex_index), g,
601  boost::vertex_index),
602  std::move(solution), std::move(components), std::move(visitor));
603 }
604 
620 template <typename Graph, typename EdgeSetOutputIterator,
621  typename IRcomponents = tree_augmentation_ir_components<>,
622  typename Visitor = trivial_visitor>
624  EdgeSetOutputIterator solution,
626  IRcomponents(),
627  Visitor visitor = Visitor()) {
629  g, boost::no_named_parameters(), std::move(solution),
630  std::move(components), std::move(visitor));
631 }
632 
633 } // ir
634 } // paal
635 
636 #endif // PAAL_TREE_AUGMENTATION_HPP
const TreeGraph & get_tree_graph() const
int filtered_num_edges(const EdgeListGraph &g)
void operator()(Problem &problem, const GetSolution &solution)
tree_aug< Graph, TreeMap, CostMap, VertexIndex, EdgeSetOutputIterator > make_tree_aug(const Graph &g, TreeMap tree_map, CostMap cost_map, VertexIndex vertex_index, EdgeSetOutputIterator solution)
Creates a tree_aug object. Non-named parameters.
The common LP solvers base class. Responsible for:
Definition: lp_base.hpp:55
col_id add_column(double cost_coef=0, double lb=0., double ub=lp_traits::PLUS_INF, const std::string &name="")
Definition: lp_base.hpp:92
functor return false
Definition: functors.hpp:222
void bind_edge_to_row(Edge e, lp::row_id row)
ta_round_condition(double epsilon=ta_compare_traits::EPSILON)
IRResult tree_augmentation_iterative_rounding(const Graph &g, const boost::bgl_named_params< P, T, R > &params, EdgeSetOutputIterator solution, IRcomponents components=IRcomponents(), Visitor visitor=Visitor())
Solves the Tree Augmentation problem using Iterative Rounding. Named parameters.
void set_lp_name(const std::string problem_name)
Definition: lp_base.hpp:78
auto make_tree_aug(const Graph &g, const boost::bgl_named_params< P, T, R > &params, EdgeSetOutputIterator solution) -> tree_aug< Graph, decltype(choose_const_pmap(get_param(params, boost::edge_color), g, boost::edge_color)), decltype(choose_const_pmap(get_param(params, boost::edge_weight), g, boost::edge_weight)), decltype(choose_const_pmap(get_param(params, boost::vertex_index), g, boost::vertex_index)), EdgeSetOutputIterator >
ErrorMessage check_input_validity()
Checks validity of the input.
void operator()(Problem &problem, LP &lp)
EdgeList & get_covered_by(Edge e)
A boost graph map that returns a constant integer value.
IRResult tree_augmentation_iterative_rounding(const Graph &g, TreeMap tree_map, CostMap cost_map, VertexIndex vertex_index, EdgeSetOutputIterator solution, IRcomponents components=IRcomponents(), Visitor visitor=Visitor())
Solves the Tree Augmentation problem using Iterative Rounding. Non-named parameters.
Edge row_to_edge(lp::row_id row) const
Default Iterative Rounding visitor.
CostValue get_solution_cost() const
boost::optional< double > operator()(Problem &problem, LP &lp, lp::col_id col)
Column rounding component. A variable is rounded up to 1, if it has value at least half in the soluti...
This is Jain&#39;s iterative rounding 2-approximation algorithm for the Generalised Steiner Network Probl...
bool is_in_solution(Edge e) const
typename components::type< Args...> IRcomponents
Iterative rounding components.
lp::col_id edge_to_col(Edge e) const
ta_set_solution(double epsilon=ta_compare_traits::EPSILON)
row_id add_row(const double_bounded_expression &constraint=double_bounded_expression{}, const std::string &name="")
Definition: lp_base.hpp:109
tree_aug(const Graph &g, TreeMap tree_map, CostMap cost_map, VertexIndex vertex_index, EdgeSetOutputIterator solution)
std::pair< lp::problem_type, IRSolutionCost > IRResult
IRResult solve_iterative_rounding(Problem &problem, IRcomponents components, Visitor visitor=Visitor())
Solves an Iterative Rounding problem.
bool e(T a, T b) const
equals
Definition: floating.hpp:33
const NonTreeGraph & get_links_graph() const
void add_to_solution(lp::col_id col)
auto get_cost(Edge e) -> decltype(get(std::declval< CostMap >(), e))
void bind_edge_to_col(Edge e, lp::col_id col)