Method GroupClusters

src/txgraph.cpp:1856–2066

}

void TxGraphImpl::GroupClusters(int level) noexcept
{
    auto& clusterset = GetClusterSet(level);
    // If the groupings have been computed already, nothing is left to be done.
    if (clusterset.m_group_data.has_value()) return;

    // Before computing which Clusters need to be merged together, first apply all removals and
    // split the Clusters into connected components. If we would group first, we might end up
    // with inefficient and/or oversized Clusters which just end up being split again anyway.
    SplitAll(level);

    /** Annotated clusters: an entry for each Cluster, together with the sequence number for the
     *  representative for the partition it is in (initially its own, later that of the
     *  to-be-merged group). */
    std::vector<std::pair<Cluster*, uint64_t>> an_clusters;
    /** Annotated dependencies: an entry for each m_deps_to_add entry (excluding ones that apply
     *  to removed transactions), together with the sequence number of the representative root of
     *  Clusters it applies to (initially that of the child Cluster, later that of the
     *  to-be-merged group). */
    std::vector<std::pair<std::pair<GraphIndex, GraphIndex>, uint64_t>> an_deps;

    // Construct an an_clusters entry for every oversized cluster, including ones from levels below,
    // as they may be inherited in this one.
    for (int level_iter = 0; level_iter <= level; ++level_iter) {
        for (auto& cluster : GetClusterSet(level_iter).m_clusters[int(QualityLevel::OVERSIZED_SINGLETON)]) {
            auto graph_idx = cluster->GetClusterEntry(0);
            auto cur_cluster = FindCluster(graph_idx, level);
            if (cur_cluster == nullptr) continue;
            an_clusters.emplace_back(cur_cluster, cur_cluster->m_sequence);
        }
    }

    // Construct a an_clusters entry for every parent and child in the to-be-applied dependencies,
    // and an an_deps entry for each dependency to be applied.
    an_deps.reserve(clusterset.m_deps_to_add.size());
    for (const auto& [par, chl] : clusterset.m_deps_to_add) {
        auto par_cluster = FindCluster(par, level);
        auto chl_cluster = FindCluster(chl, level);
        // Skip dependencies for which the parent or child transaction is removed.
        if (par_cluster == nullptr || chl_cluster == nullptr) continue;
        an_clusters.emplace_back(par_cluster, par_cluster->m_sequence);
        // Do not include a duplicate when parent and child are identical, as it'll be removed
        // below anyway.
        if (chl_cluster != par_cluster) an_clusters.emplace_back(chl_cluster, chl_cluster->m_sequence);
        // Add entry to an_deps, using the child sequence number.
        an_deps.emplace_back(std::pair{par, chl}, chl_cluster->m_sequence);
    }
    // Sort and deduplicate an_clusters, so we end up with a sorted list of all involved Clusters
    // to which dependencies apply, or which are oversized.
    std::ranges::sort(an_clusters, [](auto& a, auto& b) noexcept { return a.second < b.second; });
    an_clusters.erase(std::ranges::unique(an_clusters).begin(), an_clusters.end());
    // Sort an_deps by applying the same order to the involved child cluster.
    std::ranges::sort(an_deps, [&](auto& a, auto& b) noexcept { return a.second < b.second; });

    // Run the union-find algorithm to find partitions of the input Clusters which need to be
    // grouped together. See https://en.wikipedia.org/wiki/Disjoint-set_data_structure.
    {
        /** Each PartitionData entry contains information about a single input Cluster. */