Due Date
See the
calendar for due date.
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:
exsc-prereqs.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
|
|
They plan to use your program for the following prerequisites (with all edges treated equally):
The university has requested that the output match the following for (
exsc-prereqs.tab):
Please enter the prereqs filename (or simply press return to use exsc-prereqs.tab)
Found 8 vertices and 7 edges in exsc-prereqs.tab
Course order:
BIOL_2010
EXSC_3830
EXSC_4240
EXSC_4260
EXSC_4000
EXSC_4010
EXSC_4230
BIOL_2020
or
the following output for
exsc-prereqs-reversed.tab:
Please enter the prereqs filename (or simply press return to use exsc-prereqs.tab)
Found 8 vertices and 7 edges in exsc-prereqs-reversed.tab
Course order:
BIOL_2010
BIOL_2020
EXSC_3830
EXSC_4230
EXSC_4000
EXSC_4010
EXSC_4240
EXSC_4260
or the following for
labTopologicalSorting-test-ugrad.tab:
Please enter the prereqs filename (or simply press return to use exsc-prereqs.tab)
Found 32 vertices and 36 edges in labTopologicalSorting-test-ugrad.tab
Course order:
CSCI_4600
CSCI_4280
CSCI_1010
MATH_1910
MATH_2050
MATH_1920
CSCI_1170
...
Note, other topological orders exist, but
for full points, the output must exactly match the example above.
Requirements
Your program needs to meet the the following requirements for full points:
- Use the following source code as the driver for this lab: labTopologicalSorting-main.cpp.
- Create a Digraph class (see below for description).
- Create your own test input file(s) for various conditions (for example, disconnected graphs) include it(them) with your submission.
- For the topological sort method, iterate over vertices in the order that they appear in the input file. Each time you look for another vertex without a successor, start over again from the beginning of the list of vertices.
- Your program must compile and run in both Visual Studio and on ranger. On ranger, it must compile with the following command:
g++ -std=c++0x *.cpp -o labTopologicalSorting
- Include a completed rubric and number of hours spent on the assignment. Please copy and paste the rubric into a new file inside your project directory. Name the file: rubric-yourlastname.txt.
class Digraph:
This class should store a digraph.
Furthermore, this class should contain:
- Appropriate constructor(s)
- Private data members:
- Edge information as either an adjacency matrix or an adjacency list
- Number of vertices
- Number of edges
- Vertex labels
- Methods to support adding, removing and printing vertex information.
- A method that implements topological sorting (following the algorithm present in the video and in class).
Submission
Before preparing your project for submission, remove the
debug and
ipch directories (if present) and any
.sdf files.
Additionally, remove any other files not associated with labTopologicalSorting.
Zip the whole project folder (
e.g., by right-clicking on the folder and choosing
send to::Compressed (zipped folder)). Name your zip file as
labTopologicalSorting.zip.
Make sure that all of the source code files are in your zipped file.
Submit your zip file at
https://3110.cs.mtsu.edu/.
Rubric:
Points Item
---------- --------------------------------------------------------------
_____ / 10 Documentation:
+ All source code files (.h & .cpp) include file name, author, description etc.
+ Functions and variables
+ All non-trival variables are commented
+ All functions preceded by brief comments
+ Comments included before major portions of code
+ Functions should be no longer than 1 page
_____ / Compiles and runs in Visual Studio and on ranger
Requirements met:
_____ / 20 + Digraph class with appropriate methods and data members
_____ / 40 + Topological sort gives correct results
_____ / 8 + Test file(s) [that you made]
_____ / 2 Completed rubric
_____ / 80 Total
_____ Approximate number of hours spent
Notes
- The tutoring lab has several hours to answer questions.
- 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., "CSCI_3110").
- You can assume that there will be less than 200 vertices in the graph.
- Part of the grading process is automated by using diff. You should verify that your output matches the above output directly with the following commands on ranger:
g++ -std=c++0x *.cpp -o labTopologicalSorting-yourlastname
cp /nfshome/hcarroll/public_html/3110/private/labs/exsc-prereqs.tab .
echo "" | ./labTopologicalSorting-yourlastname &> labTopologicalSorting-yourlastname.txt
diff /nfshome/hcarroll/public_html/3110/private/labs/exsc-prereqs-stdout_stderr.txt labTopologicalSorting-yourlastname.txt
If the two files match exactly (which is what you want) then there should be NO output from diff. If diff shows one or more differences, fix them and run it again. To get side-by-side output (with the answer key on the left and your output on the right), replace the last line with:
diff --side-by-side /nfshome/hcarroll/public_html/3110/private/labs/exsc-prereqs-stdout_stderr.txt labTopologicalSorting-yourlastname.txt
For details about interpreting the output of diff, see the Using diff section on the Misc. webpage.
Optional (worth 0 points!)
- Extend your topological sort to produce all possible topological orders.
- Make a second class with the other graph implementation.
