Lab 8: Graphs (100 pts)
Due Tuesday, March 6 at 9:20am on Canvas
Pair Programming Extra Credit Opportunity (5 pts)
 Both partners fill in, sign, date, and submit the pair programming contract
 Upload the document(s) along with your Lab to Canvas.
 Only ONE partner submits the lab assignment on Canvas. Please make sure both your names are on ALL THE FILES.
Part 1: Tutorial on Vectors
 Although you may not have studied vectors in the past, they are a commonlyused 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 (65 pts)
 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:
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
Graph Header File
#include <iostream> #include <cstdlib> #include <vector> #include "List.h"using namespace std;
class Graph { public:
/**Constructors and Destructors*/
Graph(int n); //initializes an empty graph to have n vertices
/*** Access Functions ***/
int getNumEdges() const;
//returns the number of edges in the graph
int getNumVertices() const;
//returns the number of vertices in the graph
bool isEmpty() const;
//returns whether the graph is empty (no vertices)
int getDistance(int v) const; //Pre: v <= vertices //Returns the value of the distance[v]
int getParent(int v) const; //Pre: v <= vertices //Returns the value of the parent[v]
char getColor(int v) const; //Pre: v <= vertices //Returns the value of color[v]
/*** 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)
//and inserts u into v.
/*** Additional Operations ***/
void printGraph(ostream& out);
//Prints the adjacency list of each vertex in the graph,
//vertex: <space separated list of adjacent vertices>
//Prints to the console or to an output file given the ostream parameter
void printBFS(ostream& out); //Prints the current values in the parallel vectors after executing BFS
//Prints to the console or to an output file given the ostream parameter
//First prints the heading:
//v <tab> c <tab> p <tab> d <tab>
//Then, prints out this information for each vertex in the graph
//Note that this function is intended purely to help you debug your code
void BFS(int source);
//Performs breath first search on this Graph give a source vertex
//pre: at least one vertex must exist
//pre: source is a vertex in the graph
void printPath(int source, int destination, ostream& out);
//Prints the path from the source to the destination vertex //Prints to the console or to an output file given the ostream parameter
private: int vertices, edges; //number of edges and vertices vector<List<int> > adj;
vector<char> color; vector<int> distance; vector<int> parent;
};
Parallel Arrays for the BFS Algorithm
 Your
Graph will store information not only about adjacent vertices,
but also about the color, parent and the distance from the source of all
the vertices in the Graph.
 Inside your Graph class, there are four private vectors:
private: int vertices, edges; //number of edges and vertices vector<List<int> > adj; vector<char> color; vector<int> distance; vector<int> parent;
 These vectors will work in parallel to each other.
 For example:
adj[1] color[1] distance[1] parent[1]
All store information about vertex 1 of the Graph.  In other words, your Graph should contain:
 A vector of Lists whose ith element contains the neighbors of vertex i.
 A vector of chars whose ith element is the color (white, gray, black) of vertex i.
 A vector of ints whose ith element is the parent of vertex i.
 A vector of ints whose ith element is the distance from the (most recent) source to vertex i.
The Graph Constructor
 Your graph constructor will take in a parameter for the number of vertices in the graph.
 This parameter will define the size of the private parallel vectors.
 You will need to initialize all values in the parallel vectors.
 The
color vector should be initialized to 'W' (later updated to 'G' and
'B')
 The distance vector should be initialized to 1 (which we will use
to indicate an infinite distance)
 The parent vector should be
initialized to 0.
 The adjacency list vector should be initialized to an empty list at each index.
 Note that your graph constructor can be written using a single for loop to initialize all the vectors.
Implementation of the BFS Algorithm
 Use the pseudocode below to help you implement this function:
BFS(G, s) for all x in V(G) color[x] = white distance[x] = 1 parent[x] = Nil color[s] = grey distance[s] = 0 Enqueue(Q,s) while(Q is not empty) x = front of Q Dequeue(Q,x)
for all y in adj[x] if color[y] == white color[y] = grey distance[y] = distance[x] + 1 parent[y] = x Enqueue(Q, y) color[x] = black
Printing Your Graph
 There are two print functions for the Graph: printGraph() and printBFS().
 We are representing our Graph using the Adjacency List Representation.
 Thus, to display the graph itself, we will print its adjacency list representation.
 Below is an example of how to print your Graph when the user calls printGraph():
1: 2 5 2: 1 3 4 3: 2 4 4: 2 3 5
5: 1 4 5
 In contrast, below is an example of what the printBFS() function's output should look like:
v c p d 1 B 0 0 2 B 1 1 3 B 2 2 4 B 2 2 5 B 1 1
 Note
