Math 171 Spring 2005, Lab 17 (double lab)

Due Thursday, April 21, 11:59 P.M.

1. Overview
2. Assignment
3. Hints

Overview

The purpose of this lab is to give you additional practice with dynamic data types in Fortran.

Top

Assignment

Write a program called numcomp that reads in a graph from a file, determines the number of connected components, and writes this information out to the screen. The graph file should be formatted as follows:

• Every line in the file is blank or contains a single integer.
• The first integer specifies the number of vertices in the graph.
• The remainder of the file consists of blocks of integers, each of which specifies a single vertex in the graph. The integers in each block are ordered as follows:
  1. The vertex number, which should be between 1 and the number of vertices in the graph.
  2. The number of neighbors of this vertex, which may be any nonnegative integer.
  3. The vertex numbers for each of the neighbors.
• The number of blocks equals the number of vertices in the graph.

Here are some example graph files:

• The complete graph on three vertices (i.e. a triangle)
• The complete graph on five vertices
• A graph consisting of two triangles sharing only a single vertex
• A complete graph on four vertices plus a vertex with no neighbors
• Two disconneected triangles

You will want to make sure your code detects only the last two as being disconnected.

Top

Hints

1. First, decide how you want to organize your data. You will need to define a data type for the vertices, which contains a neighbor count, a pointer to an array of indices for its neighbors, and a flag. You will also want to declare a type for the graph which contains the vertex count and a pointer to an array of all the vertices. The reason for using pointers here is that it allows you to use exactly the amount of memory needed to represent the graph.
2. Now define the interface to the functions that will read in the graph and determine whether it is connected. You should have a function read_graph(filename) that takes a character string as its argument and returns the graph contained in the file specified by the name given in the string. You should also define a function is_connected(g) that returns a logical variable corresponding to whether or not the graph g is connected. At this point, your functions should just be empty stubs that return useless values. Have read_graph always return an empty graph with a vertex count of zero, and have is_connected always return false.
3. Now write a test driver program that prompts for a filename, calls read_graph on this file, and writes out an appropriate message depending on the return value of is_connected. Since the test driver is the simplest part of this program, you should be able to verify that it is correct by reading through your code carefully. Make sure the driver is free of errors, since you will be using it to test the rest of your program. Now make sure your code compiles and runs as expected before continuing.
4. Now go back and finish writing your read_graph function. If the specifed file cannot be opened, you will need to either abort or return a graph formatted in such a way that the caller will be able to detect the error and abort (e.g. return a graph with a vertex count of -1). Now read in the number of vertices, and allocate an array containing this many vertices. Next, write a nested DO loop that reads in the vertex blocks. The outer loop should read in the vertex number and the neighbor count, and allocate an array of integers for the neighbors. The inner loop should just read the neighbor indices into this array. Finally, go back and do some error checking on the numbers that were specifed. Make sure your code only allocates an array if the corresponding size is a positive integer, and flag an error if any of the values lie outside the acceptable range. You will need to add tests for the vertex numbers and neighbor count. To avoid memory leaks, make sure that you deallocate the vertex array if returning an error code after the array has been allocated. Although there are several other possible errors in the input file (e.g. a vertex number 3 is specifed multiple times, or not all vertices are specified), you do not need to worry about checking for any of these.
5. At this point, you may want to write a subroutine that writes out a graph. Even though this is not required to fulfill the stated purpose of the program, writing out the graph will make it much easier to test the function you have just written before continuing to the next step. Since the write_graph subroutine should be relatively easy to implement, it is worth the extra effort to ensure your code's correctness. If at any point your start getting segfaults, try compiling your code with the -g option and using idb to find the problem as discussed in class.
6. Now finish writing the is_connected function. You will need to write an additional recursive subroutine rec_is_connected(g,n) that performs depth-first-search on the graph starting at vertex number n and sets the flag to true in each vertex it visits. The is_connected function should initialize all the flags in your vertices to false, perform a depth-first-search on any vertex in the graph, and then test whether all the flags are set to true. If any of the flags are false, the graph is disconnected. Make sure you handle the case for an empty graph correctly.
7. Finally, test your code on the graph files I provided, and make sure it returns the expected results. You may also want to write some additional files of your own to test with.

Top

Back to the course information page