Random Walk

ReservoirSampler.java

public class ReservoirSampler {
    private final Random random;
    private final int[] buffer;
    private int writePosition;
    private int readPosition;

    public ReservoirSampler(int size) {
        this.random = new Random();
        this.buffer = new int[size];
        this.writePosition = 0;
        this.readPosition = -1;
    }

    public void add(int node) {
        if (writePosition < buffer.length) {
            buffer[writePosition] = node;
        } else {
            final int randomPosition = random.nextInt(writePosition);

            if (randomPosition < buffer.length) {
                buffer[randomPosition] = node;
            }
        }
        writePosition++;
    }

    public int nextSample() {
        readPosition++;

        if (readPosition < buffer.length) {
            return buffer[readPosition];
        }
        throw new RuntimeException("Tried to read more samples than sample size! Sample size: " + buffer.length);
    }
}

SampledGraph.java

public class SampledGraph {
    private final Map<Integer, UniformSampler> leftToRightSmallNodes;
    private final Map<Integer, ReservoirSampler> leftToRightBigNodes;
    private final Map<Integer, AtomicInteger> degrees;
    private final Random random;
    private final int bufferSize;

    public SampledGraph(int bufferSize) {
        this.bufferSize = bufferSize;
        this.leftToRightSmallNodes = new HashMap<>();
        this.leftToRightBigNodes = new HashMap<>();
        this.degrees = new HashMap<>();
        this.random = new Random();
    }

    public void add(int source, int target) {
        degrees.putIfAbsent(source, new AtomicInteger(0));
        final int degree = degrees.get(source).incrementAndGet();

        if (degree == (bufferSize + 1)) {

            for (Integer node : leftToRightSmallNodes.keySet()) {
                removeSmallNode(node, source);
                addBigNode(node, source);
            }
        }
        if (degree <= bufferSize) {
            addSmallNode(source, target);
        } else {
            addBigNode(source, target);
        }
    }

    public List<Integer> randomWalk(int start, int length) {
        final List<Integer> nodes = new ArrayList<>();

        for (int i = 0; i < length; i++) {
            final int coinToss = random.nextInt(100);

            if (coinToss < 50) {
                try {
                    nodes.add(leftToRightSmallNodes.get(start).nextSample());
                } catch (IllegalArgumentException e) {
                    nodes.add(leftToRightBigNodes.get(start).nextSample());
                }
            } else {
                nodes.add(leftToRightBigNodes.get(start).nextSample());
            }
        }
        return nodes;
    }

    public void addSmallNode(int source, int target) {
        UniformSampler uniformSampler = leftToRightSmallNodes.getOrDefault(source, new UniformSampler(bufferSize));
        uniformSampler.add(target);
        leftToRightSmallNodes.put(source, uniformSampler);
    }

    public void removeSmallNode(int source, int target) {
        UniformSampler uniformSampler = leftToRightSmallNodes.get(source);
        uniformSampler.remove(target);
        leftToRightSmallNodes.put(source, uniformSampler);
    }

    public void addBigNode(int source, int target) {
        ReservoirSampler sampler = leftToRightBigNodes.getOrDefault(source, new ReservoirSampler(bufferSize));
        sampler.add(target);
        leftToRightBigNodes.put(source, sampler);
    }
}

SampleMain.java

public class SampleMain {
    public static void main(String[] args) {
        SampledGraph sampledGraph = new SampledGraph(10);

        for (int i = 0; i < 100; i++) {
            for (int k = 0; k < 50; k++) {
                sampledGraph.add(i, k);
            }
        }

        System.out.println(sampledGraph.randomWalk(0, 10));
    }
}

UniformSampler.java

public class UniformSampler {
    private final Random random;
    private final int size;
    private final ArrayList<Integer> buffer;

    public UniformSampler(int size) {
        this.size = size;
        this.buffer = new ArrayList<>(size);
        this.random = new Random();
    }

    public void add(int node) {
        if (buffer.size() < size) {
            buffer.add(node);
        } else {
            throw new RuntimeException("Buffer of uniform sampler is full!");
        }
    }

    public void remove(int node) {
        final int position = buffer.indexOf(node);
        if (position > -1) {
            buffer.remove(position);
        }
    }

    public int nextSample() {
        final int randomPosition = random.nextInt(buffer.size());
        return buffer.get(randomPosition);
    }
}