This extra credit is worth up to 25 extra points on project #5.

• To implement Dijkstra's algorithm
• To implement DIRECTED edges for your graph

CTS now wants you to implement a messaging system for it's lab managers to use and part of the software you are writing must be able to find a path from "Lab A" to "Lab B" over which the message will be sent. Rather than just finding any path you figured it would be best to find the "cheapest" path - assume that the higher the cost the edge the more expensive it is to use, thus CTS wants to avoid using such "edges" when possible.

Applies to this extra credit just like all projects in this course.

Applies as well.

See the main description for these policies.

Required functions:

You must write a function called:

        dijkstra

This function must take FOUR parameters:

1. a Graph object, by const reference, (this graph can not be altered by the function - although copies may be)
2. a key representing which node to start the "search" from.
3. a key representing which node to end the "search" at.
4. a boolean which if true means to provide "DEBUGGING" information (as specified in this description).

For Dijkstra's algorithm you can assume that 99999 represents infinity (this would be good to define as a constant).

You MAY add additional parameters to this function, if you wish.

You may add additional helper functions in the dijkstra.cpp file, as you desire. IN FACT IT IS RECOMMENDED that you consider doing this - for example you might consider creating a function which when passed a vector with a valid path and the corresponding graph it returns the COST of that path - note that this is a NON-MEMBER function (and it is perfectly fine and good style as such).

PROJECTS NOT USING Dijkstra's algorithm TO FIND THE PATH WILL RECIEVE LITTLE TO NO EXTRA CREDIT.

You can assume that edge weights in the graph provided for computation of the MST for most tests will be positive (but not always unique). There may be more than one possible valid output - as long as your program finds one of them it will be considered valid for that test.

HEADER FILE - you should create a header file called dijkstra.h and this should ONLY be #include'd by any file that uses dijkstra (and NO OTHER FILES) - in the header file you will not declare a class or anything like that - just the prototype for dijkstra (and any other functions that other files will use that are defined in dijkstra.cpp - note that this should be very few functions if any).

main() function: (File main.cpp)

You will need to modify your main.cpp (driver) file so that it processes the items found in the main project description AND the set of commands provided below:

1. COMPUTE_PATH <computer_lab_START> <computer_lab_END>

   Finds the CHEAPEST path from START to END and prints out that path and the total cost. If no path exists from START to END a message stating so is output according to the following format:

   POSSIBLE OUTPUTS (FOLLOW THIS FORMAT EXACTLY):
   ----------------------------------------------
   Printing cheapest path from START to END
   Take START to A to F to B to END
   for a total cost of 24.3
   
   Printing cheapest path from START to END
   No path exists
   

2. COMPUTE_PATH_DETAILED <computer_lab_START> <computer_lab_END>

   Finds the CHEAPEST path from START to END and prints out that path and the total cost. If no path exists from START to END a message stating so is output according to the following format:

   POSSIBLE OUTPUTS (FOLLOW THIS FORMAT EXACTLY):
   ----------------------------------------------
   
   Printing cheapest path from START to END
   DEBUG:
   ------
   START
   C
   A
   F
   D
   Z
   B
   Q
   END
   ------
   Take START to A to F to B to END
   for a total cost of 24.3
   
   Printing cheapest path from START to END
   DEBUG:
   ------
   START
   C
   A
   F
   D
   Z
   B
   Q
   L
   M
   N
   ------
   No path exists
   

3. ADD_DIR_EDGE <computer_lab_A> <computer_lab_B> <cost>

   Adds a DIRECTED edge between the two computer labs from A to B with the given cost (if either lab is non-existant or an edge already exists this should "fail").

   POSSIBLE OUTPUTS (FOLLOW THIS FORMAT EXACTLY):
   ----------------------------------------------
   Sorry, self loops are not permitted
   Failed to add DIR edge from A to B of cost 10.9
   Successfully added DIR edge from A to B of cost 7
   

