1 // Copyright 2010-2021 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 14 #include "ortools/algorithms/sparse_permutation.h" 15 16 #include <algorithm> 17 18 #include "absl/strings/str_join.h" 19 #include "ortools/base/logging.h" 20 21 namespace operations_research { 22 23 void 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 52 std::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 81