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;
325inline 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;
#define DCHECK_GE(val1, val2)
#define DCHECK_LT(val1, val2)
IterablePart ElementsInPart(int i) const
uint64 FprintOfPart(int part) const
void Refine(const std::vector< int > &distinguished_subset)
int SizeOfPart(int part) const
void UndoRefineUntilNumPartsEqual(int original_num_parts)
IterablePart ElementsInSamePartAs(int i) const
int PartOf(int element) const
int ParentOfPart(int part) const
DynamicPartition(int num_elements)
std::string DebugString(DebugStringSorting sorting) const
const std::vector< int > & ElementsInHierarchicalOrder() const
const int NumParts() const
int NumNodesInSamePartAs(int node)
void Reset(int num_nodes)
std::string DebugString()
int MergePartsOf(int node1, int node2)
int FillEquivalenceClasses(std::vector< int > *node_equivalence_classes)
void KeepOnlyOneNodePerPart(std::vector< int > *nodes)
int GetRootAndCompressPath(int node)
MergingPartition(int num_nodes)
int GetRoot(int node) const
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
std::vector< int >::const_iterator end() const
std::vector< int >::const_iterator const_iterator
std::vector< int >::const_iterator begin_
std::vector< int >::const_iterator begin() const
IterablePart(const std::vector< int >::const_iterator &b, const std::vector< int >::const_iterator &e)
std::vector< int >::const_iterator end_