1"""Laplacian-coherence coreset sampler using adjacency lists only."""
 2import math, random
 3
 4class LaplacianColumns:
 5    def __init__(self, adjacency):
 6        self.adj = adjacency
 7        self.degree = [sum(w for _, w in nbrs) for nbrs in adjacency]
 8        self.norm2 = [self.degree[i] ** 2 + sum(w*w for _, w in adjacency[i])
 9                      for i in range(len(adjacency))]
10    def column(self, i):
11        d = {i: self.degree[i]}
12        for j, w in self.adj[i]:
13            d[j] = d.get(j, 0.0) - w
14        return d
15    def dot(self, i, j):
16        # Iterate through the smaller support; this is the sparse operation.
17        a, b = self.column(i), self.column(j)
18        if len(a) > len(b): a, b = b, a
19        return sum(x * b.get(k, 0.0) for k, x in a.items())
20    def coherence(self, i, j, eps=1e-12):
21        return abs(self.dot(i, j)) / (math.sqrt(self.norm2[i]*self.norm2[j]) + eps)
22
23def coherent_sample(columns, candidates, batch_size, rng):
24    """Greedy min-max coherence selection from one candidate pool."""
25    if batch_size > len(candidates):
26        raise ValueError("batch_size cannot exceed candidate pool")
27    pool = list(candidates)
28    first = pool[rng.randrange(len(pool))]
29    selected = [first]
30    remaining = set(pool); remaining.remove(first)
31    while len(selected) < batch_size:
32        # Refreshing candidates can be added by calling this function repeatedly;
33        # this implementation matches one candidate pool per minibatch.
34        best = min(remaining, key=lambda i: max(columns.coherence(i, j)
35                                                for j in selected))
36        selected.append(best); remaining.remove(best)
37    return selected
38
39def uniform_sample(n, batch_size, rng):
40    return rng.sample(range(n), batch_size)