C++ Reference: class DynamicPartition

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

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.