Project 5 is worth 6% of your grade.

NOTE: failure to follow ANY of the general guidelines outlined in this and prior project descriptions in this course may result in the loss of points on this project.

As with all projects it is extremely important to begin early. There are generally a number of details contained in a project description such as this one. Please note that failure to follow the details outlined in the project description could result in a substantial loss of points so it is very important to pay close attention to the project description.

Note that email regarding project questions will go unanswered and the means for obtaining assistance on a project is through office hours. See the course syllabus for additional information regarding these policies. In particular the course syllabus states that email is for "emergency purposes only" and if you do send email you must include the appropriate information (including your full name, login ID and class section number) - as specified on the class syllabus.

• To design your own classes
• To implement a templatized Graph class using an adjacency list
• To implement Prim's algorithm for minimum spanning tree
• To use Standard Template Library in your implementation

CTS (Campus Technology Services) is interested in installing the next generation of fast networks that will connect the computer labs across the campus. It wishes to make the installation as cheaply as possible. To meet this goal, CTS has made some estimates of the cost required to connect any two computer labs on campus. This information will be provided as part of the input file used by your program.

CTS has hired you to find the cheapest way to connect all the computers given this information. Being a clever computer science major, you realize that this problem can be solved by running a minimum spanning tree algorithm on a graph.

You will therefore write a Graph template class, which will implement a graph using an adjacency list representation. In the graph, the vertices represent the computer lab sites (e.g., AVW, Centerville, CSS, EPSL, Hornbake). The edges will represent the cost (in some monetary unit) required to connect two computers labs with the new network connection. The Graph template class must support a wide variety of operations such as adding and deleting a node, adding and removing an edge, etc.

You will then implement Prim's algorithm as a regular (non-member) function. Prim's algorithm computes the minimum spanning tree (called MST, for short) of a graph (call it G). A minimum spanning tree is a tree which uses a subset of the edges from G, which is assumed to be connected.

In the first four projects, you've been provided .h files and a complete description of all methods that you had to implement. In upper level computer science courses, such files will rarely be provided. You will often be given project descriptions that are not as detailed (compared to the project descriptions in intro. classes), and may have to decide which classes to write, how many classes, etc. Furthermore, each student's projects may not always be expected to produce exactly the same outputs, so you may have to decide what outputs your program will produce. All of this will require planning and thought.

To help you make this transition, this project will not have the same kind of detail. You will not be told every single class you must write. You will not be provided any .h files or .cpp files (except a driver program). You will have to plan the project, as well as implement it.

Here are the goals of this project:

1. To write your own .h and .cpp files

   There will be no .h or .cpp files provided to you. You will have to write all .h and .cpp files. You will also have to decide which classes to write (there will be some required classes, while the rest must be developed on your own).

2. To implement a Graph template class using an adjacency list representation.

   A graph typically consists of vertices (usually corresponding to integers) and edges, with edge weights. You will implement a graph template class, which will allow you to refer to vertices of any class/type that you wish. For example, you might have a graph where the vertices may be strings, and you will refer to edges by indicating two strings (one for each vertex).

   Although you will write the .h file and the .cpp file for a Graph class, everyone's Graph class sould behave similarly (based upon the GraphDriver.cpp file). Rather than provide you with a .h file which would guarantee that everyone's public interface is the same, you will be provided a file called GraphDriver.cpp.

   You can imagine that someone has provided you the driver program (and its output), but no longer has Graph.cpp nor Graph.h. They want you to figure out what Graph.h and Graph.cpp must have contained to run the driver in GraphDriver.cpp. GraphDriver.cpp makes calls to all of the public methods you must implement. You will also be provided GraphDriver.out, the output file generated by GraphDriver.cpp, to see the results of running GraphDriver.cpp.

3. To use several STL classes in an implementation.

   To implement the Graph class, you will use container classes from the STL (standard template library). In particular, you are expected to use the vector template class, the map class, and the list class. You are also expected to use STL iterators to process instances of these classes.

   Given the use of STL in industry (and its appearance in textbooks), having some experience using STL would be useful.

