+++ /dev/null
-
-package edu.uci.ics.jung.algorithms.generators.random;
-
-/*
-* Copyright (c) 2009, the JUNG Project and the Regents of the University
-* of California
-* All rights reserved.
-*
-* This software is open-source under the BSD license; see either
-* "license.txt" or
-* http://jung.sourceforge.net/license.txt for a description.
-*/
-
-import java.util.HashMap;
-import java.util.Map;
-import java.util.Random;
-
-import org.apache.commons.collections15.Factory;
-
-import edu.uci.ics.jung.algorithms.generators.Lattice2DGenerator;
-import edu.uci.ics.jung.algorithms.util.WeightedChoice;
-import edu.uci.ics.jung.graph.Graph;
-
-/**
- * Graph generator that produces a random graph with small world properties.
- * The underlying model is an mxn (optionally toroidal) lattice. Each node u
- * has four local connections, one to each of its neighbors, and
- * in addition 1+ long range connections to some node v where v is chosen randomly according to
- * probability proportional to d^-alpha where d is the lattice distance between u and v and alpha
- * is the clustering exponent.
- *
- * @see "Navigation in a small world J. Kleinberg, Nature 406(2000), 845."
- * @author Joshua O'Madadhain
- */
-public class KleinbergSmallWorldGenerator<V, E> extends Lattice2DGenerator<V, E> {
- private double clustering_exponent;
- private Random random;
- private int num_connections = 1;
-
- /**
- * Creates
- * @param graph_factory
- * @param vertex_factory
- * @param edge_factory
- * @param latticeSize
- * @param clusteringExponent
- */
- public KleinbergSmallWorldGenerator(Factory<? extends Graph<V,E>> graph_factory, Factory<V> vertex_factory,
- Factory<E> edge_factory, int latticeSize, double clusteringExponent)
- {
- this(graph_factory, vertex_factory, edge_factory, latticeSize, latticeSize, clusteringExponent);
- }
-
- /**
- * @param graph_factory
- * @param vertex_factory
- * @param edge_factory
- * @param row_count
- * @param col_count
- * @param clusteringExponent
- */
- public KleinbergSmallWorldGenerator(Factory<? extends Graph<V,E>> graph_factory, Factory<V> vertex_factory,
- Factory<E> edge_factory, int row_count, int col_count, double clusteringExponent)
- {
- super(graph_factory, vertex_factory, edge_factory, row_count, col_count, true);
- clustering_exponent = clusteringExponent;
- initialize();
- }
-
- /**
- * @param graph_factory
- * @param vertex_factory
- * @param edge_factory
- * @param row_count
- * @param col_count
- * @param clusteringExponent
- * @param isToroidal
- */
- public KleinbergSmallWorldGenerator(Factory<? extends Graph<V,E>> graph_factory, Factory<V> vertex_factory,
- Factory<E> edge_factory, int row_count, int col_count, double clusteringExponent,
- boolean isToroidal)
- {
- super(graph_factory, vertex_factory, edge_factory, row_count, col_count, isToroidal);
- clustering_exponent = clusteringExponent;
- initialize();
- }
-
- private void initialize()
- {
- this.random = new Random();
- }
-
- /**
- * Sets the {@code Random} instance used by this instance. Useful for
- * unit testing.
- */
- public void setRandom(Random random)
- {
- this.random = random;
- }
-
- /**
- * Sets the seed of the internal random number generator. May be used to provide repeatable
- * experiments.
- */
- public void setRandomSeed(long seed)
- {
- random.setSeed(seed);
- }
-
- /**
- * Sets the number of new 'small-world' connections (outgoing edges) to be added to each vertex.
- */
- public void setConnectionCount(int num_connections)
- {
- if (num_connections <= 0)
- {
- throw new IllegalArgumentException("Number of new connections per vertex must be >= 1");
- }
- this.num_connections = num_connections;
- }
-
- /**
- * Returns the number of new 'small-world' connections to be made to each vertex.
- */
- public int getConnectionCount()
- {
- return this.num_connections;
- }
-
- /**
- * Generates a random small world network according to the parameters given
- * @return a random small world graph
- */
- @Override
- public Graph<V,E> create()
- {
- Graph<V, E> graph = super.create();
-
- // TODO: For toroidal graphs, we can make this more clever by pre-creating the WeightedChoice object
- // and using the output as an offset to the current vertex location.
- WeightedChoice<V> weighted_choice;
-
- // Add long range connections
- for (int i = 0; i < graph.getVertexCount(); i++)
- {
- V source = getVertex(i);
- int row = getRow(i);
- int col = getCol(i);
- int row_offset = row < row_count/2 ? -row_count : row_count;
- int col_offset = col < col_count/2 ? -col_count : col_count;
-
- Map<V, Float> vertex_weights = new HashMap<V, Float>();
- for (int j = 0; j < row_count; j++)
- {
- for (int k = 0; k < col_count; k++)
- {
- if (j == row && k == col)
- continue;
- int v_dist = Math.abs(j - row);
- int h_dist = Math.abs(k - col);
- if (is_toroidal)
- {
- v_dist = Math.min(v_dist, Math.abs(j - row+row_offset));
- h_dist = Math.min(h_dist, Math.abs(k - col+col_offset));
- }
- int distance = v_dist + h_dist;
- if (distance < 2)
- continue;
- else
- vertex_weights.put(getVertex(j,k), (float)Math.pow(distance, -clustering_exponent));
- }
- }
-
- for (int j = 0; j < this.num_connections; j++) {
- weighted_choice = new WeightedChoice<V>(vertex_weights, random);
- V target = weighted_choice.nextItem();
- graph.addEdge(edge_factory.create(), source, target);
- }
- }
-
- return graph;
- }
-}
Code Review / controller.git / blobdiff