Lab 9: Graphs Pt 1(100 pts)

Due Tuesday, June 13 at 1:20pm on Catalyst

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
  • 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 and no edges
    
/***
 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

/*** Manipulation Procedures ***/

void addEdge(int u, int v);
//Pre: u <= getNumVertices() && v <=getNumVertices()
//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.

void removeEdge(int u, int v);
//Pre: u <= getNumVertices() && v <=getNumVertices()
//removes vertex v from the adjacency list of vertex u

//and removes u from 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

private:
    int vertices, edges; //number of edges and vertices
    vector<List<int> > adj;

};



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


File Input and Output

  • Save two text files in the main project directory on Eclipse.
  • Create a new source file named WriteGraph.cpp which will contain logic for reading in information about a Graph from a file and then writing out the results to a 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.
  • Your WriteGraph.cpp file should then write out the corresponding graph to outfile.txt. See the examples below:
Sample Input File
6
1 2
1 3
2 4
2 5
2 6
3 4
4 5
5 6

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

Total vertices: 6
Total edges: 8


Example Input File:

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


Example Output File:

1: 4 5
2: 3 6
3: 2 7
4: 1 5
5: 1 4
6: 2 7
7: 3 6

Total vertices: 7
Total edges: 7

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
  • It should then prompt the user for the name of an output file and print the graph inside this 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

  • -10 for a missing or inadequate GraphTest.cpp
  • -5 for each missing or incorrect function
  • -50 (max) for missing or incorrect WriteGraph.cpp


What to Submit

  • Submit your List.h, Graph.cpp, GraphTest.cpp, and WriteGraph.cpp to Catalyst