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 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 (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:


  • 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


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 (right-click 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 source-destination pair your program will do the following:
      1. 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.
      2. 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).