4. To implement Prim's algorithm using only the public methods of Graph.

   So far, all of the methods you've implemented have been member functions. Usually, member functions are easier to implement than non-member functions because you have access to all methods in the class as well as any private data members. However, the usefulness of a class is often based on how easy it is to carry out tasks with the public interface.

   Therefore, in this project, you will implement Prim's algorithm as a regular (non-member) function. This function will take a Graph object as parameter, and must compute an MST (resulting in a new graph) by calling only public methods of Graph.

   Prim's algorithm will be described in pseudocode. There may be more than one way to implement this algorithm (for example, you may have to decide between using an array, or an STL list, or an STL vector, or a class you've written, or will write). In future courses, you may be asked to implement algorithms or code written in pseudocode (or less). You will need to understand the pseudocode (algorithm) thoroughly before implementing it.

5. To design at least one class on your own.

   While it's convenient for us to test your code by providing .h files to you, this also means you have not been given the opportunity to decide which classes to write and how to write them. This has resulted in students writing projects using one class and one main in future courses.

   You've been given many classes that are reasonably well-written during the course of the semester and may serve as models for the classes you choose to write. Nevertheless, using a well-written class and creating one are two different tasks. Therefore, you will be required to write at least one class on your own.

   You should design your classes in a sensible way. Write all methods that are reasonable for that class. Do NOT simply write methods needed for the project, and no more. For example, if it makes sense to write an assignment operator, you should write one, regardless of whether it is used in your project or not.

Please note that all programming projects in this course (including this one) are to be done independently or with the assistance of the instructional staff of this course only.

Please review the policies outlined on the class syllabus and below concerning the use of class computer accounts (Acceptable Use Guidelines) and concerning the University's Code of Academic Integrity. The instructors of this course will review all of the programs submitted by students for potential violations of the Code of Academic Integrity and if it is believed that a violation has occurred it will be referred to the Office of Judicial Programs and the Student Honor Council.

Note that "hardcoding" is also considered a violation of academic integrity.

If you are unclear about any of the policies of this course you should ask either of the instructors for further clarification. NOTE: unless explicitly specified otherwise these policies apply to all assignments in this course:

Code of Academic Integrity
Guidelines for Acceptable Use of Computing Resources

All your programs in this course should be written in ANSI C++, which means they must compile and run correctly with "cxx -w0 -std strict_ansi" on the OIT UNIX Class Cluster (dc.umd.edu).

Your program must have a comment near the top which contains your name, login ID, your section number, your TA's name, an estimated time it took to complete the project (in hours) and an original description of the action and operation of the program (thus at least 6 items neatly organized and easy to read).

Your program should be written using good programming style and formatting, as discussed in class and throughout your textbook. For this project, style is considered to consist of:

• neat and proper indentation and formatting (including both "horizontal" and "vertical" whitespace - blank lines)
• keeping all lines less than 81 characters long
• writing clear and readable code
• commenting code as necessary - each method/function you define in a .cpp (source) file must have a "header" comment at the top of the method/function including the name of the method/function, a brief description of what it does (including any data members it modifies).
• generally (but not necessarily always) any "stretch of code" longer than 6-10 lines should have one or more comments (sometimes certain sections of code will have more comments than others but in general there should be comments interspersed with your code).
• using meaningful and descriptive names for functions and variables

Answers to "frequently asked questions" will be posted via the main projects page. Prior to asking a question or submitting a project you should check the FAQ to see if any important information has been covered there. In addition to answers to FAQ's, any important information pertaining to a project will be posted on it's FAQ.

Note that the FAQ is considered part of the project description and thus just as important to read and review - even after you have submitted a project you should periodically check AND READ any new FAQ's posted. Once the project deadline has passed no new FAQs will be entered for that project and thus you can then stop checking it.

