This lab will investigate the implementation of a graph class using an adjacency matrix representation.

1. Copy the files:
   • /dept/cs/cs230/www/labs/lab10/main.cpp
   • /dept/cs/cs230/www/labs/lab10/graph.h
   Create a new project as usual and look over the files. The main program is a simple application that allows the user to interactively add edges to a graph with a set number of vertices.

   Of more interest to us is the graph class itself, of which you are given only the public interface. Read through the file comments and make sure you understand what each method is supposed to do. You will be providing an implementation for the graph class based on an adjacency matrix. As you examine the class interface, think about how you will implement each method.

   The remainder of this lab consists of hints on how to proceed.

2. Private instance variables. You will need two private containers: one to hold the vertices, and the other to hold the adjacency matrix itself. Use STL vectors for this (remember they are templated).

   Note that for the adjacency matrix, the container will actually be a vector of vectors. In addition, you will need to distinguish between edges that exist and those that do not, while at the same time storing the edge weights for those that exist (the edge weight is of template type Edge). To do this, make the "inner" vector of the adjacency matrix a vector of pointers to Edge; a null pointer indicates that the edge does not exist.

3. Constructor. The constructor will need to fill in both the vector for the vertices and the n x n adjacency matrix based on the number of vertices. You can create a "blank" vertex using the constructor Vertex(). Take care when populating the nested vectors for the adjacency list; it is best to first construct a single row (a vector of n null Edge pointers), and then repeatedly use push_back to add rows to the mtrix.

4. Number of vertices (vsize). You should be able to implement this method without adding another private variable to the class.

5. Access and existence methods. The methods vertex, exists, and edge can all be implemented simply, but be careful with the adjacency matrix; remember that it stores pointers to the edges and not the edges themselves!

6. Adding edges. Again, here you need to be careful and remember that the matrix stores pointers. You will need to create the edge itself using the C++ new operator. You should also check to see if the edge already exists, and if so just return without changing it. One last pitfall is to remember that the graph is undirected; what does this imply about the adjacency matrix?

7. Running the program. If you get this far, you should now be able to build and run the main program. Try it out, debugging any errors.

8. Improvements. If you still have time left, you might want to try the following improvement. Since the graph is undirected, we can get away with storing only half of the full adjacency matrix, using less memory. How would you change your class to do this?

9. Adjacency lists. If you manage to get this far, think about how you would implement the graph class using an adjacency list. How would the private instance variables that you use change? How would the implementation of the class methods change? Copy the graph class to another file and make as many of the modifications as you can.

At the conclusion of this lab, take a moment to review the following:

You have explored the interface and implementation of a graph class based on the adjacency matrix representation.