C++ Reference: class MergingPartition

This documentation is automatically generated.

Partition class that supports incremental merging, using the union-find algorithm (see http://en.wikipedia.org/wiki/Disjoint-set_data_structure).
Method
DebugString

Return type: std::string

Dump all components, with nodes sorted within each part and parts sorted lexicographically. Eg. "0 1 3 4 | 2 5 | 6 7 8".

FillEquivalenceClasses

Return type: int

Arguments: std::vector<int>* node_equivalence_classes

Output the whole partition as node equivalence classes: if there are K parts and N nodes, node_equivalence_classes[i] will contain the part index (a number in 0..K-1) of node #i. Parts will be sorted by their first node (i.e. node 0 will always be in part 0; then the next node that isn't in part 0 will be in part 1, and so on). Returns the number K of classes.

GetRoot

Return type: int

Arguments: int node

FOR DEBUGGING OR SPECIAL "CONST" ACCESS ONLY: Find the root of the union-find tree with leaf 'node', i.e. its representative node, but don't use path compression. The amortized complexity can be as bad as log(N), as opposed to the version using path compression.

GetRootAndCompressPath

Return type: int

Arguments: int node

Get the representative of "node" (a node in the same equivalence class, which will also be returned for any other "node" in the same class). The complexity if the same as MergePartsOf().

KeepOnlyOneNodePerPart

Return type: void

Arguments: std::vector<int>* nodes

Specialized reader API: prunes "nodes" to only keep at most one node per part: any node which is in the same part as an earlier node will be pruned.

MergePartsOf

Return type: int

Arguments: int node1, int node2

Complexity: amortized O(Ackermann⁻¹(N)) -- which is essentially O(1) -- where N is the number of nodes. Return value: If this merge caused a representative node (of either node1 or node2) to stop being a representative (because only one can remain); this method returns that removed representative. Otherwise it returns -1. Details: a smaller part will always be merged onto a larger one. Upons ties, the smaller representative becomes the overall representative.

MergingPartition

At first, all nodes are in their own singleton part.

MergingPartition

Return type: explicit

Arguments: int num_nodes

NumNodes

Return type: int

NumNodesInSamePartAs

Return type: int

Arguments: int node

Reset

Return type: void

Arguments: int num_nodes

ResetNode

Return type: void

Arguments: int node

Advanced usage: sets 'node' to be in its original singleton. All nodes who may point to 'node' as a parent will remain in an inconsistent state. This can be used to reinitialize a MergingPartition that has been sparsely modified in O(|modifications|). CRASHES IF USED INCORRECTLY.