operations_research::MergingPartition Class Reference

#include <dynamic_partition.h>

Public Member Functions
	MergingPartition ()
	At first, all nodes are in their own singleton part.
	MergingPartition (int num_nodes)
void	Reset (int num_nodes)
int	NumNodes () const
int	MergePartsOf (int node1, int node2)
int	GetRootAndCompressPath (int node)
void	KeepOnlyOneNodePerPart (std::vector< int > *nodes)
int	FillEquivalenceClasses (std::vector< int > *node_equivalence_classes)
std::string	DebugString ()
void	ResetNode (int node)
int	NumNodesInSamePartAs (int node)
int	GetRoot (int node) const

Detailed Description

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

Definition at line 199 of file dynamic_partition.h.

Constructor & Destructor Documentation

MergingPartition() [1/2]

operations_research::MergingPartition::MergingPartition ( )

inline

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

Definition at line 202 of file dynamic_partition.h.

MergingPartition() [2/2]

operations_research::MergingPartition::MergingPartition ( int num_nodes )

inlineexplicit

Definition at line 203 of file dynamic_partition.h.

Member Function Documentation

DebugString()

std::string operations_research::MergingPartition::DebugString

(

)

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

Note

typically, a lot of elements of "sorted_parts" will be empty, but these won't be visible in the string that we construct below.

Definition at line 279 of file dynamic_partition.cc.

FillEquivalenceClasses()

int operations_research::MergingPartition::FillEquivalenceClasses

(

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.

Definition at line 264 of file dynamic_partition.cc.

GetRoot()

int operations_research::MergingPartition::GetRoot ( int node ) const

inline

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.

Definition at line 341 of file dynamic_partition.h.

GetRootAndCompressPath()

int operations_research::MergingPartition::GetRootAndCompressPath

(

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().

Definition at line 240 of file dynamic_partition.cc.

KeepOnlyOneNodePerPart()

void operations_research::MergingPartition::KeepOnlyOneNodePerPart

(

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.

Clean up the tmp_part_bit_ vector. Since we've already compressed the paths (if backtracking was enabled), no need to do it again.

Definition at line 248 of file dynamic_partition.cc.

MergePartsOf()

int operations_research::MergingPartition::MergePartsOf	(	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.

Attach the smaller part to the larger one. Break ties by root index.

Update the part size. Don't change part_size_[root2]: it won't be used again by further merges.

Definition at line 216 of file dynamic_partition.cc.

NumNodes()

int operations_research::MergingPartition::NumNodes ( ) const

inline

Definition at line 206 of file dynamic_partition.h.

NumNodesInSamePartAs()

int operations_research::MergingPartition::NumNodesInSamePartAs ( int node )

inline

Definition at line 247 of file dynamic_partition.h.

Reset()

void operations_research::MergingPartition::Reset

(

int

num_nodes

)

Definition at line 208 of file dynamic_partition.cc.

ResetNode()

void operations_research::MergingPartition::ResetNode ( int node )

inline

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.

Definition at line 366 of file dynamic_partition.h.

---

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

• ortools/algorithms/dynamic_partition.h
• ortools/algorithms/dynamic_partition.cc