src/old/clique2_ablations_compat.java

package old;

import java.util.*;
import java.util.function.Consumer;

/**
 * clique2_ablations_streaming (INTERNAL-DEGREE Q, streaming)
 *
 * Computes Q(C) = d^T L_C d with d_i = deg_C(i) (INTERNAL degree in the induced subgraph),
 * exactly and incrementally during reverse reconstruction.
 *
 * Entry point:
 *   - runLaplacianRMCStreaming(List<Integer>[] adj1Based, Consumer<SnapshotDTO> sink)
 *
 * Notes:
 * - Adjacency is 1-based on input; we convert to 0-based int[][].
 * - This implementation favors correctness; for very large graphs it may be slow.
 */
public class clique2_ablations_compat {

    public static List<SnapshotDTO> runLaplacianRMC(List<Integer>[] adj1Based) {
        ArrayList<SnapshotDTO> out = new ArrayList<>();
        runLaplacianRMCStreaming(adj1Based, out::add);
        return out;
    }

    public static void runLaplacianRMCStreaming(List<Integer>[] adj1Based,
                                                Consumer<SnapshotDTO> sink) {
        final int n = adj1Based.length - 1; // 1-based
        int[][] nbrs = new int[n][];
        int[] degFull = new int[n];
        for (int u1 = 1; u1 <= n; u1++) {
            List<Integer> lst = adj1Based[u1];
            int m = lst.size();
            int[] arr = new int[m];
            for (int i = 0; i < m; i++) arr[i] = lst.get(i) - 1;
            nbrs[u1 - 1] = arr;
            degFull[u1 - 1] = m;
        }

        // Degeneracy order (stable PQ for small, bucket for large)
        int[] order = (n <= 100_000) ? degeneracyOrderStable(nbrs, degFull)
                                     : degeneracyOrderBucket(nbrs, degFull);

        DSU dsu = new DSU(n);
        boolean[] added = new boolean[n];
        int[] degC = new int[n];              // internal degree within current induced subgraph
        // Per-component aggregates for Q = 2*(S3 - P)
        double[] S3 = new double[n];          // Σ d_i^3 per component
        double[] P  = new double[n];          // Σ_{(i,j)∈E_C} d_i d_j per component (unordered edges)

        for (int step = n - 1; step >= 0; step--) {
            final int u = order[step];
            added[u] = true;
            dsu.makeSingleton(u);

            // Gather neighbors of u already added
            int[] Nu = nbrs[u];
            int t = 0;
            for (int v : Nu) if (added[v]) t++;

            // Collect those neighbors and their current internal degrees b_v
            int[] neigh = new int[t];
            int k = 0;
            long sum_b = 0L;
            long sum_b2 = 0L;
            for (int v : Nu) {
                if (!added[v]) continue;
                neigh[k++] = v;
                int b = degC[v];
                sum_b += b;
                sum_b2 += (long) b * (long) b;
            }

            // Union u with each neighbor's component
            int ru = dsu.find(u);
            for (int i = 0; i < t; i++) {
                int rv = dsu.find(neigh[i]);
                if (ru != rv) ru = dsu.union(ru, rv);
            }

            // --- Exact Δ for Q = 2*(S3 - P) ---
            // ΔS3 = t^3 + Σ_i [(b_i+1)^3 - b_i^3] = t^3 + Σ_i [3 b_i^2 + 3 b_i + 1]
            double deltaS3 = (double) t * t * t + 3.0 * (double) sum_b2 + 3.0 * (double) sum_b + (double) t;

            // ΔP = Σ_i [ t*(b_i+1) + sN_pre(v_i) ]
            // where sN_pre(v) = Σ_{w ∈ N_C(v) before} degC(w).
            double deltaP = 0.0;
            for (int i = 0; i < t; i++) {
                int v = neigh[i];
                int b = degC[v];
                // sum degrees of neighbors w that are already added and are in the same component as v (before updating degC)
                int rv = dsu.find(v);
                long sNv = 0L;
                for (int w : nbrs[v]) {
                    if (!added[w]) continue;
                    if (dsu.find(w) != rv) continue;
                    sNv += degC[w];
                }
                deltaP += (double) t * (double) (b + 1) + (double) sNv;
            }

            // Apply deltas to component aggregates
            S3[ru] += deltaS3;
            P[ru]  += deltaP;

            // Emit snapshot for the component containing u
            int[] nodes = dsu.nodesOf(ru);
            long sumDegIn2 = dsu.sumDegIn2(ru); // 2*|E_C| == Σ d_i
            double Q = 2.0 * (S3[ru] - P[ru]);
            sink.accept(new SnapshotDTO(nodes, nodes.length, sumDegIn2, Q));

            // Now update degC for u and neighbors (for the next steps)
            degC[u] += t;
            for (int i = 0; i < t; i++) {
                int v = neigh[i];
                degC[v] += 1;
            }
        }
    }

    // ------------------------- Degeneracy Order -------------------------

