30 #ifndef OR_TOOLS_ALGORITHMS_DYNAMIC_PARTITION_H_
31 #define OR_TOOLS_ALGORITHMS_DYNAMIC_PARTITION_H_
61 const int NumParts()
const {
return part_.size(); }
72 int PartOf(
int element)
const;
108 void Refine(
const std::vector<int>& distinguished_subset);
144 std::vector<int> element_;
147 std::vector<int> index_of_;
150 std::vector<int> part_of_;
167 Part() : start_index(0), end_index(0), parent_part(0), fprint(0) {}
168 Part(
int start_index,
int end_index,
int parent_part,
uint64 fprint)
169 : start_index(start_index),
170 end_index(end_index),
171 parent_part(parent_part),
174 std::vector<Part> part_;
179 std::vector<int> tmp_counter_of_part_;
180 std::vector<int> tmp_affected_parts_;
185 std::vector<int>::const_iterator
end()
const {
return end_; }
187 std::vector<int>::const_iterator
end_;
193 const std::vector<int>::const_iterator& e)
208 void Reset(
int num_nodes);
265 void SetParentAlongPathToRoot(
int node,
int parent);
267 std::vector<int> parent_;
268 std::vector<int> part_size_;
271 std::vector<bool> tmp_part_bit_;
280 return IterablePart(element_.begin() + part_[i].start_index,
281 element_.begin() + part_[i].end_index);
287 return part_of_[element];
293 const Part& p = part_[part];
294 return p.end_index - p.start_index;
300 return part_[part].parent_part;
311 return part_[part].fprint;
319 const int parent = parent_[child];
320 if (parent == child)
return child;
325 inline void MergingPartition::SetParentAlongPathToRoot(
int node,
int parent) {
332 const int old_parent = parent_[child];
333 parent_[child] = parent;
334 if (old_parent == child)
return;
342 parent_[node] = node;
343 part_size_[node] = 1;
348 #endif // OR_TOOLS_ALGORITHMS_DYNAMIC_PARTITION_H_