third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/KleinbergSmallWorldGenerator.java

   1
   2 package edu.uci.ics.jung.algorithms.generators.random;
   3
   4 /*
   5 * Copyright (c) 2009, the JUNG Project and the Regents of the University
   6 * of California
   7 * All rights reserved.
   8 *
   9 * This software is open-source under the BSD license; see either
  10 * "license.txt" or
  11 * http://jung.sourceforge.net/license.txt for a description.
  12 */
  13
  14 import java.util.HashMap;
  15 import java.util.Map;
  16 import java.util.Random;
  17
  18 import org.apache.commons.collections15.Factory;
  19
  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;
  23
  24 /**
  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.
  31  *
  32  * @see "Navigation in a small world J. Kleinberg, Nature 406(2000), 845."
  33  * @author Joshua O'Madadhain
  34  */
  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;
  39
  40     /**
  41      * Creates
  42      * @param graph_factory
  43      * @param vertex_factory
  44      * @param edge_factory
  45      * @param latticeSize
  46      * @param clusteringExponent
  47      */
  48     public KleinbergSmallWorldGenerator(Factory<? extends Graph<V,E>> graph_factory, Factory<V> vertex_factory,
  49             Factory<E> edge_factory, int latticeSize, double clusteringExponent)
  50     {
  51         this(graph_factory, vertex_factory, edge_factory, latticeSize, latticeSize, clusteringExponent);
  52     }
  53
  54     /**
  55      * @param graph_factory
  56      * @param vertex_factory
  57      * @param edge_factory
  58      * @param row_count
  59      * @param col_count
  60      * @param clusteringExponent
  61      */
  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)
  64     {
  65         super(graph_factory, vertex_factory, edge_factory, row_count, col_count, true);
  66         clustering_exponent = clusteringExponent;
  67         initialize();
  68     }
  69
  70     /**
  71      * @param graph_factory
  72      * @param vertex_factory
  73      * @param edge_factory
  74      * @param row_count
  75      * @param col_count
  76      * @param clusteringExponent
  77      * @param isToroidal
  78      */
  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,
  81             boolean isToroidal)
  82     {
  83         super(graph_factory, vertex_factory, edge_factory, row_count, col_count, isToroidal);
  84         clustering_exponent = clusteringExponent;
  85         initialize();
  86     }
  87
  88     private void initialize()
  89     {
  90         this.random = new Random();
  91     }
  92
  93     /**
  94      * Sets the {@code Random} instance used by this instance.  Useful for
  95      * unit testing.
  96      */
  97     public void setRandom(Random random)
  98     {
  99         this.random = random;
 100     }
 101
 102     /**
 103      * Sets the seed of the internal random number generator.  May be used to provide repeatable
 104      * experiments.
 105      */
 106     public void setRandomSeed(long seed)
 107     {
 108         random.setSeed(seed);
 109     }
 110
 111     /**
 112      * Sets the number of new 'small-world' connections (outgoing edges) to be added to each vertex.
 113      */
 114     public void setConnectionCount(int num_connections)
 115     {
 116         if (num_connections <= 0)
 117         {
 118             throw new IllegalArgumentException("Number of new connections per vertex must be >= 1");
 119         }
 120         this.num_connections = num_connections;
 121     }
 122
 123     /**
 124      * Returns the number of new 'small-world' connections to be made to each vertex.
 125      */
 126     public int getConnectionCount()
 127     {
 128         return this.num_connections;
 129     }
 130
 131     /**
 132      * Generates a random small world network according to the parameters given
 133      * @return a random small world graph
 134      */
 135     @Override
 136     public Graph<V,E> create()
 137     {
 138         Graph<V, E> graph = super.create();
 139
 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;
 143
 144         // Add long range connections
 145         for (int i = 0; i < graph.getVertexCount(); i++)
 146         {
 147             V source = getVertex(i);
 148             int row = getRow(i);
 149             int col = getCol(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;
 152
 153             Map<V, Float> vertex_weights = new HashMap<V, Float>();
 154             for (int j = 0; j < row_count; j++)
 155             {
 156                 for (int k = 0; k < col_count; k++)
 157                 {
 158                     if (j == row && k == col)
 159                         continue;
 160                     int v_dist = Math.abs(j - row);
 161                     int h_dist = Math.abs(k - col);
 162                     if (is_toroidal)
 163                     {
 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));
 166                     }
 167                     int distance = v_dist + h_dist;
 168                     if (distance < 2)
 169                         continue;
 170                     else
 171                         vertex_weights.put(getVertex(j,k), (float)Math.pow(distance, -clustering_exponent));
 172                 }
 173             }
 174
 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);
 179             }
 180         }
 181
 182         return graph;
 183     }
 184 }