class WattsStrogatzGraphGenerator implements GraphGenerator<V, E, V> {

    @Override
    public void generateGraph(
        Graph<V, E> target, VertexFactory<V> vertexFactory, Map<String, V> resultMap)
    {
        // special cases
        if (n == 0) {
            return;
        } else if (n == 1) {
            target.addVertex(vertexFactory.createVertex());
            return;
        }

        // create ring lattice
        List<V> ring = new ArrayList<>(n);
        Map<V, List<E>> adj = new LinkedHashMap<>(n);

        for (int i = 0; i < n; i++) {
            V v = vertexFactory.createVertex();
            if (!target.addVertex(v)) {
                throw new IllegalArgumentException("Invalid vertex factory");
            }
            ring.add(v);
            adj.put(v, new ArrayList<>(k));
        }

        for (int i = 0; i < n; i++) {
            V vi = ring.get(i);
            List<E> viAdj = adj.get(i);

            for (int j = 1; j <= k / 2; j++) {
                viAdj.add(target.addEdge(vi, ring.get((i + j) % n)));
            }
        }

        // re-wire edges
        for (int r = 0; r < k / 2; r++) {
            for (int i = 0; i < n; i++) {
                V v = ring.get(i);
                E e = adj.get(i).get(r);

                if (rng.nextDouble() < p) {
                    V other = ring.get(rng.nextInt(n));
                    if (!other.equals(v) && !target.containsEdge(v, other)) {
                        if (!addInsteadOfRewire) {
                            target.removeEdge(e);
                        }
                        target.addEdge(v, other);
                    }
                }
            }
        }

    }

    public  WattsStrogatzGraphGenerator(int n, int k, double p);
    public  WattsStrogatzGraphGenerator(int n, int k, double p, long seed);
    public  WattsStrogatzGraphGenerator(
        int n, int k, double p, boolean addInsteadOfRewire, Random rng);

}