Classes you may use:

If you wish, you may use any of the classes from any of the first four projects. You may also modify those classes to make them behave the way you want (for example, by adding additional methods). However, data members that were private before should remain private now.

You may develop any class(es) needed for the project. However, such classes must be written on your own, without assistance from anyone other than the teaching staff (CMSC 214 TAs and instructors). No classes may be obtained from friends, the Internet, etc.

Classes you MUST implement:

You must implement a Graph template class. You may decide how many template parameters the Graph class requires (it should be either one or two, depending on how you choose to implement the Graph template class---the GraphDriver.cpp class only uses one template parameter, but you can choose to use two, if you believe it makes sense to do so - if so you can modify the GraphDriver.cpp file to use two template parameters).

The Graph template class MUST have the following private data member (you may choose to name the data member as you wish).

       vector< list< EdgeData > > adjacency_list;

You are not required to have the following data member, but it may be convenient to do so.

       vector< GraphData > lookupTable;

        lookupTable[ 0 ]

Since this is a template class, you will need a template instantiation file. For convenience, you must call this file Instantiations.cpp as in previous projects.

YOU MUST IMPLEMENT GRAPH AS AN adjacency list. ANY ADJACENCY MATRIX REPRESENTATION will receive little to no credit!

Required functions:

You must write a function called:

        computeMST

This function must take (at least) TWO parameters:

1. a Graph object, by const reference, (this graph can not be altered by the function)
2. a key representing which node to start the spanning tree. The key depends on how you choose to implement the Graph template class.

computeMST must return a Graph by VALUE, which will be a new graph representing the MST as computed by Prim's algorithm; computeMST cannot be implemented as a member function of a class.

You must use Prim's algorithm to implement the minimum spanning tree. See the primary output to see the result of calling Prim's algorithm.

For Prim's algorithm you can assume that 99999 represents infinity.

ALTHOUGH THE GRAPH TEMPLATE CLASS SUPPORTS ADDING directed edges, YOU WILL IMPLEMENT PRIM'S ALGORITHM FOR AN undirected GRAPH. YOUR GRAPH CLASS will have METHODS that SUPPORT UNDIRECTED EDGES.

You MAY add additional parameters to computeMST, if you wish.

You may add additional helper functions in the prim.cpp file, as you desire.

PROJECTS NOT USING Prim's algorithm TO FIND THE MST WILL LOSE SIGNIFICANT CREDIT.

You can assume that edge weigths in the graph provided for computation of the MST for most tests will be unique (no two edges have the same weight). In addition, the edge weights will be positive values. If there are non-unique edge weights 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 prim.h and this should ONLY be #include'd by any file that uses computeMST (and NO OTHER FILES) - in the header file you will not declare a class or anything like that - just the prototype for computeMST (and any other functions that other files will use that are defined in prim.cpp - note that this should be very few functions if any others at all).

main() function: (File main.cpp)

You must also write your own main.cpp (driver) file which will process a set of commands provided in the standard input. For example, the file primary.output is the result obtained after the commands available in primary.input has been processed by the driver via input redirection. In a similar fashion, the file secondary.output is the result obtained after the commands in secondary.input has been processed by the driver.

The input your program receives is organized in two parts: information about labs, and commands to process data. A lab has a name, managers, and a set of computers (each has a name, type, and IP address). The commands provided will allow you to print information about a lab, create/modify a graph that represents possible connections between labs, compute the MST associated with a possible graph, etc. Check the provided inputs and outputs for more details.

Your driver must handle the following tasks:

