The graph is represented as a hashtable of vertex IDs (key) and Vertex pointers (value)

Each Vertex object has a vector of pointers to Edge objects, in additions to a pointer to Data.

The graph constructor constructs the graph from a text file that specifies the source and target vertices of all edges in the graph. The arguments to the constructor are (1) if a reverse edge needs to be inserted (for undirected graphs), and (2) the file handler for the text file.

Note that the constructor has to create these objects dynamically (that is with new)

First make sure that the graph is constructed correctly by verifying with printGraph() method. printGraph prints each vertex and all the vertices reachable from it on separate lines. You should get the same output as the textfile.

/*Header File*/

#ifndef GRAPH_H

#define GRAPH_H

#include

#include

#include

using namespace std;

typedef struct {

bool visited; // Add other fields if needed

}Data;

typedef struct {

int target_vertex;

int source_vertex;

int weight;

}Edge;

typedef struct {

int vertex_id;

Data* data;

vector edge_list; // Vertex object maintains a list of pointers to edge objects

}Vertex;

class Graph {

private:

unordered_map vertex_list; //Hashtable with vertex ID as key, and point to vertex object as value

int num_edges;

void addEdge(int vs, int vt);

public:

Graph():num_edges(0) {};

Graph(bool insertReverseEdge, ifstream& ifs); // Reads the graph from a text file of edges one per line.

~Graph();

int getNumVertices() { return vertex_list.size();}

int getNumEdges() { return num_edges;}

void printGraph(); // For each vertex, print all the vertices it is connected to

//void BFS(int vs); // Visits nodes breadth first

//void DFS(int vs); // Visits nodes depth first

};

#endif

/* End of Header */

/*Test Program*/

#include

#include

using namespace std;

int main()

{

ifstream ifs("sample_edges.txt");

Graph g(false, ifs);

cout << "Number of vertices " << g.getNumVertices() << endl;

cout << "Number of edges " << g.getNumEdges() << endl;

cout << "Printing graph" << endl;

g.printGraph();

//cout << "Printing vertices in BFS order starting at vertex 0 " << endl;

// g.BFS(0);

// cout << "Printing vertices in DFS order starting at vertex 0 " << endl;

// g.DFS(0);

return 0;

}

/* End of Test Program*/

/* Functions to be coded*/

Graph::Graph(bool insertReverseEdge, ifstream& ifs) {

// Read lines of text, until end of file. Hint: Use getline()

// For each line, extract vertices Hint: Use stringstream, or string methods with space as delimiter

// If vertex does not exist in hashtable, create vertex object. Hint: Use find method of unordered_map. Check if iterator is end(). Create Data objecct, Vertex object, and Edge object

// Either way, create edge object, and insert into vector assocciated with the vertex object

// If insertReverseEdge, then create reverse edge object, and insert into the vector associated with the second vertex object. Hint: Do the same as above for target vertex

}

Graph::~Graph() {

// Walk through the hashtable

// For each vertex object, walk through the vector of edge pointers

// Delete each edge pointer, to free the edge objecte

// Delete the vertex pointer, to free the vertex object

}

Graph::printGraph() {

// For each vertex, print the vertices it is connected to

// Walk through the hashtable

// For each vertex object, walk through the vector of edges, and print the target vertices

}

Graph::DFS(int vertexID) {

}

Graph::BFS(int vertexID) {

}

/*End of Functions to be coded*/

/*Text file :" sample_edges.txt " :

0 1

0 2

1 3

2 4

3 4

3 5

4 5

*/

//end of txt file