that the printBFS() function is designed to be useful to you as the
programmer in tracking down bugs as you are implementing the BFS function. It has no other purpose in
this assignment.
The Print Path Algorithm
 Once
BFS has been called on a Graph, you will need a way to step through the
parent array to find the shortest path from the source to the
destination vertex.
 We can use the recursive print path algorithm to help us.
 Below is the recursive pseudocode for Print Path:
Print_Path(Graph, source, destination) if destination == source print source else if parent[destination] == 0 print "No path from " source "to " destination exists else Print_Path(Graph, source, parent[destination]) print destination
Part 3: File I/O and WriteGraph.cpp (35 pts)
 Save two text files in the main project directory on Eclipse (rightclick the name of the project and go to New>File) not in the src folder.
 The input file will be in two parts. The first part will begin with a line consisting of a single integer n giving the number of vertices in the graph.
 You will pass this value n into your Graph constructor, setting the numVertices to be this value n.
 Each
subsequent line will represent an edge by a pair of distinct numbers in
the range 1 to n, separated by a space. These numbers are the end
vertices of the corresponding edge.
 The
first part of the input file defines the graph, and will be terminated
by a dummy line containing “0 0”. After these lines are read, your
program will print the adjacency list representation of the graph to the
output file.
 The
second part of the input file will consist of a number of lines, each
consisting of a pair of integers in the range 1 to n, separated by a
space. Each line specifies a pair of vertices in the graph; a starting
point (or source) and a destination.
 The second part of the input file will also be terminated by the dummy line “0 0”.
 For each sourcedestination pair your program will do the following:
 Perform
a Breadth First Search (BFS) from the given source vertex. This assigns
a parent vertex (which may be 0, indicating that there is no parent) to
every vertex in the graph.
 Use the
results of BFS to print out the distance from the source vertex to the
destination vertex, then use the parent pointers to print out a shortest
path from source to destination.
Example Input File:
7 1 3 1 4 1 5 2 6 3 5 4 5 5 7 0 0 1 7 2 6 3 3 4 6 0 0
Example Output File:
1: 3 4 5 2: 6 3: 1 5 4: 1 5 5: 1 3 4 7 6: 2 7: 5 The distance from 1 to 7: 2
A shortest path from 1 to 7: 1 5 7
The distance from 2 to 6: 1
A shortest path from 2 to 6: 2 6
The distance from 3 to 3: 0 A shortest path from 3 to 3: 3 The distance from 4 to 6: 1 No path from 4 to 6 exists.
 If
there is no path from source to destination (which may happen if the
graph is disconnected), then your program should print a message to that
effect.
 Note that there may be more than one shortest path joining a given pair of vertices.
 The particular path discovered by BFS depends on the order in which it steps through the vertices in each adjacency list.
 We adopt the convention in this assignment that vertices are always processed in sorted order, i.e. by increasing labels.
Input File:
8 1 2 2 3 2 4 2 5 2 6 3 8 6 7 7 8 0 0 2 7 4 7 5 8 0 0
Output File:
1: 2 2: 1 3 4 5 6 3: 2 8 4: 2 5: 2 6: 2 7 7: 6 8 8: 3 7 The distance from 2 to 7: 2 A shortest path from 2 to 7: 2 6 7 The distance from 4 to 7: 3 A shortest path from 4 to 7: 4 2 6 7 The distance from 5 to 8: 3 A shortest path from 5 to 8: 5 2 3 8
WriteGraph.cpp
 Your WriteGraph.cpp should work identically to the sample output below.
 It
should prompt a user for the name of a file and then use a loop to
report an error if the file name is not found in the directory.
 It should read in the contents of the file specified by the user
 Next, it will call BFS on the graph for each source vertex, and then calculate the path from source to destination.
 It should then prompt the user for the name of an output file and print the information as shown in the sample output files above into the output file:
Welcome to WriteGraph!
Enter the name of the file containing the graph information: asdkshjkdshljkdsf Invalid file name!
Please enter the name of the file: input Invalid file name!
Please enter the name of the file: input.txt ***Reading from input.txt***
Please enter the name of the output file: output.txt
Thank you! Your Graph is now written to output.txt!
How You Will Be Graded
 5 points for each correct graph function
 35 points for a WriteGraph.cpp which can replicate the results of all example input and output files given for this assignment, plus any additional files with which the instructor may decide to test your code
 10 point deduction for a missing or incomplete GraphTest.cpp file
What to Submit
 Submit your List.h, Graph.cpp, WriteGraph.cpp, and GraphTest.cpp to Canvas.
 Do not submit your Graph.h to Canvas.
 Please submit each file separately (no zip files please).
