OR-Tools  8.2
dynamic_partition.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_format.h"
19#include "absl/strings/str_join.h"
20#include "ortools/base/murmur.h"
21
22namespace operations_research {
23
24namespace {
25uint64 FprintOfInt32(int i) {
26 return util_hash::MurmurHash64(reinterpret_cast<const char*>(&i),
27 sizeof(int));
28}
29} // namespace
30
32 DCHECK_GE(num_elements, 0);
33 element_.assign(num_elements, -1);
34 index_of_.assign(num_elements, -1);
35 for (int i = 0; i < num_elements; ++i) {
36 element_[i] = i;
37 index_of_[i] = i;
38 }
39 part_of_.assign(num_elements, 0);
40 uint64 fprint = 0;
41 for (int i = 0; i < num_elements; ++i) fprint ^= FprintOfInt32(i);
42 part_.push_back(Part(/*start_index=*/0, /*end_index=*/num_elements,
43 /*parent_part=*/0,
44 /*fprint=*/fprint));
45}
46
48 const std::vector<int>& initial_part_of_element) {
49 if (initial_part_of_element.empty()) return;
50 part_of_ = initial_part_of_element;
51 const int n = part_of_.size();
52 const int num_parts = 1 + *std::max_element(part_of_.begin(), part_of_.end());
53 DCHECK_EQ(0, *std::min_element(part_of_.begin(), part_of_.end()));
54 part_.resize(num_parts);
55
56 // Compute the part fingerprints.
57 for (int i = 0; i < n; ++i) part_[part_of_[i]].fprint ^= FprintOfInt32(i);
58
59 // Compute the actual start indices of each part, knowing that we'll sort
60 // them as they were given implicitly in "initial_part_of_element".
61 // The code looks a bit weird to do it in-place, with no additional memory.
62 for (int p = 0; p < num_parts; ++p) {
63 part_[p].end_index = 0; // Temporarily utilized as size_of_part.
64 part_[p].parent_part = p;
65 }
66 for (const int p : part_of_) ++part_[p].end_index; // size_of_part
67 int sum_part_sizes = 0;
68 for (int p = 0; p < num_parts; ++p) {
69 part_[p].start_index = sum_part_sizes;
70 sum_part_sizes += part_[p].end_index; // size of part.
71 }
72
73 // Now that we have the correct start indices, we set the end indices to the
74 // start indices, and incrementally add all elements to their part, adjusting
75 // the end indices as we go.
76 for (Part& part : part_) part.end_index = part.start_index;
77 element_.assign(n, -1);
78 index_of_.assign(n, -1);
79 for (int element = 0; element < n; ++element) {
80 Part* const part = &part_[part_of_[element]];
81 element_[part->end_index] = element;
82 index_of_[element] = part->end_index;
83 ++part->end_index;
84 }
85
86 // Verify that we did it right.
87 // TODO(user): either remove this or factor it out if it can be used
88 // elsewhere.
89 DCHECK_EQ(0, part_[0].start_index);
90 DCHECK_EQ(NumElements(), part_[NumParts() - 1].end_index);
91 for (int p = 1; p < NumParts(); ++p) {
92 DCHECK_EQ(part_[p - 1].end_index, part_[p].start_index);
93 }
94}
95
96void DynamicPartition::Refine(const std::vector<int>& distinguished_subset) {
97 // tmp_counter_of_part_[i] will contain the number of
98 // elements in distinguished_subset that were part of part #i.
99 tmp_counter_of_part_.resize(NumParts(), 0);
100 // We remember the Parts that were actually affected.
101 tmp_affected_parts_.clear();
102 for (const int element : distinguished_subset) {
103 DCHECK_GE(element, 0);
104 DCHECK_LT(element, NumElements());
105 const int part = part_of_[element];
106 const int num_distinguished_elements_in_part = ++tmp_counter_of_part_[part];
107 // Is this the first time that we touch this element's part?
108 if (num_distinguished_elements_in_part == 1) {
109 // TODO(user): optimize the common singleton case.
110 tmp_affected_parts_.push_back(part);
111 }
112 // Move the element to the end of its current Part.
113 const int old_index = index_of_[element];
114 const int new_index =
115 part_[part].end_index - num_distinguished_elements_in_part;
116 DCHECK_GE(new_index, old_index)
117 << "Duplicate element given to Refine(): " << element;
118 // Perform the swap, keeping index_of_ up to date.
119 index_of_[element] = new_index;
120 index_of_[element_[new_index]] = old_index;
121 std::swap(element_[old_index], element_[new_index]);
122 }
123
124 // Sort affected parts. This is important to behave as advertised in the .h.
125 // TODO(user,user): automatically switch to an O(N) sort when it's faster
126 // than this one, which is O(K log K) with K = tmp_affected_parts_.size().
127 std::sort(tmp_affected_parts_.begin(), tmp_affected_parts_.end());
128
129 // Iterate on each affected part and split it, or keep it intact if all
130 // of its elements were distinguished.
131 for (const int part : tmp_affected_parts_) {
132 const int start_index = part_[part].start_index;
133 const int end_index = part_[part].end_index;
134 const int split_index = end_index - tmp_counter_of_part_[part];
135 tmp_counter_of_part_[part] = 0; // Clean up after us.
136 DCHECK_GE(split_index, start_index);
137 DCHECK_LT(split_index, end_index);
138
139 // Do nothing if all elements were distinguished.
140 if (split_index == start_index) continue;
141
142 // Compute the fingerprint of the new part.
143 uint64 new_fprint = 0;
144 for (int i = split_index; i < end_index; ++i) {
145 new_fprint ^= FprintOfInt32(element_[i]);
146 }
147
148 const int new_part = NumParts();
149
150 // Perform the split.
151 part_[part].end_index = split_index;
152 part_[part].fprint ^= new_fprint;
153 part_.push_back(Part(/*start_index*/ split_index, /*end_index*/ end_index,
154 /*parent_part*/ part, new_fprint));
155 for (const int element : ElementsInPart(new_part)) {
156 part_of_[element] = new_part;
157 }
158 }
159}
160
162 DCHECK_GE(NumParts(), original_num_parts);
163 DCHECK_GE(original_num_parts, 1);
164 while (NumParts() > original_num_parts) {
165 const int part_index = NumParts() - 1;
166 const Part& part = part_[part_index];
167 const int parent_part_index = part.parent_part;
168 DCHECK_LT(parent_part_index, part_index) << "UndoRefineUntilNumPartsEqual()"
169 " called with "
170 "'original_num_parts' too low";
171
172 // Update the part contents: actually merge "part" onto its parent.
173 for (const int element : ElementsInPart(part_index)) {
174 part_of_[element] = parent_part_index;
175 }
176 Part* const parent_part = &part_[parent_part_index];
177 DCHECK_EQ(part.start_index, parent_part->end_index);
178 parent_part->end_index = part.end_index;
179 parent_part->fprint ^= part.fprint;
180 part_.pop_back();
181 }
182}
183
185 if (sorting != SORT_LEXICOGRAPHICALLY && sorting != SORT_BY_PART) {
186 return absl::StrFormat("Unsupported sorting: %d", sorting);
187 }
188 std::vector<std::vector<int>> parts;
189 for (int i = 0; i < NumParts(); ++i) {
190 IterablePart iterable_part = ElementsInPart(i);
191 parts.emplace_back(iterable_part.begin(), iterable_part.end());
192 std::sort(parts.back().begin(), parts.back().end());
193 }
194 if (sorting == SORT_LEXICOGRAPHICALLY) {
195 std::sort(parts.begin(), parts.end());
196 }
197 std::string out;
198 for (const std::vector<int>& part : parts) {
199 if (!out.empty()) out += " | ";
200 out += absl::StrJoin(part, " ");
201 }
202 return out;
203}
204
205void MergingPartition::Reset(int num_nodes) {
206 DCHECK_GE(num_nodes, 0);
207 part_size_.assign(num_nodes, 1);
208 parent_.assign(num_nodes, -1);
209 for (int i = 0; i < num_nodes; ++i) parent_[i] = i;
210 tmp_part_bit_.assign(num_nodes, false);
211}
212
213int MergingPartition::MergePartsOf(int node1, int node2) {
214 DCHECK_GE(node1, 0);
215 DCHECK_GE(node2, 0);
216 DCHECK_LT(node1, NumNodes());
217 DCHECK_LT(node2, NumNodes());
218 int root1 = GetRoot(node1);
219 int root2 = GetRoot(node2);
220 if (root1 == root2) return -1;
221 int s1 = part_size_[root1];
222 int s2 = part_size_[root2];
223 // Attach the smaller part to the larger one. Break ties by root index.
224 if (s1 < s2 || (s1 == s2 && root1 > root2)) {
225 std::swap(root1, root2);
226 std::swap(s1, s2);
227 }
228
229 // Update the part size. Don't change part_size_[root2]: it won't be used
230 // again by further merges.
231 part_size_[root1] += part_size_[root2];
232 SetParentAlongPathToRoot(node1, root1);
233 SetParentAlongPathToRoot(node2, root1);
234 return root2;
235}
236
238 DCHECK_GE(node, 0);
239 DCHECK_LT(node, NumNodes());
240 const int root = GetRoot(node);
241 SetParentAlongPathToRoot(node, root);
242 return root;
243}
244
245void MergingPartition::KeepOnlyOneNodePerPart(std::vector<int>* nodes) {
246 int num_nodes_kept = 0;
247 for (const int node : *nodes) {
248 const int representative = GetRootAndCompressPath(node);
249 if (!tmp_part_bit_[representative]) {
250 tmp_part_bit_[representative] = true;
251 (*nodes)[num_nodes_kept++] = node;
252 }
253 }
254 nodes->resize(num_nodes_kept);
255
256 // Clean up the tmp_part_bit_ vector. Since we've already compressed the
257 // paths (if backtracking was enabled), no need to do it again.
258 for (const int node : *nodes) tmp_part_bit_[GetRoot(node)] = false;
259}
260
262 std::vector<int>* node_equivalence_classes) {
263 node_equivalence_classes->assign(NumNodes(), -1);
264 int num_roots = 0;
265 for (int node = 0; node < NumNodes(); ++node) {
266 const int root = GetRootAndCompressPath(node);
267 if ((*node_equivalence_classes)[root] < 0) {
268 (*node_equivalence_classes)[root] = num_roots;
269 ++num_roots;
270 }
271 (*node_equivalence_classes)[node] = (*node_equivalence_classes)[root];
272 }
273 return num_roots;
274}
275
277 std::vector<std::vector<int>> sorted_parts(NumNodes());
278 for (int i = 0; i < NumNodes(); ++i) {
279 sorted_parts[GetRootAndCompressPath(i)].push_back(i);
280 }
281 for (std::vector<int>& part : sorted_parts)
282 std::sort(part.begin(), part.end());
283 std::sort(sorted_parts.begin(), sorted_parts.end());
284 // Note: typically, a lot of elements of "sorted_parts" will be empty,
285 // but these won't be visible in the string that we construct below.
286 std::string out;
287 for (const std::vector<int>& part : sorted_parts) {
288 if (!out.empty()) out += " | ";
289 out += absl::StrJoin(part, " ");
290 }
291 return out;
292}
293
294} // 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_EQ(val1, val2)
Definition: base/logging.h:885
IterablePart ElementsInPart(int i) const
void Refine(const std::vector< int > &distinguished_subset)
void UndoRefineUntilNumPartsEqual(int original_num_parts)
std::string DebugString(DebugStringSorting sorting) const
int MergePartsOf(int node1, int node2)
int FillEquivalenceClasses(std::vector< int > *node_equivalence_classes)
void KeepOnlyOneNodePerPart(std::vector< int > *nodes)
uint64_t uint64
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
uint64 MurmurHash64(const char *buf, const size_t len)
Definition: murmur.h:23
ColIndex representative
std::vector< int >::const_iterator end() const
std::vector< int >::const_iterator begin() const