Data Structure

Topological Sort Project

Overview

For this project, you will build upon the code you wrote for the Graph Conversion project, project 1. In this project, your program will still convert a graph stored using an adjacency matrix to a graph stored using adjacency lists. Once your program has the adjacency list for each vertex, your program will perform a topological sort of the vertices of the graph. Read pages 359 through 365 in the course textbook to learn about the topological sort algorithm.

Topological sort is only performed on directed graphs. A directed graph is a graph where all edges are directed edges. A directed edge is an ordered pair of vertices (u, v) where vertex v is adjacent to vertex u which means we can travel from vertex u to vertex v. But, we would only be able to travel from vertex v to vertex u if there is a directed edge from vertex v to vertex u represented by the ordered pair (v, u). Figure 1 is an example of a directed graph with the arrows, also called arcs, representing the directed edges connecting vertices. For example, vertex A is adjacent to vertex E. A vertex can be adjacent to itself if there is an edge which starts and ends at that same vertex. Figure 2 is the adjacency matrix for the directed graph in figure 1.

A E

B D

C

Figure 1.

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

Figure 2.

( P a g e 1 o f 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 and D. Once your program produces the adjacency list for each and every vertex, it will perform a topological sort of the vertices of the graph printing the vertices in topological order.

Design

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

use to open the file:

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

Assuming you are using Eclipse to create your project, you’ll store the input file project3.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. It is implied that vertex names can be 1 or more characters consisting of letters, digits, and punctuation. 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 corresponds 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, project3.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 is 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 Project3 and it should only contain only one method:

public static void main(String args[]).

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

3. Modify the Vertex class to store the adjacency list of the vertex as well as its name. The only methods you’ll

add to the Vertex class are the get and set methods for the vertex adjacency list data member.

4. Your program will probably create and use a class to implement the topological sort algorithm.

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, print the adjacency list for each vertex, perform a topological sort of the vertices of the graph, and finally print the vertices of the graph in topological order.

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.

Grading Criteria

The total project is worth 20 points, broken down as follows:

4 points: Program compiles without any errors.

4 points: Following good coding standards, good comments, concise main program, no significant code duplication (i.e., good method design), and following directions as specified in this assignment. Putting all or most of the code in the main method will cause you to lose points. You must write methods and classes.

4 points: Checking error conditions such as basic input exception handling, unknown input, and anything else you can anticipate.

4 points: Ability to read the graph from the input file and create it properly.

4 points: Correct result for the graph conversion and topological sort