C++ Reference: class DynamicPartition

Note: This documentation is automatically generated.

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.

Method
DebugString	Return type: std::string Arguments: DebugStringSorting sorting
DynamicPartition	Return type: explicit Arguments: int num_elements Creates a DynamicPartition on n elements, numbered 0..n-1. Start with the trivial partition (only one subset containing all elements).
DynamicPartition	Return type: explicit Arguments: const std::vector<int>& initial_part_of_element 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.
ElementsInHierarchicalOrder	Return type: const std::vector<int>& 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 that 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.
ElementsInPart	Return type: IterablePart Arguments: int i
ElementsInSamePartAs	Return type: IterablePart Arguments: int i A handy shortcut to ElementsInPart(PartOf(e)). The returned IterablePart will never be empty, since it contains at least i.
FprintOfPart	Return type: uint64_t Arguments: int part 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.
NumElements	Return type: int Accessors.
NumParts	Return type: const int
ParentOfPart	Return type: int Arguments: int part
PartOf	Return type: int Arguments: int element
Refine	Return type: void Arguments: const std::vector<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*?
SizeOfPart	Return type: int Arguments: int part
UndoRefineUntilNumPartsEqual	Return type: void Arguments: 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.