Template Class GenericPartition¶

Class Documentation¶

template<IntegralValue IndexType>
class GenericPartition¶

Implements a partition of a set, i.e. a subdivision of the set into disjoint subsets.

Public Functions

GenericPartition()¶

GenericPartition(IndexType z)¶

Create a new partition data structure for z elements.

Parameters:

z – [in] maximum ValueType

GenericPartition(IndexType z, IndexType defaultValue)¶

Create a new partition data structure for z elements. Initialize each entry to the default value. WARNING: this circumvents the standard interface and leaves the object in an inconsistent state if defaultValue is neither none nor 0. Use only in exceptional cases.

Parameters:

• z – [in] maximum ValueType

• defaultValue – [in]

GenericPartition(const std::vector<IndexType> &data)¶

inline void reset(IndexType newZ, IndexType defaultValue)¶

Updates the maximum index of the partition to newZ and sets all its values to defaultValue. WARNING: this leaves the object in an inconsistent state if defaultValue is neither none nor 0. Use only in exceptional cases.

Parameters:

• newZ – [in] New maximum index of the partition.

• defaultValue – [in] Default value of all the elements in the partition.

inline IndexType &operator[](IndexType e)¶

Index operator.

Parameters:

e – [in] an element

inline const IndexType &operator[](IndexType e) const¶

Index operator for const instances of this class.

Parameters:

e – [in] an element

inline IndexType subsetOf(IndexType e) const¶

Get the set (id) in which the element e is contained.

Parameters:

e – Index of element.

Returns:

The index of the set in which e is contained.

inline IndexType extend()¶

Extend the data structure and create a slot for one more element. Initializes the entry to noneIndex and returns the index of the entry.

inline void remove(IndexType e)¶

Removes the entry for the given element by setting it to noneIndex.

inline void addToSubset(IndexType s, IndexType e)¶

Add a (previously unassigned) element e to the set s.

Parameters:

• s – The index of the subset.

• e – The element to add.

inline void moveToSubset(IndexType s, IndexType e)¶

Move the (previously assigned) element e to the set s.

Parameters:

• s – The index of the subset.

• e – The element to move.

inline void toSingleton(IndexType e)¶

Creates a singleton set containing the element e.

Parameters:

e – The index of the element.

void allToSingletons()¶

Assigns every element to a singleton set. Set id is equal to element id.

void allToOnePartition()¶

Assigns every element to the same subset. Set id is equal to zero.

IndexType mergeSubsets(IndexType s, IndexType t)¶

Assigns the elements from both sets to a new set and returns the id of it.

Parameters:

• s – Set to merge.

• t – Set to merge.

Returns:

Id of newly created set.

inline void setUpperBound(IndexType upper)¶

Sets an upper bound for the subset ids that CAN be assigned.

Parameters:

upper – [in] highest assigned subset ID + 1

inline IndexType upperBound() const¶

Return an upper bound for the subset ids that have been assigned. (This is the maximum id + 1.)

Returns:

The upper bound.

inline IndexType lowerBound() const¶

Get a lower bound for the subset ids that have been assigned.

Returns:

The lower bound.

void compact(bool useTurbo = false)¶

Change subset IDs to be consecutive, starting at 0.

Parameters:

useTurbo – Default: false. If set to true, a vector instead of a map to assign new ids which results in a shorter running time but possibly a large space overhead.

inline bool contains(IndexType e) const¶

Check if partition assigns a valid subset to the element e.

Parameters:

e – The element.

Returns:

true if the assigned subset is valid, false otherwise.

inline bool inSameSubset(IndexType e1, IndexType e2) const¶

Check if two elements e1 and e2 belong to the same subset.

Parameters:

• e1 – Element.

• e2 – Element.

Returns:

true if e1 and e2 belong to same subset, false otherwise.

std::vector<count> subsetSizes() const¶

Get a list of subset sizes. Indices do not necessarily correspond to subset ids.

Returns:

A vector of subset sizes.

std::map<IndexType, count> subsetSizeMap() const¶

Get a map from subset id to size of the subset.

Returns:

A map from subset id to size of the subset.

std::set<IndexType> getMembers(IndexType s) const¶

Get the members of the subset s.

Parameters:

s – The subset.

Returns:

A set containing the members of s.

inline IndexType numberOfElements() const¶

Returns:

number of elements in the partition.

count numberOfSubsets() const¶

Get the current number of sets in this partition.

Returns:

The current number of sets.

const std::vector<IndexType> &getVector() const¶

Get the actual vector representing the partition data structure.

Returns:

vector containing information about partitions.

std::set<std::set<IndexType>> getSubsets() const¶

Returns:

the subsets of the partition as a set of sets.

std::set<IndexType> getSubsetIds() const¶

Get the ids of nonempty subsets.

Returns:

A set of ids of nonempty subsets.

inline void setName(std::string name)¶

Set a human-readable identifier name for the instance.

Parameters:

name – The name.

inline std::string getName() const¶

Get the human-readable identifier.

Returns:

The name of this partition.

template<typename Callback>
inline void forEntries(Callback func) const¶

Iterate over all entries (node, cluster id) and execute callback function func (lambda closure).

Parameters:

func – Takes parameters (node, index)

template<typename Callback>
inline void parallelForEntries(Callback handle) const¶

Iterate over all entries (node, cluster id) in parallel and execute callback function handle (lambda closure).

Parameters:

handle – Takes parameters (node, index)

Public Static Attributes

static constexpr IndexType noneIndex = std::numeric_limits<IndexType>::max()¶