cluster_linearize::PostLinearize

Improve a given linearization.

Synopsis

Declared in <cluster_linearize.h>

template<typename SetType>
void
PostLinearize(
    DepGraph<SetType> const& depgraph,
    std::span<DepGraphIndex> linearization);

Description

Postlinearization guarantees:

  • The resulting chunks are connected.

  • If the input has a tree shape (either all transactions have at most one child, or all transactions have at most one parent), the result is optimal.

  • Given a linearization L1 and a leaf transaction T in it. Let L2 be L1 with T moved to the end, optionally with its fee increased. Let L3 be the postlinearization of L2. L3 will be at least as good as L1. This means that replacing transactions with same-size higher-fee transactions will not worsen linearizations through a "drop conflicts, append new transactions, postlinearize" process.

Parameters

NameDescription
depgraph [in]Dependency graph of the cluster being linearized.
linearization [inout]On input, an existing linearization for depgraph. On output, a potentially better linearization for the same graph.