Graphs are a very important data abstraction, and subsequent labs will build on the graph class you develop in this lab.

Iterators provide a way to access a collection of data elements without exposing the underlying implementation -- this is a good information-hiding technique. For example, when writing programs that work on graphs, one may want to take a vertex, say vertex 5, and check all its neighbours for a certain property. Without reference to the underlying implementation of the graph, we will want to be able to do the equivalent of demanding, "Give me a neighbour of vertex 5." Then, perhaps: "Give me another neighbour of vertex 5." And so on, continuing to get a new, as-yet-unprocessed neighbour of vertex 5. Eventually, vertex 5 will run out of neighbours; you should be checking for that.

Iterators are a design pattern that you can implement yourself; or we can use the Standard Template Library (STL) classes; these are known to the g++ compiler by simply including the appropriate header files. (This is done for you in the files provided.)


You will implement parts of a Graph class, some of which is already provided for you. The graph representation is an adjacency list. You will use an Standard Template Library (STL) class called a vector.

A vector is a container that offers sequential access. It is sufficient to "include <stdlib.h>" or "include <vector>" in your header file to have access to this class. You declare a vector of integers as follows.
vector<int> aList;
for (int x = 0; x < 10; x++)  aList.push_back(x)

vector<int>::iterator neighbour = aList.begin();
while (neighbour != aList.end())  {
 cout << *neighbour < " ";
 neighbour++;
 }
return 0;
}
The output to the above will be the contents of the adjlist. It will print out "0 1 2 3 4 5 6 7 8 9". The "push_back" operations pushes the value onto the back of the list of values within the vector. Note that the operator "++" is overloaded for this class, to increment the iterator to the next value in the container (vector).
Other useful vector functions are clear(), empty(), front(), insert(iter, val), pop_back(), reverse() and size().


The input format Your program will read in graph data in the following form:

5
0 1 24
1 4 3 
1 2 16
3 2 14
4 2 6 
4 2 9 
5 5 5 

0:    1 (24),
1:    0 (24), 4 (3), 2 (16),
2:    1 (16), 3 (14), 4 (9),
3:    2 (14),
4:    1 (3), 2 (9),

1. Write the code that will construct a graph, given the name of a file of graph data -- return 0 if not found, 1 if found. You are to use the Adjacency List representation. You do not have to enforce simplicity -- if there are multiple edges or self loops, so be it.
   Note that each edge must be entered into two adjacency lists.
   
   This step involves amending graph_read so that it works -- i.e., where it says "write your code here" you provide the code that reads in the neighbours of vertex u and the weight, as per the format.
   
   
2. Write the code for add_edge, remove_edge, and adjacent.
   
   
3. Add the capacity to create a new graph, with all the information about the graph input by the user. You will edit testapp.cpp so that a new graph can be created. You must use the graph function add_edge(u,v) to insert edges into the new graph.

You are to use the provided "testapp.cpp" and "graph.h" and "graph.cpp" files as a starting place. Note that the provided files are primarily stubs, You will have to allow the edges to have weights, and ensure symmetry (for the undirected graphs that we assume).

Test your code thoroughly.


Everything but the data files and the makefile should bear your complete name and student number. Code should be well-documented and well designed. Files are to be submitted via git. A sample graph is provided, called "graphdata1.in". You can create your own for testing (and you should!).