COSC 2P03 – Advanced Data Structures
Fall 2016
Assignment #4
Due Date: December 5th, noon Late Date: December 8th, noon
This assignment accounts for 6% of your final grade and is worth a total of 60 marks
The goal of this assignment is to practice working with directed graphs.
You are to write a program to perform a modified topological sort on a directed graph. A topological sort of a directed graph G is an ordering v1, …, vn of the vertices of G such that for every pair of vertices vi and vj, if there is a path from vi to vj then i < j. This implies that G has no directed cycles.
Suppose that we modify this problem to handle cycles in the following way: if vertices are part of the same directed cycle then they can all be taken at the same time. However, vertices should only be taken at the same time if necessary. Given this modification, we might consider the ordering as being an ordering between sets.
As an example, consider the problem of finding a sequence of courses such that whenever a course is taken, all of its prerequisites are satisfied: our modification allows for corequisites, i.e. courses that must be taken concurrently.
Example:
Consider the graph represented by the following adjacency matrix:
101 / 102 / 120 / 125 / 130 / 230101 / 0 / 1 / 1 / 0 / 0 / 0
102 / 1 / 0 / 0 / 1 / 0 / 0
120 / 0 / 0 / 0 / 1 / 0 / 0
125 / 0 / 0 / 0 / 0 / 1 / 0
130 / 0 / 0 / 1 / 0 / 0 / 1
230 / 0 / 0 / 0 / 0 / 0 / 0
This graph contains two directed cycles.
A valid topological ordering would be as follows:
{101, 102}, {120, 125, 130}, {230}
This indicates that first 101 and 102 should be taken concurrently, followed by 120, 125 and 130 all concurrently, and then finally 230. Note that any permutation of the values within each set is also a valid solution; consider, for example, {102, 101}, {120, 125, 130}, {230}.
Input: Your program should read from a file; this file has the following format:
An integer value n, indicating that we have a graph with n vertices.
A list of n integers representing vertex labels
A nxn binary array representing the adjacency matrix of the graph in row-major order.
Output:
· A modified topological sort of the graph, written in the format used in the example above:
§ each set of vertices taken at the same time are enclosed within curly brackets {} and separated by commas within those brackets, and
§ each of the sets should also be separated by commas.
Hint: Ensure that your program is able to handle the situation in which the same vertex is part of more than 1 directed cycle.
Notes:
1. For submission purposes, you must hand in the output obtained by running your program using the input file assn4in.txt found on the course website.
2. Your program will be tested using other input files; therefore you must make sure that your program is thoroughly tested. For testing purposes you may assume that n ≤ 12. You are advised not to use too large a value of n in your testing, as otherwise detection of cycles can be very time-consuming.
3. In general there may be several valid solutions. You are only expected to produce one valid solution.
Submission Requirements:
All of the following must be submitted in an envelope in the COSC 2P03 assignment box:
1. A cover sheet, available from http://www.cosc.brocku.ca/forms/cover, completely filled out. Your assignment will not be marked unless one is submitted with the assignment.
2. A commented and properly documented source code listing for your program.
3. A listing of the output for your program from the supplied input, assn4in.txt.
4. A statement specifying whether you used NetBeans or DrJava (to assist the marker).
You must also submit your assignment electronically so that it can be checked for plagiarism using MOSS. To do this, create a directory on Sandcastle containing all files for this assignment, and run the script submit2p03 from this directory. Your assignment will not be marked unless this is done.