Repository: bitcoin/bitcoin
File: src/cluster_linearize.h (C/C++)

Code before:
 *                                old_linearization is topologically valid.
 * @return                        A tuple of:
 *                                - The resulting linearization. It is guaranteed to be at least as
 *                                  good (in the feerate diagram sense) as old_linearization.
 *                                - A boolean indicating whether the result is guaranteed to be
 *                                  optimal.
 *                                - How many optimization steps were actually performed.
 */
template<typename SetType>
std::tuple<std::vector<DepGraphIndex>, bool, uint64_t> Linearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations, uint64_t rng_seed, std::span<const DepGraphIndex> old_linearization = {}, bool is_topological = true) noexcept
{
    /** Initialize a spanning forest data structure for this cluster. */
    SpanningForestState forest(depgraph, rng_seed);
    if (!old_linearization.empty()) {
        forest.LoadLinearization(old_linearization);
        if (!is_topological) forest.MakeTopological();
    } else {
        forest.MakeTopological();
    }
    // Make improvement steps to it until we hit the max_iterations limit, or an optimal result
    // is found.
    if (forest.GetCost() < max_iterations) {
        forest.StartOptimizing();
        do {
            if (!forest.OptimizeStep()) break;
        } while (forest.GetCost() < max_iterations);
    }
    // Make chunk minimization steps until we hit the max_iterations limit, or all chunks are
    // minimal.
    bool optimal = false;
    if (forest.GetCost() < max_iterations) {
        forest.StartMinimizing();
        do {
            if (!forest.MinimizeStep()) {
                optimal = true;
                break;
            }
        } while (forest.GetCost() < max_iterations);
    }
    return {forest.GetLinearization(), optimal, forest.GetCost()};
}

/** Improve a given linearization.
 *
 * @param[in]     depgraph       Dependency graph of the cluster being linearized.
 * @param[in,out] linearization  On input, an existing linearization for depgraph. On output, a
 *                               potentially better linearization for the same graph.
 *
 * Postlinearization guarantees:
 * - The resulting chunks are connected.
 * - If the input has a tree shape (either all transactions have at most one child, or all

Review comment (suggestion):
`Linearize()` description of the return tuples "optimal" value should pedantically say the result is minimal as well

Code after:
 * @param[in] is_topological      (Only relevant if old_linearization is not empty) Whether
 *                                old_linearization is topologically valid.
 * @return                        A tuple of:
 *                                - The resulting linearization. It is guaranteed to be at least as
 *                                  good (in the feerate diagram sense) as old_linearization.
 *                                - A boolean indicating whether the result is guaranteed to be
 *                                  optimal with minimal chunks.
 *                                - How many optimization steps were actually performed.
 */
template<typename SetType>
std::tuple<std::vector<DepGraphIndex>, bool, uint64_t> Linearize(const DepGraph<SetType>& depgraph, uint64_t max_iterations, uint64_t rng_seed, std::span<const DepGraphIndex> old_linearization = {}, bool is_topological = true) noexcept
{
    /** Initialize a spanning forest data structure for this cluster. */
    SpanningForestState forest(depgraph, rng_seed);
    if (!old_linearization.empty()) {
        forest.LoadLinearization(old_linearization);
        if (!is_topological) forest.MakeTopological();
    } else {
        forest.MakeTopological();
    }
    // Make improvement steps to it until we hit the max_iterations limit, or an optimal result
    // is found.
    if (forest.GetCost() < max_iterations) {
        forest.StartOptimizing();
        do {
            if (!forest.OptimizeStep()) break;
        } while (forest.GetCost() < max_iterations);
    }
    // Make chunk minimization steps until we hit the max_iterations limit, or all chunks are
    // minimal.
    bool optimal = false;
    if (forest.GetCost() < max_iterations) {
        forest.StartMinimizing();
        do {
            if (!forest.MinimizeStep()) {
                optimal = true;
                break;
            }
        } while (forest.GetCost() < max_iterations);
    }
    return {forest.GetLinearization(), optimal, forest.GetCost()};
}

/** Improve a given linearization.
 *
 * @param[in]     depgraph       Dependency graph of the cluster being linearized.
 * @param[in,out] linearization  On input, an existing linearization for depgraph. On output, a
 *                               potentially better linearization for the same graph.
 *
 * Postlinearization guarantees:
 * - The resulting chunks are connected.