OR-Tools  8.2
sparse_permutation.cc
Go to the documentation of this file.
1// Copyright 2010-2018 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
15
16#include <algorithm>
17
18#include "absl/strings/str_join.h"
20
21namespace operations_research {
22
23void SparsePermutation::RemoveCycles(const std::vector<int>& cycle_indices) {
24 // TODO(user): make this a class member to avoid allocation if the complexity
25 // becomes an issue. In this case, also optimize the loop below by not copying
26 // the first cycles.
27 std::vector<bool> should_be_deleted(NumCycles(), false);
28 for (int i : cycle_indices) {
29 DCHECK_GE(i, 0);
30 DCHECK_LT(i, NumCycles());
31 DCHECK(!should_be_deleted[i])
32 << "Duplicate index given to RemoveCycles(): " << i;
33 should_be_deleted[i] = true;
34 }
35 int new_cycles_size = 0; // new index in cycles_
36 int new_cycle_ends_size = 0; // new index in cycle_ends_
37 int start = 0;
38 for (int i = 0; i < NumCycles(); ++i) {
39 const int end = cycle_ends_[i];
40 if (!should_be_deleted[i]) {
41 for (int j = start; j < end; ++j) {
42 cycles_[new_cycles_size++] = cycles_[j];
43 }
44 cycle_ends_[new_cycle_ends_size++] = new_cycles_size;
45 }
46 start = end;
47 }
48 cycles_.resize(new_cycles_size);
49 cycle_ends_.resize(new_cycle_ends_size);
50}
51
52std::string SparsePermutation::DebugString() const {
53 DCHECK_EQ(cycles_.empty(), cycle_ends_.empty());
54 if (!cycles_.empty()) DCHECK_EQ(cycles_.size(), cycle_ends_.back());
55 std::vector<std::vector<int>> cycles;
56 int start = 0;
57 for (const int end : cycle_ends_) {
58 // Find the minimum.
59 int min_pos = start;
60 for (int i = start + 1; i < end; ++i) {
61 if (cycles_[i] < cycles_[min_pos]) min_pos = i;
62 }
63 std::vector<int> cycle;
64 for (int i = min_pos; i < end; ++i) cycle.push_back(cycles_[i]);
65 for (int i = start; i < min_pos; ++i) cycle.push_back(cycles_[i]);
66 cycles.push_back(cycle);
67 start = end;
68 }
69 std::sort(cycles.begin(), cycles.end());
70 std::string out;
71 for (const std::vector<int>& cycle : cycles) {
72 if (!out.empty()) out += " ";
73 out += "(";
74 out += absl::StrJoin(cycle, " ");
75 out += ")";
76 }
77 return out;
78}
79
80} // namespace operations_research
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK_LT(val1, val2)
Definition: base/logging.h:888
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
void RemoveCycles(const std::vector< int > &cycle_indices)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...