Assignment 5: Graphs (100 pts)
Due Tuesday, November 29 at 11:20am on Catalyst and as a hard copy in class


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();
    //graph destructor
    
/***
 Access Functions ***/

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

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

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

/*** 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)

/*** Additional Operations ***/

void print_graph(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 print_BFS(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

void breadth_first_search(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 print_path(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;


};


Breadth First Search
  • 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.
Implement the BFS Function
  • 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 print_graph():
1: 2 5
2: 1 3 4
3: 4
4: 3
5: 1 4 5
  • Below is an example of what the print_BFS() function's output should look like for the above graph:

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 print_BFS() function is designed to be useful to you as the programmer in tracking down bugs as you are implementing the breadth_first_search(int source) function. It has no other purpose in this assignment.
File Input and Output
  • Write a file named BST.cpp which will contain 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.
Sample Input File
6
1 2
1 3
2 4
2 5
2 6
3 4
4 5
5 6
0 0

  • 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 is 2
A shortest 1-5 path is: 1 2 5
The distance from 3 to 6 is 3
A shortest 3-6 path is: 3 1 2 6
The distance from 2 to 3 is 2
A shortest 2-3 path is: 2 1 3
The distance from 4 to 4 is 0
A shortest 4-4 path is: 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 is 2
A shortest 2-7 path is: 2 3 7
The distance from 3 to 6 is 2
A shortest 3-6 path is: 3 2 6
The distance from 1 to 7 is infinity
No 1-7 path 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

How to Approach This Assignment

  • Your program’s operation can be broken down into two basic steps, corresponding to the two groups of input data.
1. Read and store the graph and print out its adjacency list representation.
2. Enter a loop that processes the second part of the input. Each iteration of the loop should read in one pair of vertices (source, destination), run BFS on the source vertex, print the distance to the destination vertex, then find and print the resulting shortest path, if it exists, or print a message if no path from source to destination exists (as in the above example).

What to Submit
  • Submit your List.h, Graph.h, Graph.cpp, BFS.cpp, and GraphTest.cpp, Queue.h, and Queue.cpp to Catalyst.
  • Submit Graph.cpp, BFS.cpp as a hard copy in class