Lab 10: Graphs Part 2 (100 pts)
Due Tuesday, June 20 at 1:20pm on Catalyst


Part 1: Updated Header File
  • Alter your header file from Lab 9 so that it now looks like the following:

#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
    
/***
 Access Functions ***/

int getNumEdges();
//returns the number of edges in the graph

int getNumVertices();
//returns the number of vertices in the graph

bool isEmpty();
//returns whether the graph is empty

int getDistance(int v);

//Pre: v <= numVertices. Returns the value of the distance[v]


int getParent(int v);

//Pre: v <= numVertices. Returns the value of the parent[v]

int getDistance(int v);

//Pre: v <= numVertices. Returns the value of distance[v]


char getColor(int v);

//Pre: v <= numVertices. 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& output);
//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& output);
//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& output);
//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 now will store information not just about the 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.
  • Thus, inside your Graph constructor, you will need to initialize all values in these parallel arrays.
  • 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) and the parent vector should be initialized to 0.
  • These values will then be updated when the BFS function is called on the Graph.

Part 2: Implement 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



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 when the user calls printGraph():
1: 2 5
2: 1 3 4
3: 2 4
4: 2 3 5
5: 1 4 5
  • 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.


File Input and Output
  • Save two text files in the main project directory on Eclipse.
  • Open up the source file named WriteGraph.cpp which contains logic for reading in information about a Graph from a file and then writing out the results of running BFS on that Graph to another file.
  • 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 when you create your Graph, 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:

6
1 2
1 3
2 4
2 5
2 6
3 4
4 5
5 6
0 0
1 5
3 6
2 3
4 4
0 0


Example Output File:

1: 2 3
2: 1 4 5 6
3: 1 4
4: 2 3 5
5: 2 4 6
6: 2 5
The distance from 1 to 5: 2
A shortest path from 1 to 5: 1 2 5
The distance from 3 to 6: 3
A shortest path from 3 to 6: 3 1 2 6
The distance from 2 to 3: 2
A shortest path from 2 to 3: 2 1 3
The distance from 4 to 4: 0
A shortest path from 4 to 4: 4


  • 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.
  • The output of BFS is uniquely determined by this requirement. The following example represents a disconnected graph.

Input File:

7
1 4
1 5
4 5
2 3
2 6
3 7
6 7
0 0
2 7
3 6
1 7
0 0


Output File:

1: 4 5
2: 3 6
3: 2 7
4: 1 5
5: 1 4
6: 2 7
7: 3 6
The distance from 2 to 7: 2
A shortest path from 2 to 7: 2 3 7
The distance from 3 to 6: 2
A shortest path from 3 to 6: 3 2 6
The distance from 1 to 7: infinite
No path from 1 to 7 exists



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


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
  • Half credit for a fully functional BFS function
  • 25 points for a functional printPath
  • 20 points for WriteGraph and a properly formatted output file
  • 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 Catalyst.