All Classes Namespaces Files Functions Variables Typedefs Enumerations Friends Macros Pages
steiner_network_example.cpp
Go to the documentation of this file.
1 //=======================================================================
2 // Copyright (c) 2013 Piotr Wygocki
3 // 2014 Piotr Godlewski
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
19 
20 #include <boost/graph/adjacency_list.hpp>
21 
22 #include <iostream>
23 #include <vector>
24 
25 int main() {
26  using Graph = boost::adjacency_list<boost::vecS, boost::vecS,
27  boost::undirectedS, boost::no_property,
28  boost::property<boost::edge_weight_t, int>>;
29  using Edge = boost::graph_traits<Graph>::edge_descriptor;
30 
31  // sample problem
32  std::vector<std::pair<int, int>> edges {{0,1},{0,1},{1,2},{1,2},{2,0}};
33  std::vector<int> costs {1,1,1,1,7};
34  auto restrictions = [](int i, int j) {return 2;};
35 
36  Graph g(edges.begin(), edges.end(), costs.begin(), 3);
37 
38  std::vector<Edge> result_network;
39 
40  // optional input validity checking
41  auto steiner_network = paal::ir::make_steiner_network(
42  g, restrictions, std::back_inserter(result_network));
43  auto error = steiner_network.check_input_validity();
44  if (error) {
45  std::cerr << "The input is not valid!" << std::endl;
46  std::cerr << *error << std::endl;
47  return -1;
48  }
49 
50  // solve it
52  g, restrictions, std::back_inserter(result_network));
53 
54  // print result
55  if (result.first == paal::lp::OPTIMAL) {
56  std::cout << "Edges in steiner network" << std::endl;
57  for (auto e : result_network) {
58  std::cout << "Edge " << e << std::endl;
59  }
60  std::cout << "Cost of the solution: " << *(result.second) << std::endl;
61  } else {
62  std::cout << "The instance is infeasible" << std::endl;
63  }
64  paal::lp::glp::free_env();
65  return 0;
66 }
IRResult steiner_network_iterative_rounding(const Graph &g, const Restrictions &restrictions, const boost::bgl_named_params< P, T, R > &params, ResultNetworkOutputIterator result, IRcomponents components=IRcomponents(), Oracle oracle=Oracle(), Visitor visitor=Visitor())
Solves the Steiner Network problem using Iterative Rounding. Named version.
int main()
[Steiner Network Example]
auto make_steiner_network(const Graph &g, const Restrictions &restrictions, const boost::bgl_named_params< P, T, R > &params, ResultNetworkOutputIterator result_network, Oracle oracle=Oracle()) -> steiner_network< Graph, Restrictions, 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)), ResultNetworkOutputIterator, Oracle >