    static int[] degeneracyOrderStable(int[][] nbrs, int[] deg0) {
        final int n = nbrs.length;
        int[] deg = Arrays.copyOf(deg0, n);
        boolean[] removed = new boolean[n];
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> (a[0] << 21) | a[1]));
        for (int u = 0; u < n; u++) pq.add(new long[]{deg[u], u});
        int[] order = new int[n];
        int ptr = 0;
        while (ptr < n) {
            long[] top = pq.poll();
            int du = (int) top[0];
            int u = (int) top[1];
            if (removed[u] || du != deg[u]) continue;
            removed[u] = true;
            order[ptr++] = u;
            for (int v : nbrs[u]) if (!removed[v]) {
                deg[v]--;
                pq.add(new long[]{deg[v], v});
            }
        }
        return order;
    }

    static int[] degeneracyOrderBucket(int[][] nbrs, int[] deg0) {
        final int n = nbrs.length;
        int maxDeg = 0;
        for (int d : deg0) if (d > maxDeg) maxDeg = d;

        int[] deg = Arrays.copyOf(deg0, n);
        int[] head = new int[Math.max(2, maxDeg + 2)];
        int[] next = new int[n];
        int[] prev = new int[n];
        Arrays.fill(head, -1);
        Arrays.fill(next, -1);
        Arrays.fill(prev, -1);
        for (int u = 0; u < n; u++) {
            int d = deg[u];
            next[u] = head[d];
            if (head[d] >= 0) prev[head[d]] = u;
            head[d] = u;
        }

        boolean[] removed = new boolean[n];
        int[] order = new int[n];
        int ptr = 0;
        int cur = 0;
        while (cur <= maxDeg && head[cur] < 0) cur++;

        for (int it = 0; it < n; it++) {
            while (cur <= maxDeg && head[cur] < 0) cur++;
            if (cur > maxDeg) cur = maxDeg;
            int u = head[cur];
            head[cur] = next[u];
            if (head[cur] >= 0) prev[head[cur]] = -1;
            next[u] = prev[u] = -1;
            removed[u] = true;
            order[ptr++] = u;

            for (int v : nbrs[u]) if (!removed[v]) {
                int dv = deg[v];
                int pv = prev[v], nv = next[v];
                if (pv >= 0) next[pv] = nv; else head[dv] = nv;
                if (nv >= 0) prev[nv] = pv;
                int nd = dv - 1;
                deg[v] = nd;
                next[v] = head[nd];
                if (head[nd] >= 0) prev[head[nd]] = v;
                prev[v] = -1;
                head[nd] = v;
                if (nd < cur) cur = nd;
            }
        }
        return order;
    }

    // --------------------------- DSU ---------------------------

    static final class DSU {
        final int n;
        final int[] parent;
        final int[] size;
        final long[] sumDegIn2;  // 2 * |E_C|
        final IntList[] members;

        DSU(int n) {
            this.n = n;
            this.parent = new int[n];
            this.size = new int[n];
            this.sumDegIn2 = new long[n];
            this.members = new IntList[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 0;
                sumDegIn2[i] = 0L;
                members[i] = new IntList();
            }
        }

        void makeSingleton(int u) {
            parent[u] = u;
            size[u] = 1;
            sumDegIn2[u] = 0L;
            members[u].clear();
            members[u].add(u);
        }

        int find(int x) {
            int r = x;
            while (r != parent[r]) r = parent[r];
            int y = x;
            while (y != r) { int p = parent[y]; parent[y] = r; y = p; }
            return r;
        }

        int union(int ra, int rb) {
            ra = find(ra); rb = find(rb);
            if (ra == rb) return ra;
            if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
            parent[rb] = ra;
            size[ra] += size[rb];
            sumDegIn2[ra] += sumDegIn2[rb];
            members[ra].addAll(members[rb]);
            members[rb].clear();
            return ra;
        }

        long sumDegIn2(int r) { return sumDegIn2[find(r)]; }

        int[] nodesOf(int r) {
            return members[find(r)].toArray();
        }
    }

    // Simple dynamic int list
    static final class IntList {
        int[] a; int sz;
        IntList() { a = new int[4]; sz = 0; }
        void clear() { sz = 0; }
        void add(int x) { if (sz == a.length) a = Arrays.copyOf(a, sz << 1); a[sz++] = x; }
        void addAll(IntList other) {
            if (other.sz == 0) return;
            int need = sz + other.sz;
            if (need > a.length) {
                int cap = a.length;
                while (cap < need) cap <<= 1;
                a = Arrays.copyOf(a, cap);
            }
            System.arraycopy(other.a, 0, a, sz, other.sz);
            sz = need;
        }
        int[] toArray() { return Arrays.copyOf(a, sz); }
    }

    // ------------------------- Snapshot DTO -------------------------

    public static final class SnapshotDTO {
        public final int[] nodes;   // 0-based ids
        public final int nC;        // |C|
        public final long sumDegIn; // 2 * |E(C)|
        public final double Q;      // EXACT internal-degree Q = d^T L_C d

        public SnapshotDTO(int[] nodes, int nC, long sumDegIn, double Q) {
            this.nodes = nodes;
            this.nC = nC;
            this.sumDegIn = sumDegIn;
            this.Q = Q;
        }
    }
}