All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
tree_augmentation_example.cpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c)
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 //=======================================================================
18 
19 #include <boost/graph/adjacency_list.hpp>
20 
21 #include <iostream>
22 #include <vector>
23 
24 int main() {
25  using EdgeProp = boost::property<boost::edge_weight_t, double,
26  boost::property<boost::edge_color_t, bool>>;
27  using Graph = boost::adjacency_list<boost::vecS, boost::vecS,
28  boost::undirectedS, boost::no_property, EdgeProp>;
29  using Edge = boost::graph_traits<Graph>::edge_descriptor;
30 
31  // sample problem
32  std::vector<std::pair<int, int>> edges {{0,1},{1,2},{1,3},{3,4},{3,5},
33  {0,3},{0,3},{2,4},{2,5},{4,5}};
34  std::vector<EdgeProp> edge_properties {EdgeProp(0, true),
35  EdgeProp(0, true), EdgeProp(0, true), EdgeProp(0, true),
36  EdgeProp(0, true), EdgeProp(1, false), EdgeProp(1, false),
37  EdgeProp(1, false), EdgeProp(1, false), EdgeProp(1,false)};
38 
39  Graph g(edges.begin(), edges.end(), edge_properties.begin(), 6);
40 
41  std::vector<Edge> solution;
42 
43  // optional input validity checking
44  auto tree_aug = paal::ir::make_tree_aug(g, std::back_inserter(solution));
45  auto error = tree_aug.check_input_validity();
46  if (error) {
47  std::cerr << "The input is not valid!" << std::endl;
48  std::cerr << *error << std::endl;
49  return -1;
50  }
51 
52  // solve it
54  g, std::back_inserter(solution));
55 
56  // print result
57  if (result.first == paal::lp::OPTIMAL) {
58  std::cout << "The solution contains the following nontree edges:"
59  << std::endl;
60  for (auto e : solution) {
61  std::cout << "Edge " << e << std::endl;
62  }
63  std::cout << "Cost of the solution: " << *(result.second) << std::endl;
64  } else {
65  std::cout << "The instance is infeasible" << std::endl;
66  }
67  paal::lp::glp::free_env();
68  return 0;
69 }
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.
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 >
int main()
[Tree Augmentation Example]