class KleinbergSmallWorldGraphGenerator 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;
        }

        /*
         * Ensure directed or undirected
         */
        GraphTests.requireDirectedOrUndirected(target);
        boolean isDirected = target.getType().isDirected();

        /*
         * Create vertices
         */
        List<V> nodes = new ArrayList<>(n * n);
        for (int i = 0; i < n * n; i++) {
            V v = vertexFactory.createVertex();
            if (!target.addVertex(v)) {
                throw new IllegalArgumentException("Invalid vertex factory");
            }
            nodes.add(v);
        }

        /*
         * Add local-contacts
         */
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int vi = i * n + j;
                V v = nodes.get(vi);

                // lookup neighborhood
                for (int di = -p; di <= p; di++) {
                    for (int dj = -p; dj <= p; dj++) {
                        int t = (i + di) * n + (j + dj);
                        if (t < 0 || t == vi || t >= n * n) {
                            continue;
                        }
                        if (Math.abs(di) + Math.abs(dj) <= p && (isDirected || t > i * n + j)) {
                            target.addEdge(v, nodes.get(t));
                        }
                    }
                }
            }
        }

        /*
         * Add long-range contacts
         */
        double[] p = new double[n * n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                V v = nodes.get(i * n + j);

                /*
                 * Create inverse r power distribution
                 */
                double sum = 0d;
                for (int oi = 0; oi < n; oi++) {
                    for (int oj = 0; oj < n; oj++) {
                        if (oi != i || oj != j) {
                            double weight = Math.pow(Math.abs(i - oi) + Math.abs(j - oj), -r);
                            p[oi * n + oj] = weight;
                            sum += weight;
                        }
                    }
                }
                p[i * n + j] = 0d;
                for (int k = 0; k < n * n; k++) {
                    p[k] /= sum;
                }

                /*
                 * Sample from distribution and add long-range edges
                 */
                AliasMethodSampler sampler = new AliasMethodSampler(p, rng);
                for (int k = 0; k < q; k++) {
                    V u = nodes.get(sampler.next());
                    if (!u.equals(v) && !target.containsEdge(v, u)) {
                        target.addEdge(v, u);
                    }
                }
            }
        }
    }

    public  KleinbergSmallWorldGraphGenerator(int n, int p, int q, int r);
    public  KleinbergSmallWorldGraphGenerator(int n, int p, int q, int r, long seed);
    public  KleinbergSmallWorldGraphGenerator(int n, int p, int q, int r, Random rng);

}