How to linearize your cluster

Lagrang3 · April 5, 2025, 9:20pm

I was implementing a proof of concept myself, just to get some understanding of GGT.

examples/maxfeerate-ggt.cpp

e298019aa

/* Maximum feerate closure.
 *
 * Input:
 * N M // N: number of transactions, M: number of dependencies
 * f_i, z_i // N lines, one for each transaction, f_i: the fee of transaction i,
 * z_i: the size of transaction i
 * a_i b_i // M lines, one for each dependency, a_i depends on b_i.
 * */

#include <algorithm>
#include <cassert>
#include <iostream>
#include <queue>
#include <span>
#include <sstream>
#include <vector>

#include "clusterlinearize.h"

int can_reach_sink(std::span<const int> dependency,

This file has been truncated. show original

I will love to see through your code.

I think there might be a little optimization gain if we consider the fact that the graph is bipartite. Nodes have either a non-zero capacity arc with the source or the sink but not both. If we classify nodes this way, let’s say into set N1 (nodes connected to the source) and N2 (nodes connected to the sink) we also realize that we can ignore arcs that go from N1 to N1, and N2 to N2, why is that? because for any arc that connects nodes a and b (in N1 for instance) that arc either:

case 1, does NOT carry any flow in the final solution, so it can be ignored,

case 2, it DOES carry some flow, but that means that there exist some node c in N2 for which a and b have an arc with (by the dependency transitivity) so we might as well deviate that flow directly from a to c and not use arc a-b, this can be done since these arcs have infinite capacity.

Similarly with N2-N2 arcs.

I might be wrong though, but I think it is an interesting idea worth exploring.