1. Reads the number of computer labs
2. Stores information for each lab
3. Then, in a loop, it must process the following commands until QUIT is processed.
   1. ADD_VERTEX <computer_lab>

      Add the vertex in the Graph with the given name. The new vertex must have an index that is 1 greater than the maximum index used so far (e.g., if the graph contains four vertices, then adding a fifth vertex will make that vertex have an index of 4. Vertices are numbered from 0).

   2. DEL_VERTEX <computer_lab>

      Deletes the vertex in the Graph with the given name. See primary.output and GraphDriver.out to see what modifications are made to the graph upon deletion.

   3. ADD_EDGE <computer_lab> <computer_lab> <cost>

      Adds an UNDIRECTED edge between the two computer labs of a certain cost. See primary.output to determine what the output should look like.

   4. DEL_EDGE <computer_lab> <computer_lab>

      Deletes an UNDIRECTED edge between the two computer labs.

   5. UPDATE_EDGE <computer_lab> <computer_lab> <cost>

      Updates an UNDIRECTED edge between the two computer labs with a new cost. This only succeeds if the two labs exists in the graph. You may assume the cost is non-negative.

   6. PRINT_LAB_INFO <computer_lab>

      Prints the information about a given computer lab.

   7. PRINT_LAB_MANAGERS <computer_lab>

      Prints the list of lab managers at a given computer lab. You should do something reasonable if there are no lab managers, but the lab exists.

   8. PRINT_LAB_COMPUTERS <computer_lab>

      Prints the list of computers at a given computer lab. You should do something reasonable if there are no computers, but the lab exists.

   9. PRINT_GRAPH

      Prints the current graph.

   10. COMPUTE_MST

       Computes the minimum spanning tree using Prim's algorithm and prints the result. Also, prints the minimum cost.

   11. CLEAR_EDGES

       Removes all the edges of the graph.

   12. CLEAR_GRAPH

       Removes all the vertices and edges of the graph.

   13. QUIT

       Quits out of the program.

LENGTHY FUNCTIONS will be PENALIZED! Use helper functions!

Files provided to you:

You will be provided the following files:

GraphDriver.cpp and GraphDriver.out : These files will help you determine how Graph.h and Graph.cpp must be written.

primary.input and primary.output : These are self-explanatory. Your project will not be accepted if it doesn't generate the primary output.

secondary.input and secondary.output : These are extra inputs to show the expected output for commands not necessarily present in the primary.input. Your project doesn't need to generate the expected secondary output in order for your submission to be accepted.

prims.algorithm : Describes how Prim's algorithm works

STL.tutorial : A brief tutorial on STL (as much as is needed for the project).

NEW - readme file: (File: README.txt)

For this project you must submit a unix TEXT file named README.txt     In this textfile, include the following:

      *  The classes you wrote
         ---------------------
         Explain briefly, which additional classes you wrote, and why you
         wrote them.  You do not have to explain the Graph class or any of
         the classes used from earlier projects.

      *  A brief description of the class methods for classes you wrote
         --------------------------------------------------------------
         Explain briefly all of the methods for each of the classes you
         wrote that are listed in the section above.

Inputs used for grading:

Inputs used during grading will have the same format as primary.input and secondary.input
They will include a list of computer labs and relevant information. This information will then be immediately followed by a list of commands, which will always end in QUIT. None of the commands will be "invalid" (meaning, that they are the commands found in the section above regarding the main.cpp file).

