clusterlin: add reordering support for DepGraph

Add a DepGraph(depgraph, reordering) function that constructs a new DepGraph
corresponding to an old one, but with its transactions is a modified order
(given as a vector from old to new positions).

Also use this reordering feature inside DepGraphFormatter::Unser, which needs
a small modification so that its reordering mapping is old-to-new (rather than
the new-to-old it used before).

1 files changed, 22 insertions, 0 deletions

diff --git a/src/cluster_linearize.h b/src/cluster_linearize.h
index a52ea5c379..7e74460c7e 100644
--- a/src/cluster_linearize.h
+++ b/src/cluster_linearize.h
@@ -118,6 +118,28 @@ public:
         }
     }
 
+    /** Construct a DepGraph object given another DepGraph and a mapping from old to new.
+     *
+     * Complexity: O(N^2) where N=depgraph.TxCount().
+     */
+    DepGraph(const DepGraph<SetType>& depgraph, Span<const ClusterIndex> mapping) noexcept : entries(depgraph.TxCount())
+    {
+        Assert(mapping.size() == depgraph.TxCount());
+        // Fill in fee, size, ancestors.
+        for (ClusterIndex i = 0; i < depgraph.TxCount(); ++i) {
+            const auto& input = depgraph.entries[i];
+            auto& output = entries[mapping[i]];
+            output.feerate = input.feerate;
+            for (auto j : input.ancestors) output.ancestors.Set(mapping[j]);
+        }
+        // Fill in descendant information.
+        for (ClusterIndex i = 0; i < entries.size(); ++i) {
+            for (auto j : entries[i].ancestors) {
+                entries[j].descendants.Set(i);
+            }
+        }
+    }
+
     /** Get the number of transactions in the graph. Complexity: O(1). */
     auto TxCount() const noexcept { return entries.size(); }
     /** Get the feerate of a given transaction i. Complexity: O(1). */