Data Structure

Graph Conversion Project

Overview

For this project you will write a program which converts a graph stored using an adjacency matrix to a graph stored using adjacency lists. A graph is a set of vertices and a set of edges. Figure 1 is an example of a graph with the circles representing the vertices and the lines connecting vertices representing the edges. Two vertices are adjacent to each other if there is an edge connecting the two vertices. For example, vertices A and E in the graph of figure 1 are adjacent. A vertex can be adjacent to itself if there is an edge which starts and ends at that same vertex.

A E

B D

C

Figure 1.

An adjacency matrix is one method of representing the edges of a graph in a computer program. The number of columns in the adjacency matrix is equal to the number of rows in the adjacency matrix. Each row in the adjacency matrix corresponds to a unique vertex in the graph. Each column in the adjacency matrix also corresponds to a unique vertex in the graph.

Each element in the adjacency matrix has a value of 0 or 1. A value of 0 for the element means there is no edge between the vertex that represents the element’s row and the vertex that represents the element’s column. A value of 1 for the element means there is an edge between the vertex that represents the element’s row and the vertex that represents the element’s column. The vertices for the graph in figure 1 are: A, B, C, D, and E. Figure 2 is the adjacency matrix for the graph in figure 1.

	A	B	C	D	E
A	0	1	0	1	1
B	1	0	1	0	0
C	0	1	0	1	0
D	1	0	1	0	0
E	1	0	0	0	0

Figure 2.

4

Your program will read in the name of each vertex of the graph. Then, your program will read in the graph’s adjacency matrix. Using the graph’s list of vertices and the graph’s adjacency matrix, your program will create the graph’s adjacency lists. Each vertex in the graph has an adjacency list. The adjacency list for a vertex is a

list of all the vertices adjacent to the adjacency list’s vertex. For example, the adjacency list for vertex A of the graph in figure 1 is: B, D, and E.

Creating the adjacency list for a vertex is a simple process. Examine every element in the row for the vertex in the adjacency matrix. If the element’s value is 0, do nothing and move onto the next element. If the element’s value is 1, add the vertex for that element’s column to the adjacency list. For example, creating the adjacency list for vertex A in the graph of figure 1 using the elements in the row for vertex A in the adjacency matrix. The elements in the columns for vertex B, D, and E have a value of 1. Therefore, only B, D, and E are added to the adjacency list for vertex A.

Design

1. The input to your program will be read from a plain text file called project1.txt. This is the statement you’ll

use to open the file:

FileInputStream fstream = new FileInputStream("project1.txt");

Assuming you are using Eclipse to create your project, you’ll store the input file project1.txt in the parent directory of your source code, .java files, which happens to be the main directory of your project in Eclipse. If you’re using some other development environment, you’ll have to figure out where to store the input file.

The first line in the input file contains the names of the vertices of the graph with each name separated by 1 or more spaces. Starting on the second line of the input file is the adjacency matrix for the graph, the second line in the input file is the first row of the adjacency matrix, the third line in the input file is the second row of the adjacency matrix, and so forth. The order of the vertex names in the first line of the input file correspond to the rows and columns in the adjacency matrix. The first vertex name corresponds to the first row and first column in the adjacency matrix, the second vertex name corresponds to the second row and second column in the adjacency matrix, and so forth. Each value (0 or 1) on a line is separated by 1 or more spaces.

Here is a sample input file, project1.txt, which would be the input file for the graph in figure 1. You should create your own example graphs and their input file to properly test your program. Your program should make sure the input does not properly formatted. If the input is not properly formatted, you could properly terminate the program and let the user know about the input error.

2. Make the name of the driver class Project1 and it should only contain only one method:

public static void main(String args[]).

The main method will open the file project1.txt and hand off the input to another class or classes to perform the graph conversion process. Therefore, the main method itself should be fairly short.

3. Write a class called Vertex which stores the name of a vertex in the graph. The only methods of the Job class are the get and set methods for the vertex name, the toString method, and the constructor for the class.

4. Download the file DoublyLinkedList.java containing most of the implementation of the doubly linked list class. You cannot add data members to or modify the data members of the doubly linked list class. You cannot modify the nested private class Node of the doubly linked list class. You cannot modify the nested private class LinkedListIterator of the doubly linked list class. You cannot modify the doubly linked list class constructor and the clear, size, isEmpty, add(AnyType newValue), remove(int index), iterator, and getNode(int index) methods.

You will write the code for the getNode(int index, int lower, int upper) method. This method returns the pointer to the node whose position in the list correspond to the value of the parameter index. This method should ensure index is a value which is greater than or equal to the parameter lower and less than or equal to the parameter upper. If needed, you can write additional methods to help in your implementation of this getNode method but they must be defined as private.

You will write the code for the add(int index, AnyType newValue), remove(Node<AnyType> currNode), get, and set methods. Each of these methods will use one of the getNode methods. Recall for the add method, the index can be a value from 0 to size(). If needed, you can write additional methods to help in your implementation of each of these methods but they must be defined as private.

5. Your program will read in the graph from the input file, convert the adjacency matrix into the adjacency lists, one adjacency list (a doubly linked list of vertices) for each vertex, and finally print the adjacency list for each vertex.

6. Do NOT use your own packages in your program. Do NOT use any graphical user interface code in your program.

7. Make your program as modular as possible, not placing all your code in one .java file. You can create as many classes as you need in addition to the classes described above. Methods should be reasonably small following the guidance that "A function should do one thing, and do it well."

8. Document and comment your code thoroughly.