121 #ifndef OR_TOOLS_GRAPH_ONE_TREE_LOWER_BOUND_H_
122 #define OR_TOOLS_GRAPH_ONE_TREE_LOWER_BOUND_H_
129 #include "ortools/base/integral_types.h"
152 template <
typename CostType>
156 : step1_initialized_(false),
159 max_iterations_(max_iterations > 0 ? max_iterations
160 : MaxIterations(number_of_nodes)),
161 number_of_nodes_(number_of_nodes) {}
163 bool Next() {
return iteration_++ < max_iterations_; }
166 return (1.0 * (iteration_ - 1) * (2 * max_iterations_ - 5) /
167 (2 * (max_iterations_ - 1))) *
169 (iteration_ - 2) * step1_ +
170 (0.5 * (iteration_ - 1) * (iteration_ - 2) /
171 ((max_iterations_ - 1) * (max_iterations_ - 2))) *
176 const std::vector<int>& degrees) {
177 if (!step1_initialized_) {
178 step1_initialized_ =
true;
179 UpdateStep(one_tree_cost);
183 void OnNewWMax(CostType one_tree_cost) { UpdateStep(one_tree_cost); }
188 static int MaxIterations(
int number_of_nodes) {
189 return static_cast<int>(28 * std::pow(number_of_nodes, 0.62));
192 void UpdateStep(CostType one_tree_cost) {
193 step1_ = one_tree_cost / (2 * number_of_nodes_);
196 bool step1_initialized_;
199 const int max_iterations_;
200 const int number_of_nodes_;
205 template <
typename CostType,
typename CostFunction>
210 number_of_iterations_(2 * number_of_nodes),
217 number_of_nodes, cost);
222 const int min_iterations = 2;
223 if (iteration_ >= number_of_iterations_) {
224 number_of_iterations_ /= 2;
225 if (number_of_iterations_ < min_iterations)
return false;
237 const std::vector<int>& degrees) {
239 for (
int degree : degrees) {
240 const double delta = degree - 2;
241 norm += delta * delta;
243 step_ = lambda_ * (upper_bound_ - w) / norm;
250 int number_of_iterations_;
251 CostType upper_bound_;
261 template <
typename CostFunction>
263 int number_of_neighbors,
264 const CostFunction& cost) {
265 using CostType = decltype(cost(0, 0));
266 std::set<std::pair<int, int>> nearest;
267 for (
int i = 0; i < number_of_nodes; ++i) {
268 std::vector<std::pair<CostType, int>> neighbors;
269 neighbors.reserve(number_of_nodes - 1);
270 for (
int j = 0; j < number_of_nodes; ++j) {
272 neighbors.emplace_back(cost(i, j), j);
275 int size = neighbors.size();
276 if (number_of_neighbors < size) {
277 std::nth_element(neighbors.begin(),
278 neighbors.begin() + number_of_neighbors - 1,
280 size = number_of_neighbors;
282 for (
int j = 0; j < size; ++j) {
283 nearest.insert({i, neighbors[j].second});
284 nearest.insert({neighbors[j].second, i});
292 template <
typename CostFunction>
294 const CostFunction& cost,
295 std::set<std::pair<int, int>>* arcs) {
297 const std::vector<int> mst =
299 return cost(graph.
Tail(arc), graph.
Head(arc));
301 for (
int arc : mst) {
302 arcs->insert({graph.
Tail(arc), graph.
Head(arc)});
303 arcs->insert({graph.
Head(arc), graph.
Tail(arc)});
309 template <
typename CostFunction,
typename GraphType,
typename AcceptFunction>
311 const CostFunction& cost,
312 AcceptFunction accept) {
314 double best_edge_cost = 0;
315 for (
const auto node : graph.AllNodes()) {
317 const double edge_cost = cost(node, source);
318 if (best_node == -1 || edge_cost < best_edge_cost) {
320 best_edge_cost = edge_cost;
330 template <
typename CostFunction,
typename GraphType,
typename CostType>
332 const CostFunction& cost,
333 const std::vector<double>& weights,
334 const std::vector<int>& sorted_arcs,
335 CostType* one_tree_cost) {
336 const auto weighed_cost = [&cost, &weights](
int from,
int to) {
337 return cost(from, to) + weights[from] + weights[to];
340 std::vector<int> mst;
341 if (!sorted_arcs.empty()) {
342 mst = BuildKruskalMinimumSpanningTreeFromSortedArcs<GraphType>(graph,
345 mst = BuildPrimMinimumSpanningTree<GraphType>(
346 graph, [&weighed_cost, &graph](
int arc) {
347 return weighed_cost(graph.Tail(arc), graph.Head(arc));
350 std::vector<int> degrees(graph.num_nodes() + 1, 0);
352 for (
int arc : mst) {
353 degrees[graph.Head(arc)]++;
354 degrees[graph.Tail(arc)]++;
355 *one_tree_cost += cost(graph.Tail(arc), graph.Head(arc));
359 const int extra_node = graph.num_nodes();
360 const auto update_one_tree = [extra_node, one_tree_cost, °rees,
362 *one_tree_cost += cost(node, extra_node);
367 graph, extra_node, weighed_cost,
368 [extra_node](
int n) {
return n != extra_node; });
369 update_one_tree(node);
371 graph, extra_node, weighed_cost,
372 [extra_node, node](
int n) {
return n != extra_node && n != node; }));
377 template <
typename CostFunction,
typename Algorithm>
379 int nearest_neighbors,
380 const CostFunction& cost,
381 Algorithm* algorithm) {
382 if (number_of_nodes < 2)
return 0;
383 if (number_of_nodes == 2)
return cost(0, 1) + cost(1, 0);
384 using CostType = decltype(cost(0, 0));
385 auto nearest =
NearestNeighbors(number_of_nodes - 1, nearest_neighbors, cost);
391 for (
const auto& arc : nearest) {
392 graph.
AddArc(arc.first, arc.second);
394 std::vector<double> weights(number_of_nodes, 0);
395 std::vector<double> best_weights(number_of_nodes, 0);
396 double max_w = -std::numeric_limits<double>::infinity();
399 while (algorithm->Next()) {
400 CostType one_tree_cost = 0;
401 const std::vector<int> degrees =
403 algorithm->OnOneTree(one_tree_cost, w, degrees);
405 for (
int j = 0; j < number_of_nodes; ++j) {
406 w += weights[j] * (degrees[j] - 2);
410 best_weights = weights;
411 algorithm->OnNewWMax(one_tree_cost);
413 const double step = algorithm->GetStep();
414 for (
int j = 0; j < number_of_nodes; ++j) {
415 weights[j] += step * (degrees[j] - 2);
422 CostType one_tree_cost = 0;
426 const std::vector<int> degrees =
427 ComputeOneTree(complete_graph, cost, best_weights, {}, &one_tree_cost);
429 for (
int j = 0; j < number_of_nodes; ++j) {
430 w += best_weights[j] * (degrees[j] - 2);
451 template <
typename CostFunction>
453 int number_of_nodes,
const CostFunction& cost,
455 using CostType = decltype(cost(0, 0));
466 number_of_nodes, cost);
471 LOG(ERROR) <<
"Unsupported algorithm: " << parameters.
algorithm;
479 template <
typename CostFunction>
488 #endif // OR_TOOLS_GRAPH_ONE_TREE_LOWER_BOUND_H_