CS 32, Fall 2017

Programming Assignment 1

Due: Monday October 30, 11:59pm
Worth: 100 points

PA1 can be done either in two-people teams or individually.

If you are working with a partner, don't just split up the work! Pair programming means working together to solve each of the problems: trust us that it will work more smoothly for you if you do it like that anyway. Also be sure that both partners' names are in a comment at the top of each source code file, and that you properly form a group for this project in the submit.cs system.

1. Download and edit graph.h and its implementation file, graph.cpp, to solve the problem described in Chapter 15 Programming Project 1 (pp. 778-779) of the Data Structures textbook by Main and Savitch. Read the discussion provided by the textbook authors, and you may use their suggestions in your solution, but be sure to follow the specific instructions on this web page.
   • Type your name(s) and the date in a comment at the top of both files.
     [Like always, whether or not we remind you!]
   • Study the parts that are already done in both graph.h and graph.cpp. Also read sections 15.1 and 15.2 of that textbook to fully understand the existing graph definition and implementation.
   • Change the private member variables of class graph as suggested on page 779 of the text, and eliminate the MAXIMUM constant from the class definition.
   • Some other changes you'll need to make to graph.h:
     • Add a constructor that takes an initial allocation for the dynamic arrays, and a copy constructor. Use the following function signatures for them:

               graph(size_t initial_allocation);
               graph(const graph &source);

     • Add a destructor, a resize function, and an assignment operator with the following signatures:

               ~graph();
               void resize(size_t new_allocation);
               graph &operator=(const graph &source);

     • It would be nice (but we won't check for it) if you also edit the comments at the top of the file to reflect the changes you are making to the class definition.
   • Implement all of the new functions in graph.cpp. Also verify that the other functions still work properly with your new class definition. Here are some things to consider:
     • The constructors all must allocate memory (see page 779 again, but also review earlier parts of the text that discuss dynamic memory allocation). Let the default constructor allocate memory for 10 vertices. Careful: there is a mistake in the text on page 779. The right way to allocate an array of bool pointers is as follows:

               edges = new bool*[allocated];

       That is, there should be no parentheses around the bool* part as shown in the text.
     • Implement the destructor to delete the allocated memory.
     • Implement the assignment operator to allocate the same amount of memory as the source graph (not just the number of vertices currently added to it). This function also must be sure to deallocate the memory used by the old graph, and it must be able to handle self-assignment (see text and lectures).
     • Implement the resize function to do nothing if the new_allocation parameter is less than the current size() of the graph. Otherwise this function must allocate the requested amount of new memory, copy all of the graph's data to the new memory, and deallocate the old memory.
     • Change other functions as necessary. For instance, make sure to eliminate any assertions that are no longer appropriate - the graph should grow as needed to handle as many vertices as the user wants to add, so there are no more capacity constraints to check. That means the add_vertex function should call resize when the graph is already full (our solution doubles the current allocation in that case).
2. Compile and test your program at CSIL (by connecting remotely is okay). We strongly suggest you create your own test program, so that you can individually test each of your functions. When you are ready for more comprehensive tests, you may try out the non-interactive test program that we will use to grade your project, graphexam.cpp. Compile it as follows (and heed any warning messages):

   g++ -o graphexam -Wall graphexam.cpp

   Give a test number, 1 to 5, as a command line argument when you run it. For example, the following command will execute test number 3:

   ./graphexam 3

   We prefer that you do not proceed to the next step to submit your work until you are sure that all of your functions are working properly.
3. You will turn in both graph.h and graph.cpp.
   From our class page at https://submit.cs.ucsb.edu/, click the "Make Submission" button next to PA1, or use the following command from a CS terminal:

   ~submit/submit -p 861 graph.cpp graph.h

   Be sure to wait for the results of all tests. If you score 100/100, and you've followed all of the other rules, then you'll earn full credit.

---

Prepared 10/11/2017 by Michael Costanzo
Special thanks to Michael Main, University of Colorado, creator of many parts of this project.