omni::graph::exec::unstable::PartitionSet

Defined in omni/graph/exec/unstable/PartitioningUtils.h

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.