19 #include <boost/graph/adjacency_list.hpp>
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;
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)};
39 Graph g(edges.begin(), edges.end(), edge_properties.begin(), 6);
41 std::vector<Edge> solution;
45 auto error = tree_aug.check_input_validity();
47 std::cerr <<
"The input is not valid!" << std::endl;
48 std::cerr << *error << std::endl;
54 g, std::back_inserter(solution));
57 if (result.first == paal::lp::OPTIMAL) {
58 std::cout <<
"The solution contains the following nontree edges:"
60 for (
auto e : solution) {
61 std::cout <<
"Edge " << e << std::endl;
63 std::cout <<
"Cost of the solution: " << *(result.second) << std::endl;
65 std::cout <<
"The instance is infeasible" << std::endl;
67 paal::lp::glp::free_env();
IRResult tree_augmentation_iterative_rounding(const Graph &g, const boost::bgl_named_params< P, T, R > ¶ms, 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 > ¶ms, 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]