4. DEL_DIR_EDGE <computer_lab_A> <computer_lab_B>

   Deletes a DIRECTED edge between the two computer labs from A to B

   POSSIBLE OUTPUTS (FOLLOW THIS FORMAT EXACTLY):
   ----------------------------------------------
   Failed to delete DIR edge from A to B
   Successfully deleted DIR edge from A to B
   

5. UPDATE_DIR_EDGE <computer_lab_A> <computer_lab_B> <cost>

   Updates a DIRECTED edge between the two computer labs from A to B with the given cost.

   POSSIBLE OUTPUTS (FOLLOW THIS FORMAT EXACTLY):
   ----------------------------------------------
   Failed to update DIR edge from A to B of cost 10.9
   Successfully updated DIR edge from A to B of cost 7
   

Files provided to you:

extra.input and extra.output : This is one set up input/output that demonstrates parts (not all) of the extra credit stuff in action.

1. See the main project description. Don't forget to instantiate any templates used.
2. Don't forget to check that your "GraphDriver.cpp" file works properly and provides the correct output as found in "GraphDriver.out"
3. Don't forget to submit your "README.txt" file.

1. No hints available here.

No changes necessary for the makefile. When your makefile creates the p5 executable it should be the one that can do the extra credit stuff as well as the regular project stuff.

To test your project on the posted extra credit input/output you should do the following:

%  make  p5
%  p5  < extra.input  > my.output
%  diff  -bwi  extra.output  my.output
%

If that diff's then your project passed that ONE extra credit test.

IN ADDITION TO THE FILES SPECIFIED ON THE MAIN DESCRIPTION, you must "tar" and submit the following files:

     dijkstra.cpp         dijkstra.h

     plus any other SOURCE or HEADER files that you created and used that
     are necessary and relevant to this project.

Points may be deducted if your tar file contains extra files. IN PARTICULAR: your tarfile should NOT contain any extra files other than those needed to create the executable p5 and it must contain all those text files (.cpp, .h and makefile) necessary to create p5 (with the exception of GraphDriver.cpp which you should also include).

WARNING - BE VERY CAREFUL USING THE UNIX TAR COMMAND - if you use the command incorrectly it may automatically DELETE (permanently) one or more of your files. Make a backup copy of your files before running the tar command. In particular the filename IMMEDIATELY after the -cvf in the tar command, must be the name of the file that you want to CREATE and put the other files into. If that file already exists it (the tar command) will automatically DELETE it and create a new one and if the file doesn't exist tar will just create a new one. To find out more about the tar command there is a "tutorial" in the posting account in the ~fjm14001/Tutorials/ directory also you can type "man tar" at the UNIX prompt to read the man page.

DO NOT EDIT YOUR TARFILE - it turns out that a tar file is a plain text file that you can read, but it may look "weird" inside - that is the way the tar file works and if you modify the tar file IT WILL NOT WORK ANYMORE and we will not be able to test your program.

After you have created the tar file you must then turn in (or submit) that file to us. The way that you do this is that you can type:

%  submit  proj5.tar  5

The submit command will generally display information to the screen and you should read that information to make sure your project submits successfully - if you do not see a message stating that your project was submitted then you should assume that it did not get submitted.

Projects submitted in any other way will not be accepted.

You may submit a project more than once - note however that only the last file you submit will be used for grading purposes - meaning that if you submit twice ontime and then once two days late only the last submission will be graded (the two day late version in this case). See the course syllabus for other details regarding late submissions.

NOTE: you should make a backup copy of all of your work on a regular basis. Extensions due to mistakenly deleted files or individual computer troubles will not be granted. It is also recommended that if you do work and store your files on a personal computer you regularly backup those files by copying them into your class account (at least once a day during any of the days you work on your files).

DOUBLE CHECK WHAT YOU SUBMITTED to make sure that it is correct - in particular create a subdirectory and copy the file you submitted into that subdirectory and then untar it (tar -xvf) and check the contents to make sure they are correct - in particular compile and test the files that were extracted from the tar file. If there is a problem with the tar file you should fix it and try again.