GraphRandomizer.java

package edu.hawaii.ics.yucheng;

import java.util.ArrayList;
import java.util.Collection;

/**
 * A class that generates random graphs.
 */
class GraphRandomizer {

    /**
     * Builds a random number of subtrees into the graph recursively. This method
     * works on subtrees at a depth of one or greater in the tree.
     * 
     * @param indices The vertex indices.
     * 
     * @param root The root index of the tree.
     * 
     * @param end The end index (not assigned in this method)
     * 
     * @param edges The collection of edges.
     */
    private static void buildDeepSubtrees(final int[] indices, final int root,
        final int end, final Collection<Edge> edges) {

        // The next vertex is always a child if there are any children.
        int child = root + 1;

        // Loop until all children or ancestors are connected.
        while (child < end) {

            // Connect this child vertex.
            edges.add(new Edge(indices[root], indices[child]));

            // Determine the next child.
            final int nextChild = random(child + 1, end);

            // Recursively build deeper trees for the ancestors, if any.
            buildDeepSubtrees(indices, child, nextChild, edges);

            // Loop until all children or ancestors are connected.
            child = nextChild;
        }
    }


    /**
     * Builds a random number of loops into the graph.
     * 
     * @param edges The collection of edges.
     * 
     * @param numVertices The number of vertices.
     */
    @SuppressWarnings("boxing")
    private static void buildLoops(final Collection<Edge> edges,
        final int numVertices) {

        // Use a matrix to keep track of the connections.
        final Matrix<Boolean> matrix = new Matrix<Boolean>(numVertices,
            numVertices, false);

        // Initialize the matrix of connections.
        for (final Edge e : edges) {
            matrix.set(e.first(), e.second(), true);
            matrix.set(e.second(), e.first(), true);
        }

        // Loop over each possible edge, and connect the edge to form a loop
        // arbitrarily 25% of the time.
        for (int i = 0; i < numVertices; i++)
            for (int j = i + 1; j < numVertices; j++)
                if (!matrix.get(i, j))
                    if (random(0, 4) == 0) {
                        matrix.set(i, j, true);
                        matrix.set(j, i, true);
                        edges.add(new Edge(i, j));
                    }
    }


    /**
     * Builds a random number of subtrees into the graph.
     * 
     * @param indices The vertex indices.
     * 
     * @return The collection of edges.
     */
    private static Collection<Edge> buildSubtrees(final int[] indices) {

        // Create a new collection of edges that will be built and returned.
        final Collection<Edge> edges = new ArrayList<Edge>();

        // Loop over each vertex at depth 0.
        int from = 0;
        while (from + 1 < indices.length) {

            // Select a random number of children for its tree.
            final int to = random(from + 1, indices.length + 1);

            // Connect this root vertex to the next root vertex if there is one.
            if (to < indices.length)
                edges.add(new Edge(indices[from], indices[to]));

            // Recursively build deeper subtrees.
            buildDeepSubtrees(indices, from, to, edges);

            // Loop until all vertices are connected.
            from = to;
        }

        // Return the collection of edges created above.
        return edges;
    }


    /**
     * Creates a random, valid graph with a number of vertices between min and
     * (max - 1).
     * 
     * @param min The minimum number of vertices (inclusive).
     * 
     * @param max The maximum number of vertices (exclusive).
     * 
     * @return A new graph.
     */
    public static Graph create(final int min, final int max) {
        if (min <= 0)
            throw new IllegalArgumentException("min");
        if (max <= min)
            throw new IllegalArgumentException("max");

        // Randomly create a number of vertices, weighted between 0..99.
        final float[] vertices = new float[random(min, max)];
        for (int i = 0; i < vertices.length; i++)
            vertices[i] = random(0, 100);

        // Create an random array of edges that will connect each vertex.
        final int[] indices = new int[vertices.length];
        for (int i = 0; i < indices.length; i++)
            indices[i] = i;
        for (int i = 0; i < indices.length; i++)
            swap(indices, i, random(0, indices.length));

        // Create subtrees for some of the vertices.
        final Collection<Edge> edges = buildSubtrees(indices);

        // Create a series of random loops.
        buildLoops(edges, vertices.length);

        // Store the final result.
        return new Graph(vertices, edges);
    }


    /**
     * Returns a random number between low and high.
     * 
     * @param low The low value (inclusive).
     * 
     * @param high The high value (exclusive).
     * 
     * @return A pseudo-random number.
     */
    private static int random(final int low, final int high) {
        return (int) (Math.random() * (high - low) + low);
    }


    /**
     * Swaps two values in an array.
     * 
     * @param array The array.
     * 
     * @param a The first index.
     * 
     * @param b The second index.
     */
    private static void swap(final int[] array, final int a, final int b) {
        final int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}