OR-Tools  8.2
dynamic_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
19
20namespace operations_research {
21
23 : image_(n, -1), ancestor_(n, -1), tmp_mask_(n, false) {
24 for (int i = 0; i < Size(); ++i) image_[i] = ancestor_[i] = i;
25}
26
27void DynamicPermutation::AddMappings(const std::vector<int>& src,
28 const std::vector<int>& dst) {
29 DCHECK_EQ(src.size(), dst.size());
30 mapping_src_size_stack_.push_back(mapping_src_stack_.size());
31 mapping_src_stack_.reserve(mapping_src_stack_.size() + src.size());
32 for (int i = 0; i < src.size(); ++i) {
33 const int s = src[i];
34 const int d = dst[i];
35 DCHECK_EQ(s, ImageOf(s)); // No prior image of s.
36 DCHECK_EQ(d, ancestor_[d]); // No prior ancestor of d.
37
38 ancestor_[d] = RootOf(s);
39 image_[s] = d;
40
41 if (image_[d] == d) loose_ends_.insert(d);
42 loose_ends_.erase(s); // Also takes care of the corner case s == d.
43
44 // Remember the sources for the undo stack.
45 mapping_src_stack_.push_back(s);
46 }
47}
48
50 std::vector<int>* undone_mapping_src) {
51 DCHECK(undone_mapping_src != nullptr);
52 undone_mapping_src->clear();
53 if (mapping_src_size_stack_.empty()) return; // Nothing to undo.
54 const int num_mappings_before = mapping_src_size_stack_.back();
55 mapping_src_size_stack_.pop_back();
56 const int num_mappings_now = mapping_src_stack_.size();
57 DCHECK_GE(num_mappings_now, num_mappings_before);
58 // Dump the undone mappings.
59 undone_mapping_src->reserve(num_mappings_now - num_mappings_before);
60 undone_mapping_src->insert(undone_mapping_src->begin(),
61 mapping_src_stack_.begin() + num_mappings_before,
62 mapping_src_stack_.end());
63 // Note(user): the mappings should be undone in reverse order, because the
64 // code that keeps "tails" up to date depends on it.
65 for (int i = num_mappings_now - 1; i >= num_mappings_before; --i) {
66 const int s = mapping_src_stack_[i];
67 const int d = ImageOf(s);
68
69 if (ancestor_[s] != s) loose_ends_.insert(s);
70 loose_ends_.erase(d);
71
72 ancestor_[d] = d;
73 image_[s] = s;
74 }
75 mapping_src_stack_.resize(num_mappings_before); // Shrink.
76}
77
79 for (const int i : mapping_src_stack_) {
80 const int dst = image_[i];
81 ancestor_[dst] = dst;
82 image_[i] = i;
83 }
84 mapping_src_stack_.clear();
85 mapping_src_size_stack_.clear();
86 loose_ends_.clear();
87}
88
89std::unique_ptr<SparsePermutation> DynamicPermutation::CreateSparsePermutation()
90 const {
91 std::unique_ptr<SparsePermutation> sparse_perm(new SparsePermutation(Size()));
92 int num_identity_singletons = 0;
93 for (const int x : mapping_src_stack_) {
94 if (tmp_mask_[x]) continue;
95 // Deal with the special case of a trivial x->x cycle, which we do *not*
96 // want to add to the sparse permutation.
97 if (ImageOf(x) == x) {
98 DCHECK_EQ(x, RootOf(x));
99 ++num_identity_singletons;
100 continue;
101 }
102 const int root = RootOf(x);
103 int next = root;
104 while (true) {
105 sparse_perm->AddToCurrentCycle(next);
106 tmp_mask_[next] = true;
108 next = ImageOf(next);
109 if (next == root) break;
110 }
111 sparse_perm->CloseCurrentCycle();
112 }
113 for (const int x : mapping_src_stack_) tmp_mask_[x] = false;
114 DCHECK_EQ(mapping_src_stack_.size(),
115 sparse_perm->Support().size() + num_identity_singletons);
116 return sparse_perm;
117}
118
120 // That's wasteful, but we don't care, DebugString() may be slow.
121 return CreateSparsePermutation()->DebugString();
122}
123
124} // namespace operations_research
#define DCHECK_NE(val1, val2)
Definition: base/logging.h:886
#define DCHECK_GE(val1, val2)
Definition: base/logging.h:889
#define DCHECK(condition)
Definition: base/logging.h:884
#define DCHECK_EQ(val1, val2)
Definition: base/logging.h:885
std::unique_ptr< SparsePermutation > CreateSparsePermutation() const
void UndoLastMappings(std::vector< int > *undone_mapping_src)
void AddMappings(const std::vector< int > &src, const std::vector< int > &dst)
Block * next
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...