Your program should also be able to create the output found in GraphDriver.out when compiled with GraphDriver.cpp - note that the only change permitted to GraphDriver.cpp is to change the declarations from a template with one parameter to a template with two parameters (meaning you can change at MOST 2 lines in the GraphDriver.cpp file and those two lines are not any 2 lines but the two lines where a Graph variable is declared and you can ONLY add a 2nd template parameter.

Possible grading criteria:

Some of the issues you will be graded on:

1. Your choice and implementation of class(es)

   These are the kinds of criteria the graders may consider:
   -- were the classes reasonable (reasonable methods)?
   -- did they "reinvent the wheel" (rewrite classes that have been previously used)?
   -- were there too many/too few classes?
   You may wish to do some planning prior to writing your classes.

2. The number of methods/functions written

   If you write very long functions or methods (several pages), you may be graded poorly. If there's a way to break down a class or function into helper functions, so that each method is short, yet does a well-defined task, you should do so.

   Also, you may also be penalized if you implement constructors, copy constructors and destructors when they are unnecessary (i.e., your class would work fine if those methods were not implemented).

3. The design of your Graph class

   Your Graph class must be a template and should support all of the functionality found in the GraphDriver.cpp file.

4. The usual requirements and any other relevant details

   Does your program produce the primary output, is it commented, etc ...

1. Many requirements for the implementation of this project have been specified throughout the description provided above and in the files found in the posting account; double check those requirements are satisfied by your project.
2. You must write a file called Graph.cpp and Graph.h which must produce the output in GraphDriver.out when linked with GraphDriver.cpp (actually, when linked with the object file from an appropriate template instantiation file of Graph.cpp). This is NOT the primary, however. You will not need to produce the output from GraphDriver.out to get submit the project. You are also permitted to change the declaration of the Graph object, if you want to have two template parameters instead of the one shown in the class.
3. As stated earlier, Graph.h must use vector, map and list template classes from STL. Other STL classes, algorithms may be used in addition to the required ones. However, you should only need the classes and methods described in the STL.tutorial (In other words, feel free to try other STL classes).
4. The Graph template class must support all the methods used in GraphDriver.cpp. NO ADDITIONAL PUBLIC METHODS MAY BE ADDED (except additional constructors, operator=, and destructors, if you feel they are necessary---you may also add ONE additional public method, which will compute the total cost of all edge weights).
5. You should be able to compile GraphDriver.cpp plus an instantiation file (for the Graph class) and produce the output shown in GraphDriver.out
6. The Graph template class must be a template class (with at most two template parameters).
7. The Graph template class must be an implementation of the adjacency list. Implementations of an adjacency matrix will receive little to no credit.
8. The Graph template class MUST have the following private data member:

          vector< list< EdgeData > > adjacency_list;
   

   where vector and list are STL container classes, and EdgeData is a class (or structure) that you write. Other choices will receive little to no credit.
9. EdgeData must be defined (as a class or structure).
   It should contain only two data members:

   destIndex -- an int value representing a destination index of an edge (an edge can be considered a source index and a destination index, where the indexes represent vertices).
   weight -- a float value representing the weight
   

   You can add additional data members to EdgeData, but it should not be necessary to do so.

10. You MUST have a file called prim.cpp which must contain a non-member function called computeMST, as described earlier. computeMST must take at least TWO parameters: a Graph template object by const reference (you may assume it is connected) and a key representing the vertex where Prim's algorithm will begin. You can add helper functions to the file prim.cpp, which computeMST will call.
11. YOU MAY NOT INCLUDE .cpp FILES in OTHER .cpp FILES!!!! This means .h files must be used correctly. The only exception is Instantiations.cpp which is permitted to (and must) include .cpp files of template classes.
12. You may add any other files you feel are needed, provided you have written the code by yourself.
13. You must write a main.cpp file/class which will run the code provided by primary.input or any other file that has a similar format to the primary.input file.
14. You must have an instantiation file named Instantiations.cpp   Every template class or function used by your program must be instantiated in this file. Your program must link in this instantiation file when compiling the executable. NOTE YOU MUST PUT IN ANY TEMPLATE FUNCTION INSTANTIATIONS IN THIS FILE AS WELL AS ANY TEMPLATE CLASS INSTANTIATIONS.
15. Primary Output Requirements - Your project must generate results that match the primary output when run with the primary input and the main.cpp file you create. The results generated by your program will be considered correct if and only if this command reports no differences. The expected primary input and output are available in the posting account. ANY PROJECT NOT GENERATING THE CORRECT PRIMARY OUTPUT WILL RECEIVE A GRADE OF 0.
16. During the grading of your project, your code may be tested with a main.cpp that is different from the one you provide. That means that those functions not necessarily tested by your main.cpp may be tested. Make sure that copy constructors, destructor and assignment operators have been implemented in such a way they work correctly no matter what main.cpp is used.
17. Your code must not produce memory leaks. As long as it does not have leaks nor does it "wastefully" use dynamic memory, you may assume that memory allocations will always be successful.
18. You must write the Graph code "from scratch" as well as the code that does Prim's algorithm and any related algorithms to process your graph (you may not use system libraries to do these key parts for you). If there is any doubt on this ask the instructor.

1. READ THESE HINTS.
2. This project has a number of details in it and thus it is recommended taht you start working on it immediately. DO NOT WAIT UNTIL FEW DAYS BEFORE THE DEADLINE. Office hours are usually crowded the days before the deadline; if you wait until the last minute you might not be able to get the help you need and it will be very difficult to complete all the required tasks in time.
3. For each class you implement, you should (must) have a test driver that verifies the methods have been implemented correctly. Save those test drivers for future reference.
4. Keep backups of your projects (in a special directory separate from the one you do your main working in).
5. Remove any unnecessary files from your account. The compilation process can be interrupted if not enough disk space is available (familiarize yourself with the UNIX quota command).
6. The template mechanism for defining operator<< can be somewhat confusing. Instead of trying to define the operator, implement a public method called print(). Used this method to print the graph. Once your graph is working properly, then implement the operator<< NOT as a friend function, but simply as a function that calls print() appropriately on the provided object. The following is one possible declaration you may used for the operator<< :

         template <class GraphData>
         class Graph;
   
         template <class GraphData>
         ostream& operator<<(ostream &out, const Graph<GraphData> &data );
   

7. Compile as frequently as possible early on during this project. Compilation using the STL and templates tend to generate compilation errors that are very impressive (overwhelming at first), but usually the problems causing the compilation problems are simple. If you add a little bit of code and compile, it will be easier to track down any problems.
8. REREAD THE PRIOR HINT AND TAKE IT SERIOUSLY - TEST YOUR CODE IN PIECES - do not write hundreds of lines of code and then test it - write "pieces" and do a short quick test on them.
9. TEST YOUR CODE IN PIECES and NOT on the primary.input until you have 90+% of the code written.
10. Before you use an STL facility, familiarize yourself with it, by writing/compiling small examples.
11. See the FAQ online throughout the project for other possible hints.

Since this is the first project where you have to think about design, here are some strategies:

1. Decide what class(es) are needed to read in the input for the computer labs. Decide which need to be developed from scratch, and which do not. Begin to write .h files for them and decide data members and methods.
2. Read over GraphDriver.cpp Highlight all methods used, and begin to write Graph.h
3. When you implement Graph.cpp, look at the behavior of GraphDriver.cpp in the output file GraphDriver.out. This will tell you how the output should behave, since you have not been provided with a BNF.
4. Practice Prim's algorithm on paper with a few examples, until you feel confident that you could explain to someone how the algorithm works (don't write code), then begin to decide what you need to implement the algorithm, given what you wrote in Graph.h
5. Most of the driver program will use methods implemented in Graph.h, however, some may not, so keep that in mind.
6. You may wish to write a DataManager class if you feel that would make the implementation better.
7. STL features are used for the implementation of the Graph. However, you don't necessarily need to use the STL for every component you plan to implement. For example, if you decide to implement a priority queue using a class of your own, that's fine. However, it is recommended you explore whether the STL can be used in any function you plan to implement; the STL could save you some time.

