2 package edu.uci.ics.jung.algorithms.generators.random;
5 * Copyright (c) 2009, the JUNG Project and the Regents of the University
9 * This software is open-source under the BSD license; see either
11 * http://jung.sourceforge.net/license.txt for a description.
14 import java.util.HashMap;
16 import java.util.Random;
18 import org.apache.commons.collections15.Factory;
20 import edu.uci.ics.jung.algorithms.generators.Lattice2DGenerator;
21 import edu.uci.ics.jung.algorithms.util.WeightedChoice;
22 import edu.uci.ics.jung.graph.Graph;
25 * Graph generator that produces a random graph with small world properties.
26 * The underlying model is an mxn (optionally toroidal) lattice. Each node u
27 * has four local connections, one to each of its neighbors, and
28 * in addition 1+ long range connections to some node v where v is chosen randomly according to
29 * probability proportional to d^-alpha where d is the lattice distance between u and v and alpha
30 * is the clustering exponent.
32 * @see "Navigation in a small world J. Kleinberg, Nature 406(2000), 845."
33 * @author Joshua O'Madadhain
35 public class KleinbergSmallWorldGenerator<V, E> extends Lattice2DGenerator<V, E> {
36 private double clustering_exponent;
37 private Random random;
38 private int num_connections = 1;
42 * @param graph_factory
43 * @param vertex_factory
46 * @param clusteringExponent
48 public KleinbergSmallWorldGenerator(Factory<? extends Graph<V,E>> graph_factory, Factory<V> vertex_factory,
49 Factory<E> edge_factory, int latticeSize, double clusteringExponent)
51 this(graph_factory, vertex_factory, edge_factory, latticeSize, latticeSize, clusteringExponent);
55 * @param graph_factory
56 * @param vertex_factory
60 * @param clusteringExponent
62 public KleinbergSmallWorldGenerator(Factory<? extends Graph<V,E>> graph_factory, Factory<V> vertex_factory,
63 Factory<E> edge_factory, int row_count, int col_count, double clusteringExponent)
65 super(graph_factory, vertex_factory, edge_factory, row_count, col_count, true);
66 clustering_exponent = clusteringExponent;
71 * @param graph_factory
72 * @param vertex_factory
76 * @param clusteringExponent
79 public KleinbergSmallWorldGenerator(Factory<? extends Graph<V,E>> graph_factory, Factory<V> vertex_factory,
80 Factory<E> edge_factory, int row_count, int col_count, double clusteringExponent,
83 super(graph_factory, vertex_factory, edge_factory, row_count, col_count, isToroidal);
84 clustering_exponent = clusteringExponent;
88 private void initialize()
90 this.random = new Random();
94 * Sets the {@code Random} instance used by this instance. Useful for
97 public void setRandom(Random random)
103 * Sets the seed of the internal random number generator. May be used to provide repeatable
106 public void setRandomSeed(long seed)
108 random.setSeed(seed);
112 * Sets the number of new 'small-world' connections (outgoing edges) to be added to each vertex.
114 public void setConnectionCount(int num_connections)
116 if (num_connections <= 0)
118 throw new IllegalArgumentException("Number of new connections per vertex must be >= 1");
120 this.num_connections = num_connections;
124 * Returns the number of new 'small-world' connections to be made to each vertex.
126 public int getConnectionCount()
128 return this.num_connections;
132 * Generates a random small world network according to the parameters given
133 * @return a random small world graph
136 public Graph<V,E> create()
138 Graph<V, E> graph = super.create();
140 // TODO: For toroidal graphs, we can make this more clever by pre-creating the WeightedChoice object
141 // and using the output as an offset to the current vertex location.
142 WeightedChoice<V> weighted_choice;
144 // Add long range connections
145 for (int i = 0; i < graph.getVertexCount(); i++)
147 V source = getVertex(i);
150 int row_offset = row < row_count/2 ? -row_count : row_count;
151 int col_offset = col < col_count/2 ? -col_count : col_count;
153 Map<V, Float> vertex_weights = new HashMap<V, Float>();
154 for (int j = 0; j < row_count; j++)
156 for (int k = 0; k < col_count; k++)
158 if (j == row && k == col)
160 int v_dist = Math.abs(j - row);
161 int h_dist = Math.abs(k - col);
164 v_dist = Math.min(v_dist, Math.abs(j - row+row_offset));
165 h_dist = Math.min(h_dist, Math.abs(k - col+col_offset));
167 int distance = v_dist + h_dist;
171 vertex_weights.put(getVertex(j,k), (float)Math.pow(distance, -clustering_exponent));
175 for (int j = 0; j < this.num_connections; j++) {
176 weighted_choice = new WeightedChoice<V>(vertex_weights, random);
177 V target = weighted_choice.nextItem();
178 graph.addEdge(edge_factory.create(), source, target);