This is an individual programming assignment.
For this problem, you’ll implement random graphs. Random graphs were developed by mathematicians Paul Erdős and Alfred Rényi in 1959 and have some interesting properties. One of these properties is a kind of emergent behavior, complex behavior that arises from simple rules. Stuart A. Kauffman describes this in non-technical terms in his book Reinventing the Sacred (p. 61–62); I’ve added notes interjecting the terms we used in class:
The mathematicians Paul Erdős and Alfred Rényi in 1959 developed the theory of random graphs. In the sense they used it, “graph” denotes a set of points [vertices] with either a set of lines or a set of arrows [edges]. When the points are connected by lines it is called an undirected graph; with arrows it is a directed graph. Erdős and Rényi then ask us to imagine the following experiment. Place ten thousand buttons (our version of points) on the floor. Take a spool of red thread. Break off a piece and choose two buttons at random, then tie them together. Now repeat this process, tying more and more randomly chosen pairs of buttons together. Define a “cluster” [connected component] as a set of buttons that are directly or indirectly connected. The size of the cluster is just the number of buttons it contains. Imagine picking up a button, and ask how many other buttons you pick up with it.
This is an undirected graph since the threads have no arrow heads. Erdős and Rényi asked how the size of the largest cluster in the graph changes as more and more buttons are randomly interconnected in this graph. The results are deeply surprising. Initially, most buttons are isolated, with a few pairs of connected buttons. As more buttons are connected little clusters of connected buttons form. Then midsized clusters form. But then something magical occurs. Given enough midsized clusters, adding just a few new connections will connect most or all the midsized clusters into a single giant cluster, called the giant component [largest connected component]of the graph. This sudden jump in the size of the largest cluster is, in fact, a “phase transition,” much like the phase transition between water and ice. Adding more connections gradually brings the remaining small clusters and isolated buttons to the giant connected component of the graph.
In short, among a set of buttons connected at random by ever more threads, the size of the largest cluster quite suddenly jumps to the point where most buttons are included in it. This phase transition is emergent … and depends upon mathematics, not physics. …
An interesting point is that the details depend upon the total number of buttons. As the number increases, the phase transition becomes sharper and the size of the giant component becomes a nearly constant fraction of the total number of buttons
The four charts below plot the size of the largest connected component vs. the number of edges added to the graph. The charts show experiments with 100, 200, 400, and 800 nodes in the graph. Notice how the phase transition becomes sharper as we experiment with larger graphs.
You job is to complete the implementation of the
RandomGraph
class that you’ll find in the
RandomGraphs
project in your individual SVN repository.
Your first task is to decide on a representation for random graphs that will allow you to efficiently implement the required constructor and methods. The
RandomGraph
constructor that you must implement has the signature
public RandomGraph(int size, int[][] edges)
where each element of
edges
is a pair giving an edge for the graph. For example, the constructor call
new RandomGraph(6, new int[][]{{0,5}, {5,3}, {5,2}, {2,1}, {2,4}})
would create the graph shown in this figure:
The
RandomGraph
methods that you must implement are:
public int largestConnectedComponentSize()
public void addRandomEdge() throws IllegalStateException
public boolean isConnected()
public boolean isComplete()
public String toString()
Specifications for these methods are provided by the javadoc comments in
RandomGraph.
Your biggest challenge is likely to be coming up with a representation that lets you efficiently calculate the size of the largest connected component, while also efficiently adding a new random edge. The latter is particularlly interesting since you aren’t allowed to add an edge that already exists in the graph.
You may add fields, helper methods, and inner classes to
RandomGraph. You may also add additional classes if that helps you solve the problem.
You’ll probably find the
java.util.Collections.shuffle()
method to be helpful!
For experimenting with your graphs, the provided
Experiment
class has two sorts of test code. The static method
runPrintingExperiment()
creates a small graph, adds some random edges to it, and prints it out (using
toString()). The static method
runChartingExperiment()
uses your
RandomGraph
implementation to generate a chart like those shown in the figures above.
RandomGraphTest
provides JUnit tests. The unit tests include “time out” values that limit the amount of time that may be spent on a test. These time limits should be more than long enough for an efficient implementation. If you are failing a test because of the time limits, you should not change the limits. Instead, think about where your code is spending the most time. Can you change the way that you are representing your
RandomGraph
to avoid spending so much time? Be sure to get help if you’re stuck. The representation issues for this problem are intended to be a warm up for the Sliding Blocks exercise coming later. I want you to get enough help to do well on this assignment so you’re ready for the later one.
You do
not
have to write any graphics code; that is all provided. You should not change the provided
Experiment,
RandomGraphTest, or
ChartComponent
classes. Running the JUnit tests should not cause any graphics to be displayed.
This assignment is worth 100 points. This is the first time I’ve given this assignment, so I may need to make adjustments to the grading, but currently I’m planning to grade based on the following criteria:
Submit your code by committing it to your Subversion repository.