For this project (and the rest of them) you must make a UNIX Makefile to manage the compiling of your project. The makefile must be named makefile and should be written so that the first target is p5 and that typing make p5 or just make will result in the necessary files being compiled to create the executable p5 which can then be run as specified below in the Sample I/O section. Note that your makefile should create (and leave) the necessary .o (object) files and should not recompile unnecessarily (meaning it should not have redundant/incorrect dependency lists for the targets). Your makefile does not have to have any "extra" targets such as make clean or make tar however it is ok if it does.

The makefile must use the cxx compiler with the -w0 and the -std strict_ansi options when compiling.

NOTE THAT YOUR PROJECT WILL NOT SUBMIT UNLESS IT HAS A WORKING MAKEFILE and thus you are strongly encouraged to test this well in advance of the due date to make certain your makefile is working properly. If you have difficulty using the makefile reread the makefile tutorial in the posting account:

~fjm14001/Tutorials/Miscellaneous/makefile+tar.g++

When compiling your program should not generate any compiler warning messages.

For this project you will be provided with a primary.input and primary.output file. Both of these files can be found in the posting account in the appropriate directory. YOU SHOULD COPY THE primary.input FILE FROM THE POSTING ACCOUNT - DO NOT ATTEMPT TO TYPE THIS FILE IN OR CUT AND PASTE IT FROM THE WEBPAGE - INSTEAD, COPY IT (using the UNIX cp command) DIRECTLY FROM THE POSTING ACCOUNT.

