PartitionSet#

Fully qualified name: omni::graph::exec::unstable::PartitionSet

class PartitionSet#

Specialized container to enable partitioning algorithm via disjoint set like data structure.

Modifications to typically known algorithm (https://en.wikipedia.org/wiki/Disjoint-set_data_structure)

index set “0” is a special one and matching the root of the graph, i.e. root node will always have index 0
only “selected” nodes are inserted into sets and only these nodes are merged to form groups of nodes based on partitioning algorithm

This object is not ABI-safe.

Public Functions

inline PartitionSet(std::size_t topologyNodeCount) noexcept#: Construct a set for a static topology of a given topologyNodeCount nodes.

template<typename V> inline void makeSelectedSets(V &selected)#: Initialize selected nodes.

inline bool isMarked(INode *node) const#: Return true is give node is selected for partitioning and has a set allocated.

inline uint64_t find(INode *node)#: Find the set this node belongs to. Forwards the call to underlying implementation.

inline void merge(INode *nodeA, INode *nodeB)#: Merge two sets. Forwards the call to underlying implementation.

inline uint64_t find(uint64_t index)#

Find set that this index belongs to.

Search has a side effect, i.e. it flattens the set links directly to the last link in the chain. This allows for faster search next time same find is performed.

inline void merge(uint64_t a, uint64_t b)#

Merge two sets.

Implementation uses rank to prioritize merging into sets that received more merges. This improves the search time.

Public Members

std::vector<uint64_t> m_parent#: We have as many elements as nodes in the topology. Each element represents a unique set (if it points to its own index), or a link to another set (if merged)

std::vector<uint64_t> m_rank#: Rank per element used to prevent growing the tree to high and optimizes searches.