Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSCI 2110

DATA STRUCTURES AND ALGORITHMS

ASSIGNMENT NO.6

This is an optional assignment.

You may do this assignment if

A. You have missed one of the previous five assignments. OR

B. You have scored less on one of the previous assignments and would like to improve your overall average on the assignments.

OR

C. You have time and want to just attempt the assignment for fun and learning. In any case, the best 5 out of 6 assignments will be taken for grading purposes.

In the lectures, we discussed Topological Sorting as one of the Graph Algorithms. In this assignment, you will implement this algorithm.

Write a Java program that does the following:

a) Reads an input text file like the one described below. The text file contains the description of a directed, unweighted, acyclic graph.

b) Construct an adjacency matrix representing the graph.

c) Perform topological sorting

d) Display the result of the sort. Here’s the description in detail:

The input file will contain a number of lines. The first line will be an integer representing the number of vertices in a directed, unweighted graph. You can also assume that the graph is acyclic (this is a requirement for topological sorting). Each following line will contain a pair of uppercase characters (A-Z) separated by tabs. These pairs represent a graph’s edges.

After reading data from the input file, your program should create an adjacency matrix representing a graph. Declare a square, 2D array to act as an adjacency matrix. You may find the following code line useful:            int[][] adj = new int[n][n];

The sample input file results in a 5x5 matrix like this:

A B C D E

A 0 1 0 1 0

B 0 0 0 1 0

C 0 0 0 0 0

D 0 0 1 0 0

E 1 1 0 0 0

Both Strings and characters can be easily converted to integers in Java. A captured String can be converted to an integer using Integer.parseInt(string), while the capitals from the input file can be converted to indices via a simple arithmetic expression: character-65. You may find the following code snippet useful when building your adjacency matrix:

int v0 = input.next().charAt(0)-65;

int v1 = input.nextLine().charAt(0)-65;

adj[v0][v1] = adj[v1][v0] = 1;

Next, implement the Topological Sorting algorithm as follows:

Initialize an empty queue.

for each vertex v in the graph

compute the predecessor count, pred(v) (this is just the indegree of the vertex) for each vertex v in the graph

if (pred(v)==0) add v to the queue.

topnum ß1

while queue is not empty {

w ßdequeue

assign w with topnum

topnum ß topnum+1

for each neighbour p of w{

pred(p) ß pred(p) -1

if (pred(p)==0) then

add p to queue

}//end for

}//end while

All the vertices with be assigned with topnum in the topological sorting order.

Display the result. This will just be the listing of the vertices with increasing values of topnum. For the above example, one solution would be:

topnum:                    1    2     3    4     5

E     A    B    D    C

What to submit:

A zip file containing the following:

a) Source code (.java file or .java files if you have created multiple classes), appropriately commented. DO NOT SUBMIT .class files.

b) Sample input text file.

c) Sample output