Project 2 - Topological Sorting

Objectives:

Be familiar with digraphs and topological sorting

Description:

The university wants to upgrade part of its registration system. They've asked you to provide them with a list of classes, which if taken one class per semester that a student would meet all of the prerequisites. Instantly you think of using a directed graph class and performing topological sorting. The university will supply prerequisite information in the following formats:

COURSE1	COURSE2

where COURSE1 is a prerequisite to COURSE2 and

NONE	COURSE3

where COURSE3 has no prerequisites . They have provided an example file based on the prerequisites for Exercise Science:
Example 1 (project2A.tab):

BIOL_2010	BIOL_2020
BIOL_2010	EXSC_3830
EXSC_3830	EXSC_4000
EXSC_3830	EXSC_4230
EXSC_3830	EXSC_4240
EXSC_4000	EXSC_4010
EXSC_4240	EXSC_4260

Here are some other examples:
Example 2 (project2B.tab):

ABCD_1000	ABCD_2000
ABCD_1000	ABCD_3000
ABCD_1500	ABCD_2000
ABCD_2000	ABCD_3000
ABCD_2000	ABCD_3500

Example 3 (project2C.tab):

ABCD_1000	ABCD_2000
ABCD_1000	ABCD_3000
ABCD_1500	ABCD_2000
ABCD_2000	ABCD_3000
ABCD_2000	ABCD_3500
NONE	ABCD_4000

Example 4 (project2E.tab):

ABCD_9000	ABCD_8000
ABCD_9000	ABCD_7000
ABCD_9500	ABCD_8000
ABCD_8000	ABCD_7000
ABCD_8000	ABCD_7500
NONE	ABCD_8888
NONE	ABCD_6000

The university has requested that the output match the following for (project2A.tab):

Please enter the prereqs filename (or simply press return to run all of the test cases)
Found 8 vertices and 7 edges in ./project2A.tab
Course order:
BIOL_2010
EXSC_3830
EXSC_4240
EXSC_4260
EXSC_4000
EXSC_4010
EXSC_4230
BIOL_2020

Note, other topological orders exist. Your program does not have to match the order of this example exactly, it just needs to be a valid topological order. You do need to display "Course order:", then the vertices in the topological order. Do not display other information after this.

Requirements

Your program needs to meet the the following requirements for full points:

Create a Digraph class (see below for description).
Create your own test input files for various conditions (for example, disconnected graphs, vertices with a prerequisite of NONE, etc.) include them with your submission. These files should follow the same syntax as the example (namely, vertices are separated by a TAB character).
Copy and paste the rubric below into a .txt file and indicate a value for each "_____", including the number of hours spent. Include this .txt with your submission.

class Digraph:
This class should store a digraph. Furthermore, this class should contain:

Appropriate constructor(s)
Private data members:
1. Edge information as either an adjacency matrix or an adjacency list
2. Number of vertices
3. Number of edges
4. Vertex labels
Methods to support adding, removing and printing individual vertex information
A method that implements topological sorting

Additionally, do not use Swing components (to accommodate the grading pipeline).

Rubric:

Points      Item
----------  --------------------------------------------------------------
_____ / 10  Style
            + Code is indented correctly
            + Functions should be no longer than 1 page
            + Documentation: (written for another software developer)
              * All source code files include Javadoc header block with description, author, version/date, etc.
              * Javadoc (with block tags) before each method
              * All non-trivial variables are commented
              * Comments included before major portions of code
_____ /  0  Program compiles without errors
_____ /  0  Program executes without crashing
            Requirements met:
_____ / 20  + Digraph class with appropriate methods and data members
_____ / 40  + Topological sort gives correct results
_____ /  8  + Test files [that you made]
_____ /  2  Completed rubric

_____ / 80  Total


_____  Approximate number of hours spent

I, (REPLACE WITH YOUR FULL NAME), affirm that the code that I submitted is my own work and that I did not receive help that was not authorized by the instructor.

Copy and paste this rubric into a rubric-project2.txt file (not a .docx, .doc nor .rtf file). Think of this as a checklist to ensure that you receive the maximum points possible. For each grade item, fill in your estimate for the grade you deserve. Additionally, include your estimate of how many hours your spent. Lastly, replace, "(REPLACE WITH YOUR FULL NAME)" with your full name to indicate that what you are submitting is entirely your own work.

Submission

To facilitate grading, structure your program so that the following commands will compile and execute it:

javac *.java
java TopologicalSort

if main() is in a class named TopologicalSort. Otherwise, use:

javac *.java
java Digraph

This also means not using the package keyword.
Before submitting this assignment, make sure that there are no compilation errors. If there are errors, fix them before submitting. You may need to edit and compile your program multiple times before it compiles successfully. Verify that the output is correct (meaning that every single character matches the output). Once you are able to successfully run the program with the correct output, you are ready to submit the program. Submit your source code, test files and rubric to the appropriate Assignment tab/folder in CougarVIEW.

Notes

Before writing any code, decide whether to use an adjacency list or an adjacency matrix (and why).
A vertex label is the string associated with that vertex (e.g., "BIOL_2020").
You can assume that there will be less than 200 vertices in the graph.

Optional (worth 0 points!)

Extend your topological sort to produce all possible topological orders.
Make a second class with the other graph implementation (adjacency matrix or adjacency list).

Algorithms Analysis and Design

CPSC 6109