edu.hawaii.ics.yucheng
Class GraphRandomizer

java.lang.Object
  edu.hawaii.ics.yucheng.GraphRandomizer

 class GraphRandomizer
extends java.lang.Object

A class that generates random graphs.

Constructor Summary

GraphRandomizer()

Method Summary

private static void	buildDeepSubtrees(int[] indices, int root, int end, java.util.Collection<Edge> edges) Builds a random number of subtrees into the graph recursively.
private static void	buildLoops(java.util.Collection<Edge> edges, int numVertices) Builds a random number of loops into the graph.
private static java.util.Collection<Edge>	buildSubtrees(int[] indices) Builds a random number of subtrees into the graph.
static Graph	create(int min, int max) Creates a random, valid graph with a number of vertices between min and (max - 1).
private static int	random(int low, int high) Returns a random number between low and high.
private static void	swap(int[] array, int a, int b) Swaps two values in an array.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

GraphRandomizer

GraphRandomizer()

Method Detail

buildDeepSubtrees

private static void buildDeepSubtrees(int[] indices,
                                      int root,
                                      int end,
                                      java.util.Collection<Edge> edges)

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.

Parameters:

indices - The vertex indices.

root - The root index of the tree.

end - The end index (not assigned in this method)

edges - The collection of edges.

buildLoops

private static void buildLoops(java.util.Collection<Edge> edges,
                               int numVertices)

Builds a random number of loops into the graph.

Parameters:

edges - The collection of edges.

numVertices - The number of vertices.

buildSubtrees

private static java.util.Collection<Edge> buildSubtrees(int[] indices)

Builds a random number of subtrees into the graph.

Parameters:

indices - The vertex indices.

Returns:

The collection of edges.

create

public static Graph create(int min,
                           int max)

Creates a random, valid graph with a number of vertices between min and (max - 1).

Parameters:

min - The minimum number of vertices (inclusive).

max - The maximum number of vertices (exclusive).

Returns:

A new graph.

random

private static int random(int low,
                          int high)

Returns a random number between low and high.

Parameters:

low - The low value (inclusive).

high - The high value (exclusive).

Returns:

A pseudo-random number.

swap

private static void swap(int[] array,
                         int a,
                         int b)

Swaps two values in an array.

Parameters:

array - The array.

a - The first index.

b - The second index.