Skip to content

cluster mempool: merging & postprocessing of linearizations

Placeholder Pieter Wuille requested to merge github/fork/sipa/202406_clusterlin_meta into master

Part of cluster mempool: #30289

Depends on #30126, and was split off from it. #28676 depends on this.

This adds the algorithms for merging & postprocessing linearizations.

The PostLinearize(depgraph, linearization) function performs an in-place improvement of linearization, using two iterations of the Linearization post-processing algorithm. The first running from back to front, the second from front to back.

The MergeLinearizations(depgraph, linearization1, linearization2) function computes a new linearization for the provided cluster, given two existing linearizations for that cluster, which is at least as good as both inputs. The algorithm is described at a high level in merging incomparable linearizations.

For background and references, see Introduction to cluster linearization.

Merge request reports