src/old/clique2_ablations_parallel.java

package old;

import java.io.FileReader;
import java.io.IOException;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.Consumer;
import java.util.stream.IntStream;

public class clique2_ablations_parallel {
    static int n, m;

    public static List<SnapshotDTO> main(String[] args) throws Exception {
        if (args.length < 2) {
            System.err.println("Usage: java clique2_ablations <epsilon> <inputfile>");
        }
        final double EPS = Double.parseDouble(args[0]);

        Scanner r;
        try {
            r = new Scanner(new FileReader(args[1]));
        } catch (IOException e) {
            System.err.println("Could not open " + args[1] + ". Falling back to stdin.");
            r = new Scanner(System.in);
        }

        n = r.nextInt();
        m = r.nextInt();

        @SuppressWarnings("unchecked")
        List<Integer>[] adj = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int a = r.nextInt(), b = r.nextInt();
            adj[a].add(b);
            adj[b].add(a);
        }
        r.close();

        long t0 = System.nanoTime();
        List<SnapshotDTO> res = runLaplacianRMC(adj);
        long t1 = System.nanoTime();

        System.out.printf(Locale.US, "Runtime: %.3f ms%n", (t1 - t0) / 1_000_000.0);
        return res;
    }

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

    /**
     * Optimized O(Mk) algorithm with performance improvements.
     */
    public static List<SnapshotDTO> runLaplacianRMCStreaming(List<Integer>[] adj,
                                                             Consumer<SnapshotDTO> sink) {
        final int n = adj.length - 1;

        // Phase 1: peeling (same as before)
        int[] deg0 = new int[n + 1];
        PriorityQueue<Pair> pq = new PriorityQueue<>();
        for (int i = 1; i <= n; i++) {
            deg0[i] = adj[i].size();
            pq.add(new Pair(i, deg0[i]));
        }
        Deque<Integer> peelStack = new ArrayDeque<>(n);
        while (!pq.isEmpty()) {
            Pair p = pq.poll();
            if (p.degree != deg0[p.node]) continue;
            peelStack.push(p.node);
            for (int v : adj[p.node]) {
                if (deg0[v] > 0) {
                    deg0[v]--;
                    pq.add(new Pair(v, deg0[v]));
                }
            }
            deg0[p.node] = 0;
        }

        // Build addition order and index
        int[] addOrder = new int[n];
        int[] idx = new int[n + 1];
        for (int t = 0; t < n; t++) {
            int u = peelStack.pop();
            addOrder[t] = u;
            idx[u] = t;
        }

        // Phase 1.5: orient edges by idx and sort successors
        @SuppressWarnings("unchecked")
        ArrayList<Integer>[] succ = new ArrayList[n + 1];
        @SuppressWarnings("unchecked")
        ArrayList<Integer>[] pred = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            succ[i] = new ArrayList<>();
            pred[i] = new ArrayList<>();
        }

        // Parallelize edge orientation
        IntStream.rangeClosed(1, n).parallel().forEach(u -> {
            for (int v : adj[u]) {
                if (u < v) {
                    if (idx[u] < idx[v]) {
                        synchronized(succ[u]) { succ[u].add(v); }
                        synchronized(pred[v]) { pred[v].add(u); }
                    } else {
                        synchronized(succ[v]) { succ[v].add(u); }
                        synchronized(pred[u]) { pred[u].add(v); }
                    }
                }
            }
        });

        // Parallel sorting
        IntStream.rangeClosed(1, n).parallel().forEach(v -> {
            if (succ[v].size() > 1) {
                succ[v].sort(Comparator.comparingInt(w -> idx[w]));
            }
        });

        // Phase 2: reverse reconstruction with optimizations
        DSU dsu = new DSU(n);
        int[] deg = new int[n + 1];
        long[] predSum = new long[n + 1];

        // Optimized component tracking with ArrayList
        @SuppressWarnings("unchecked")
        ArrayList<Integer>[] compNodes = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) compNodes[i] = new ArrayList<>();

        // Reusable temporary array for node lists
        int[] tempNodes = new int[100]; // Start small, will grow as needed

        // Use original linear search (more reliable than binary search)
        final SumSucc sumSucc = new SumSucc(succ, idx, deg);

        List<SnapshotDTO> recon = new ArrayList<>();

        int step = 1;
        for (int u : addOrder) {
            System.out.println("# Step " + step);
            dsu.makeIfNeeded(u);
            long Su = 0L;
            final int Tu = idx[u];

            compNodes[u].add(u);

            // connect u to all its predecessors (earlier neighbors)
            for (int v : pred[u]) {
                long a = deg[u];
                long b = deg[v];

                // S_v = pred_sum[v] + sum of deg[w] for successors w of v with idx[w] < idx[u]
                long Sv = predSum[v] + sumSucc.until(v, Tu);

                long dQu = 2L * a * a - 2L * Su + a;
                long dQv = 2L * b * b - 2L * Sv + b;
                long edgeTerm = (a - b) * (a - b);

                int ru = dsu.find(u);
                int rv = dsu.find(v);

                dsu.Q[ru] += (double) dQu;
                dsu.Q[rv] += (double) dQv;

                int r;
                if (ru != rv) {
                    r = dsu.union(ru, rv);
                    dsu.Q[r] += (double) edgeTerm;
                    int o = (r == ru) ? rv : ru;
                    compNodes[r].addAll(compNodes[o]);
                    compNodes[o].clear();
                } else {
                    r = ru;
                    dsu.Q[r] += (double) edgeTerm;
                }

                // degree increments
                deg[u] += 1;
                deg[v] += 1;

                // Update sumDeg for the component
                dsu.sumDeg[r] += 2;

                // push +1 to predSum of successors (outdegree ≤ k)
                for (int y : succ[u]) predSum[y] += 1;
                for (int y : succ[v]) predSum[y] += 1;

                // maintain Su: add deg[v] AFTER its increment
                Su += deg[v];
            }

            // Efficient node array creation
            int r = dsu.find(u);
            int compSize = compNodes[r].size();
            if (tempNodes.length < compSize) {
                tempNodes = new int[compSize];
            }
            for (int i = 0; i < compSize; i++) {
                tempNodes[i] = compNodes[r].get(i) - 1;
            }
            Arrays.sort(tempNodes, 0, compSize);
            int[] nodes = Arrays.copyOf(tempNodes, compSize);

            int compId = dsu.componentId(r);
            SnapshotDTO snap = new SnapshotDTO(compId, nodes, nodes.length, dsu.sumDeg[r], dsu.Q[r]);
            sink.accept(snap);

            step++;
        }

        return recon;
    }

    // Keep original linear search for SumSucc - more reliable
    static final class SumSucc {
        final ArrayList<Integer>[] succ;
        final int[] idx;
        final int[] deg;

        SumSucc(ArrayList<Integer>[] succ, int[] idx, int[] deg) {
            this.succ = succ;
            this.idx = idx;
            this.deg = deg;
        }

        /** Sum of deg[w] over successors w of v with idx[w] < T (succ[v] sorted by idx). */
        long until(int v, int T) {
            long s = 0L;
            final ArrayList<Integer> sv = succ[v];
            final int sz = sv.size();
            for (int i = 0; i < sz; i++) {
                int w = sv.get(i);
                if (idx[w] >= T) break; // since sorted by idx, we can break early
                s += deg[w];
            }
            return s;
        }
    }

    // Original helper classes (unchanged)
    static class Result {
        double bestSL;
        int bestRoot;
    }

    static class Pair implements Comparable<Pair> {
        final int node, degree;
        Pair(int node, int degree) { this.node = node; this.degree = degree; }
        public int compareTo(Pair o) {
            if (degree != o.degree) return Integer.compare(degree, o.degree);
            return Integer.compare(node, o.node);
        }
    }

    static class DSU {
        final int[] parent;
        final int[] size;
        final boolean[] made;
        final double[] Q;
        final int[] sumDeg;
        final int[] compId;        // compId[root] > 0 iff the root represents a live component
        int nextCompId = 1;        // 1-based; 0 means "unassigned"

        DSU(int n) {
            parent = new int[n + 1];
            size = new int[n + 1];
            made = new boolean[n + 1];
            Q = new double[n + 1];
            sumDeg = new int[n + 1];
            compId = new int[n + 1];
        }
        void makeIfNeeded(int v) {
            if (!made[v]) {
                made[v] = true;
                parent[v] = v;
                size[v] = 1;
                Q[v] = 0.0;
                sumDeg[v] = 0;
                if (compId[v] == 0) compId[v] = nextCompId++;
            }
        }
        int find(int v) {
            if (!made[v]) return v;
            if (parent[v] != v) parent[v] = find(parent[v]);
            return parent[v];
        }
        int union(int a, int b) {
            makeIfNeeded(a);
            makeIfNeeded(b);
            int ra = find(a), rb = find(b);
            if (ra == rb) return ra;
            if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
            parent[rb] = ra;
            size[ra] += size[rb];
            Q[ra] += Q[rb];
            sumDeg[ra] += sumDeg[rb];

            int aId = compId[ra], bId = compId[rb];
            int keep = (aId == 0) ? bId : (bId == 0 ? aId : Math.min(aId, bId));
            compId[ra] = keep;
            compId[rb] = 0;  // retire loser id

            return ra;
        }

        int componentId(int v) { return compId[find(v)]; }
    }

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