In order to pass the MRC (minimum running criteria) for this project your program must generate the primary.output when tested with the primary.input as follows:

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

The first line (make p5) is the step to compile the project - note that you should strive to have NO COMPILER WARNINGS (points may be deducted for having compiler warnings). Note once again: you must use the cxx compiler in your makefile and that the -w0 and -std strict_ansi options must be used (points may be deducted for failing to use the compiler and options specified).

The second line (p5 < prima...) is a way to run the p5 program and redirect input (<) to come from the primary.input file (instead of the keyboard) and have the output redirected (>) to the file my.output (instead of the screen).

The third and final line (diff -bwi ...) is how we will test to make sure that your output (my.output) matches the expected output (primary.output). The diff command will print to the screen any lines in your file that do NOT match with the corresponding lines in the other file - if nothing gets displayed that is good news - it means that your output matches the expected output. The -bwi options tell the diff command to ignore case (be case-insensitive) and to ignore extra blank spaces. You should strive to have your output diff with the primary.output without the -bwi options, as that forces you to have a "more perfect" match - however when grading we will always use the -bwi option.

In the posting account, in the ~fjm14001/Projects/P5/ directory, there are the following files (and possibly others):

     GraphDriver.cpp        GraphDriver.h      STL.tutorial
     primary.input          primary.output     prims.algorithm
     secondary.input        secondary.output

When we test your project we will compile it as follows:

%  make  p5

%  make

NOTE: SUBMIT TAKES TIME TO RUN - you should always attempt to submit BEFORE 11pm and should do so long before 11pm - in particular if you run the submit command at 10:59pm it will not finish testing your program in time and it will end up being late.

IT IS VERY STRONGLY RECOMMENDED THAT YOU ATTEMPT TO SUBMIT THIS (and every) PROJECT AT LEAST ONE FULL DAY (24-hours) IN ADVANCE. In particular no extensions will be granted for problems encountered in trying to get your program to submit unless there is an error that the majority of students encounter with the submit program we provide and/or the corresponding instructions. Additionally you should make a safe backup copy of all your work PRIOR to beginning the process to submit your project (as described below).

For this project you must "tar" and submit the following files (primarily consisting of the source (.cpp) and header (.h) files used by your implementation including your makefile):

     main.cpp         prim.cpp        prim.h          Graph.cpp
     Graph.h          makefile        README.txt      Instantiations.cpp

     plus any other SOURCE or HEADER files that you created and used that
     are necessary and relevant to this project (including your
     GraphDriver.cpp - which should be IDENTICAL to our version or
     extremely close with at most 2 changes as specified above).

You must do this using the tar command similar to how it was used in project #2 - double check your tar file to make sure it has all of the required files and no other extra files. 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).

NOTE THAT YOUR source files (.cpp) must be named the same as the corresponding header files (.h) - so for example the source file corresponding to Foo.h must be named Foo.cpp (which is just Foo.h with the .h replaced by the .cpp).

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.