quickPartitioning#

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

template<typename VerifyAndCreateFn>
void omni::graph::exec::unstable::quickPartitioning(
ITopology *topology,
Span<INode*> selectedNodes,
VerifyAndCreateFn &&verifyAndCommitPartitionFn,
)#

Algorithm to group selected nodes into valid partitions based on node ordering.

Partition is only valid when there is no path that leaves and comes back to the same group. Such partition would introduce cycles in the graph.

Quick algorithm uses a single traversal over the entire graph to determine unique partition index for group of nodes. During traversal, the partition index is based on the node the traversal comes from and:

  • the partition index is incremented by 1 if edge crosses selected and unselected nodes

  • the partition index is assigned to the currently visited node only if it is higher than currently set

The traversal algorithm visits all the edges in the graph and does continuation on the last visit to the node.

On this page