gmx::UnionFinder Class Reference

#include <gromacs/trajectoryanalysis/modules/unionfind.h>

Description

Union-find data structure for keeping track of disjoint sets.

Union-find keeps track of a number of items, represented here by continuous integer indices starting at zero, and supports the following operations:

• Initialization puts each item into a set of its own.
• Given two items, merge the sets that contain these items.
• Given an item, find a representative item that is in the same set, such that queries for items in the same set yield the same value. Merging and querying is supported in amortized constant time.

Note that in order to achieve the amortized behavior, querying the structure modifies the internal state, but does not alter the externally visible behavior.

Public Member Functions
void	init (int count)
	Initializes count items, putting each in its own set.
void	merge (int item1, int item2)
	Merges sets that contain two given items. More...
int	representativeItem (int item)
	Returns a representative item from the set containing item.
std::vector< int >	allSizes ()
	Returns the sizes of all sets (in arbitrary order).

Member Function Documentation

void gmx::UnionFinder::merge ( int  item1, int  item2  )

inline

Merges sets that contain two given items.

If the items are already in the same set, nothing happens.

---

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

• src/gromacs/trajectoryanalysis/modules/unionfind.h