Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
Classes | Public Member Functions | List of all members
operations_research::DynamicPartition Class Reference

#include <dynamic_partition.h>

Classes

struct  IterablePart
 

Public Member Functions

 DynamicPartition (int num_elements)
 
 DynamicPartition (const std::vector< int > &initial_part_of_element)
 
int NumElements () const
 Accessors.
 
int NumParts () const
 
IterablePart ElementsInPart (int i) const
 *** Implementation of inline methods of the above classes. ***
 
int PartOf (int element) const
 
int SizeOfPart (int part) const
 
int ParentOfPart (int part) const
 
IterablePart ElementsInSamePartAs (int i) const
 
uint64_t FprintOfPart (int part) const
 
void Refine (absl::Span< const int > distinguished_subset)
 
void UndoRefineUntilNumPartsEqual (int original_num_parts)
 
std::string DebugString (bool sort_parts_lexicographically) const
 
const std::vector< int > & ElementsInHierarchicalOrder () const
 

Detailed Description

Partition class that supports incremental splitting, with backtracking. See http://en.wikipedia.org/wiki/Partition_refinement . More precisely, the supported edit operations are:

  • Refine the partition so that a subset S (typically, S <<< N) of elements are all considered non-equivalent to any element in ¬S. Typically, this should be done in O(S).

  • Undo the above operations (backtracking).

    Todo
    (user): rename this to BacktrackableSplittingPartition.

Definition at line 51 of file dynamic_partition.h.

Constructor & Destructor Documentation

◆ DynamicPartition() [1/2]

operations_research::DynamicPartition::DynamicPartition ( int num_elements)
explicit

Creates a DynamicPartition on n elements, numbered 0..n-1. Start with the trivial partition (only one subset containing all elements).

Definition at line 36 of file dynamic_partition.cc.

◆ DynamicPartition() [2/2]

operations_research::DynamicPartition::DynamicPartition ( const std::vector< int > & initial_part_of_element)
explicit

Ditto, but specify the initial part of each elements. Part indices must form a dense integer set starting at 0; eg. [2, 1, 0, 1, 1, 3, 0] is valid.

Compute the part fingerprints.

Compute the actual start indices of each part, knowing that we'll sort them as they were given implicitly in "initial_part_of_element". The code looks a bit weird to do it in-place, with no additional memory.

Now that we have the correct start indices, we set the end indices to the start indices, and incrementally add all elements to their part, adjusting the end indices as we go.

Verify that we did it right.

Todo
(user): either remove this or factor it out if it can be used elsewhere.

Definition at line 52 of file dynamic_partition.cc.

Member Function Documentation

◆ DebugString()

std::string operations_research::DynamicPartition::DebugString ( bool sort_parts_lexicographically) const

Converts the current partition to a string, like "3 | 1 2 | 0 4 5". Within each part, elements are sorted. And if sort_parts_lexicographically=true, the parts are sorted lexicographically instead of by their natural order.

Definition at line 189 of file dynamic_partition.cc.

◆ ElementsInHierarchicalOrder()

const std::vector< int > & operations_research::DynamicPartition::ElementsInHierarchicalOrder ( ) const
inline

ADVANCED USAGE: All elements (0..n-1) of the partition, sorted in a way that's compatible with the hierarchical partitioning:

  • All the elements of any given part are contiguous.
  • Elements of a part P are always after elements of part Parent(P).
  • The order remains identical (and the above property holds) after any UndoRefine*() operation.
    Note
    the order does get changed by Refine() operations. This is a reference, so it'll only remain valid and constant until the class is destroyed or until Refine() get called.

Definition at line 132 of file dynamic_partition.h.

◆ ElementsInPart()

DynamicPartition::IterablePart operations_research::DynamicPartition::ElementsInPart ( int i) const
inline

*** Implementation of inline methods of the above classes. ***

Definition at line 303 of file dynamic_partition.h.

◆ ElementsInSamePartAs()

DynamicPartition::IterablePart operations_research::DynamicPartition::ElementsInSamePartAs ( int i) const
inline

A handy shortcut to ElementsInPart(PartOf(e)). The returned IterablePart will never be empty, since it contains at least i.

Definition at line 330 of file dynamic_partition.h.

◆ FprintOfPart()

uint64_t operations_research::DynamicPartition::FprintOfPart ( int part) const
inline

Returns a fingerprint of the given part. While collisions are possible, their probability is quite low. Two parts that have the same size and the same fingerprint are most likely identical. Also, two parts that have the exact same set of elements will always have the same fingerprint.

Definition at line 335 of file dynamic_partition.h.

◆ NumElements()

int operations_research::DynamicPartition::NumElements ( ) const
inline

Accessors.

Definition at line 62 of file dynamic_partition.h.

◆ NumParts()

int operations_research::DynamicPartition::NumParts ( ) const
inline

Definition at line 63 of file dynamic_partition.h.

◆ ParentOfPart()

int operations_research::DynamicPartition::ParentOfPart ( int part) const
inline

Definition at line 324 of file dynamic_partition.h.

◆ PartOf()

int operations_research::DynamicPartition::PartOf ( int element) const
inline

Definition at line 311 of file dynamic_partition.h.

◆ Refine()

void operations_research::DynamicPartition::Refine ( absl::Span< const int > distinguished_subset)

Refines the partition such that elements that are in distinguished_subset never share the same part as elements that aren't in that subset. This might be a no-op: in that case, NumParts() won't change, but the order of elements inside each part may change.

ORDERING OF PARTS: For each i such that Part #i has a non-trivial intersection with "distinguished_subset" (neither empty, nor the full Part); Part #i is stripped out of all elements that are in "distinguished_subset", and those elements are sent to a newly created part, whose parent_part = i. The parts newly created by a single Refine() operations are sorted by parent_part. Example: a Refine() on a partition with 6 parts causes parts #1, #3 and #4 to be split: the partition will now contain 3 new parts: part #6 (with parent_part = 1), part #7 (with parent_part = 3) and part #8 (with parent_part = 4).

Todo
(user): the graph symmetry finder could probably benefit a lot from keeping track of one additional bit of information for each part that remains unchanged by a Refine() operation: was that part entirely in the distinguished subset or entirely out?

tmp_counter_of_part_[i] will contain the number of elements in distinguished_subset that were part of part #i.

We remember the Parts that were actually affected.

Is this the first time that we touch this element's part?

Todo
(user): optimize the common singleton case.

Move the element to the end of its current Part.

Perform the swap, keeping index_of_ up to date.

Sort affected parts. This is important to behave as advertised in the .h.

Todo
(user): automatically switch to an O(N) sort when it's faster than this one, which is O(K log K) with K = tmp_affected_parts_.size().

Iterate on each affected part and split it, or keep it intact if all of its elements were distinguished.

Do nothing if all elements were distinguished.

Compute the fingerprint of the new part.

Perform the split.

Definition at line 101 of file dynamic_partition.cc.

◆ SizeOfPart()

int operations_research::DynamicPartition::SizeOfPart ( int part) const
inline

Definition at line 317 of file dynamic_partition.h.

◆ UndoRefineUntilNumPartsEqual()

void operations_research::DynamicPartition::UndoRefineUntilNumPartsEqual ( int original_num_parts)

Undo one or several Refine() operations, until the number of parts becomes equal to "original_num_parts". Prerequisite: NumParts() >= original_num_parts.

Update the part contents: actually merge "part" onto its parent.

Definition at line 166 of file dynamic_partition.cc.

The documentation for this class was generated from the following files: