Topological Sorting
Due Thursday, April 21 by 11:59 pm
Implement the two topological sorting algorithms discussed in
section 5.3 (this is basically problem #8 on page 176).
Your source removal algorithm must be on the order of the number
of vertices plus the number of edges (use the algorithm outlined
in class).
You must use classes as outlined in your assignment to
set up a graph and compute the in-degree of each vertex. Please
note that this means you need at least 3 classes that represent
objects and one program to test. You must have the following:
- A class to represent a graph node on an adjacency list.
- A class to represent an unordered list. You may modify
this class so that it also serves as a queue or you can have
a separate queue class. Either way you need enqueue
and dequeue methods to add to the end of the list
and to remove the first element in the list.
- A class to represent a graph. This class will contain
the functions to set up the graph, compute in-degrees, find
a topological sorting using a depth-first search and find a
topological sorting using the source removal algorithm.
- A program that sets up a graph object, then calls the
function to find a topological sorting using depth first
search, prints the result, then does the same for source
removal.
Classes with linked structures should have copy constructors,
assignment overloading, and destructors.
The
input files will be in the same format as described in that
assignment (here).
Grading
Your program will be graded on a 100 point basis AND your
documentation will be graded on an additional 50 point basis.
Your documentation must adhere to the standards outlined in
this document.
Your directory MUST include a Makefile (20% deduction in the
program part of your grade without one).
Hand In
Tar or zip your directory with all files (including a Makefile)
and send it to me.