Final phase project 3:
Due Friday 19 May 2006 by Midnight
phase 2<--broken
For those who need extra points to count toward program 1, the AVL tree, you may opt to implement Topological breadth, depth sorts AND shortest Paths from Chapter 12 Kruse. Hopefully you did not sell back your textbook. If you did go to the library and check it out OR you may borrow my book if I'm in town.
You must get all three extensions working to get any points. I'll give you 75 points to apply toward program 1. You can't use this alternate assignment to get points for program 2 or 3. If you go over 100 points for program 1 by doing this assignment I will only count 100 points for program 1.
- You must add a 'D' command to main.cpp and a function for adding DIRECTED edges to your graph
- Depth first traversal occurs on the 'X' command
- Breadth first traversal occurs on the 'Y' command
- Shortest paths is the 'T' command
You will have to do some research into these algorithms by reading about them in the book. I will not be around to explain them to you. They took me about 15 minutes each so they are not difficult if you have done all of p3.
Suggestions:
I have to hand the grades in by friday the 26th of May. To get credit you must get your solution into me in time for me to grade it.
- tests t30-t39 test shortest paths.
- tests t40-t49 test depth first ordering
- tests t50-t59 test breadth first ordering
You will have to reverse engineer the test outputs since the writeup will not describe what to print.
For my script to score your work you must:
- put your files at the top level of your turn directory
- provide your own Makefile
- name your executable graph