CPSC 327, Spring 2018
Homework 7: Graph Programs

This homework is a programming assignment. It will count for more points than previous assignments. It is due on Friday, March 30. (There might be an additional written homework assignment due at that time or soon after.) We will discuss in class whether a version of this assignment can be a group project.

You will write several programs that implement graph algorithms. To represent graphs in the program, you are required to use the Graph class defined in Graph.java. You can find a copy in /classes/cs327. You should read the Java file carefully to learn the API for the class. You probably also want a copy of weighted-graph.txt, which contains data for a small, 16-vertex weighted undirected graph. You can use it as a test for Kruskal's or Prim's algorithm.

To submit your work, make a directory named hw7 inside your homework folder in /classes/cs327/homework, and copy your programs into that folder. I will print all Java files in that directory, except for Graph.java and TextIO.java.

Connected Components in Random Graphs

What happens when you create a random undirected graph by adding random edges to it? In particular, how likely is it that the vertices will be all, or mostly, connected? The number of edges that you need to get an almost connected, or even a fully connected, graph is probably smaller than you might guess. Here is a function that creates a random graph, using a seeded random number generator so that the result will be reproducible:

    /**
     * Creates a random undirected graph with specified numbers of vertices
     * and edges, using a pseudo-random number generator initialized with a
     * given seed.
     */
    private static Graph randomGraph( int vertexCt, int edgeCt, int seed ) {
        Random rand = new Random(seed);
        Graph grph;
        grph = new Graph(vertexCt);
        while (grph.getEdgeCount() < edgeCt) {
            int a = rand.nextInt(vertexCt);
            int b = rand.nextInt(vertexCt);
            if ( ! grph.edgeExists(a, b) ) {
                grph.addEdge(a, b);
            }
        }
        return grph;
    }

You will want to open this page in a web browser so you can copy-and-paste this method into your program.

Write a Java method for finding the size of the largest connected component in an undirected graph. To do this, you will have to find all connected components. You can try your method on the graph generated by randomGraph(100,100,1). The answer should be 84. Your method should also word for a fairly large graph, such as the one generated by randomGraph(250000,300000,1). You should write a program that runs your method for these two graphs and prints the results.

Now, you should write another program to investigate this question: For a random graph of some given size, N, how does the size of the maximum connected component depend on the number of edges in the graph? There are two aspects to this question: First, you should look at how the size of the largest connected component varies as the number of edges increases from about (1/10)*N to about 2*N. Second, you should try to say how many edges have to be added in order to be almost certain that all of the vertices are contained in a single connected component whose size is equal to the total number of vertices in the graph. The answer will be somewhat more than 2*N. Use a fairly large graph, such as 1000 or 10000 vertices, or try it for several different numbers of vertices.

You should design a program (or two programs) that you can use to investigate these questions. You should report the findings of your investigation in a long comment in the program. You should not simply write a program, run it once, and report the result! I want to know what interesting things you discover about the behavior of random graphs, and what evidence you have.

Minimal Spanning Tree

For the second part of the assignment, you should write a program that can find a Minimal Spanning tree using either Prim's algorithm with a priority queue or Kruskal's algorithm with union-find. You should apply your algorithm to at least three graphs, as discussed here. (To get good speedup for Prim's algorithm, you need a carefully designed priority queue. We will discuss this in class when I hand out this assignment.)

The first graph is to be read from the file weighted-graph.txt. This file defines a connected, weighted, undirected graph. The format of the file is as follows: The first line of the file contains two integers giving the number of vertices and the number of edges in the graph. After that, there is one line for each edge, containing the vertex numbers of the two endpoints of the edge and the weight of the edge. The vertex numbers are integers, but the weight can be real number. Your method for reading a graph from a file should be able to read any file in a similar format. (The MST for this graph has weight 45.)

The second graph is a random graph generated by calling randomWeightedGraph(100,300,10,1) where randomWeightedGraph is the following method:

    static Graph randomWeightedGraph(int v, int e, int maxWeight, long seed) {
        Random rand = new Random(seed);
        Graph g = new Graph(v);
        while (g.getEdgeCount() < e) {
            int x = rand.nextInt(v);
            int y = rand.nextInt(v);
            if (x == y || g.edgeExists(x, y))
                continue;
            g.addEdge(x, y, 1 + rand.nextInt(maxWeight));
        }
        return g;
    }

This second graph has a MST with weight 264.

Finally, you should try your method on the random graph generaged by calling randomWeightedGraph(300000,5000000,1000,2). It took my computer about 7 seconds to generate this graph and less than one second to find an MST using Prim's algorithm. At the time I'm writing this, I haven't finished my implementation of Kruskal's algorithm; when I do, I'll let you know how long it takes.