Lab 7: Graphs (100 pts)

Due Saturday, November 7 at midnight on Catalyst

Part 1: Tutorial on Vectors
  • Although you have not studied vectors in the past, they are a commonly-used part of the C++ language.
  • I would like you to learn how to use them before you leave 22C.
  • Also, they will be very useful in our Graph data structure, as we will create a vector of linked lists to represent our Graph. (Think adjacency list representation of the graph).
  • Therefore, it is time to learn about vectors if you never have before.
  • Don't worry! Vectors are easy - actually easier to use than arrays, as there are many things that vectors do for you.
  • To start, look over the vector tutorial here.
  • If you would like further explanation, you can watch this video here.

Part 2: Graph Implementation
  • Copy the code below into a new header file called Graph.h
  • Then, create a new source code file called Graph.cpp.
  • Since we are not using templates, we are going to write our function definitions inside of the Graph.cpp.
  • We will test them in GraphTest.cpp
  • We will be using the adjacency list representation of a Graph for this data structure.
  • The heart of the Graph data structure will be a vector of linked lists, to store the adjacent vertices of each vertex in the Graph:


  • images/lecture15/adjlistexample.png
    Image source.

  • For this assignment, you could visualize the above Graph as shown in the diagram to its right.
  • 1, 2, 3, 4 and 5 in the left hand column of the diagram are indices of the vector (array).
  • Those values to their right are their adjacency lists which are stored as linked lists.
  • Specifically, for our purposes, we will be representing the Graph as a vector of linked lists named "adj"
  • Thus, we could visualize storing the graph as depicted below for this assignment:
adj[0] (purposely left empty!)
adj[1] = 2 -> 3 -> 4 -> NULL //at index 1, we store the adjacency list of vertex 1
adj[2] = 3 -> NULL //at index 2, we store the adjacency list of vertex 2
adj[3] = 2 ->NULL //at index 3, we store the adjacency list of vertex 3, etc
adj[4] = 4 -> NULL
adj[5] = 2 -> NULL

Header File

#include <iostream>
#include <cstdlib>
#include "List.h"
#include <vector>

using namespace std;

class Graph {

public:

    /**Constructors and destructors*/

    Graph(int n);

    //initializes an empty graph to have n vertices

        ~Graph(); 

    /*** Access functions ***/

int getNumEdges();
int getNumVertices();

/*** Manipulation procedures ***/

void addEdge(int u, int v);
//inserts vertex v into the adjacency list of vertex u (i.e. inserts v into the list at index u)

/*** Other operations ***/

void printGraph();

//prints as the adjacency list representation of the graph

//see below


private:
    int vertices, edges; //number of edges and vertices
    vector<List<int> > adj; // we will use a vector here for our array
    //This vector is the heart of the graph as it stores the adjacency lists of the graph

};

Graph Constructor Help

  • Inside of your Graph.cpp, start by writing the default constructor for a new Graph.
  • The purpose of the constructor is to create an empty List at each vector index (as well as initialize the vertices and edges fields).
  • In other words, first, we will want to create a new, empty List to represent one index of the vector.
  • Then, we will push this new List onto the back of our vector. (Hint: which vector function will you use here?)
  • This process should repeat for all indices of your vector (i.e. for all the vertices in the graph).
  • What type of loop do you want here and when will it start and stop? Hint: Do you know the number of vertices in the Graph?
  • For ease of implementation: I strong recommend using indices 1 up through and including the number of vertices, and leaving index 0 blank.
  • When you are finished writing the constructor, open up a new C++ file called GraphTest.cpp.
  • Add a main function inside of GraphTest.cpp and instantiate a new Graph.
  • Once your code compiles and runs, work next on addEdge and then on printGraph.


A Word on Printing
  • We are representing our Graph using the Adjacency List Representation.
  • Thus, we will need to print out its adjacency lists.
  • Below is an example of how to print your Graph.
1: 2, 5
2: 1, 3, 4
3: 4
4:
5: 1, 4, 5
  • I strongly recommend that you alter your List print function for this assignment so that it prints comma separated values as shown above.
What to Submit
  • Once you are certain all of your functions are working, upload your files to Catalyst under Lab 7
  • Submit your complete Graph, including List.h, Graph.h, Graph.cpp, and GraphTest.cpp
  • Note that you will lose 15 points per function for any missing function
  • You will lose 15 points for not testing your functions inside of GraphTest.cpp