Data structures and algorithms C++ Graph implementation

Hello, I am having trouble understanding this task, thank you in advance for any help!

Your task is to implement an undirected graph class.

For example, the following undirected graph has six vertices {0,1,2,3,4,5} and eight edges {(0,2), (0,4), (0,5), (1,4), (1,5), (2,3), (2,4), (4,5)}.

The class should offer an effective suite of operations, including:

• Adding and removing vertices and edges;

• Checking whether a certain vertex exists in the graph;

• Checking whether there is an edge between two vertices;

• Getting the total number of vertices/edges in the graph;

• Getting the set of vertices in the graph;

• Depth-first and breadth-first traversals starting from a certain vertex;

• Getting the degree of a certain vertex;

• Getting the vertices adjacent to a vertex;

• Getting the largest degree of all vertices in the graph;

• Computing a spanning tree rooted at a given vertex;

The Code

You are provided with a graph.hpp file, which includes most (if not all) of the basic definitions you will need. You can add extra methods, classes, structs, etc., as long as they don't interfere with the existing definitions.

The Graph Class

You are provided with a Graph Class in graph.hpp. This class uses template type T as the type of each vertex ID. T can be any comparable datatype that can be used as a key for the map data structure in C++. e.g., T can be int, long, string, char, etc. Below is an example of creating an empty graph with string as the type of each vertex ID:

Graph g;

In the Graph class, it contains a protected member

map> adj;

which is used to maintain the adjacent vertices for each vertex in the graph. It maps each vertex ID to a set of adjacent vertex IDs. You cannot replace it with your own designed data structures.

CODE GIVEN w/instructions:

***************main.cpp*****************

#include "graph.hpp"

//the codes in the main function can be changed arbitrarily. The following code is just for your testing. int main() { Graph g; g.add_vertex('a'); g.add_vertex('b'); g.add_vertex('c'); g.add_vertex('d'); g.add_vertex('e'); g.add_vertex('f');

g.add_edge('a','c'); g.add_edge('a','e'); g.add_edge('a','f'); g.add_edge('b','e'); g.add_edge('b','f'); g.add_edge('c','d'); g.add_edge('c','e'); g.add_edge('e','f');

g.add_vertex('g'); g.add_edge('b','g'); g.add_edge('a','g'); g.add_edge('d','g'); g.add_edge('a','d');

g.remove_edge('a','d'); g.remove_vertex('g');

g.show(); cout << "num_vertices=" << g.num_vertices() << endl; cout << "num_edges=" << g.num_edges() << endl;

cout << "g.contains('f')=" << (g.contains('f')?"true":"false") << endl; cout << "g.contains('g')=" << (g.contains('g')?"true":"false") << endl; cout << "g.adjacent('a','d')=" << (g.adjacent('a','d')?"true":"false") << endl; cout << "g.adjacent('b','e')=" << (g.adjacent('b','e')?"true":"false") << endl; cout << "degree of vertex a is " << g.degree('a') << endl; cout << "largest degree=" << g.largest_degree() << endl;

auto vertices = g.get_vertices(); cout << "vertices ="; for(auto u:vertices) cout << " " << u; cout << endl;

auto nbrs = g.get_neighbours('f'); cout << "neighbors of vertex f ="; for(auto u:nbrs) cout << " " << u; cout << endl;

auto dft = g.depth_first('a'); cout << "DFT from vertex a: {"; for(auto u:dft) cout << u << " "; cout << "}" << endl;

auto bft = g.breadth_first('a'); cout << "BFT from vertex a: {"; for(auto u:bft) cout << u << " "; cout << "}" << endl;

auto tree = g.spanning_tree('a'); cout << "Spanning Tree:" << endl; tree.show();

cout << endl << endl;

return 0; }

**********graph.hpp********************

#ifndef GRAPH_H #define GRAPH_H

#include #include #include #include

using namespace std; // the standard namespace are here just in case.

/* the graph class */ template class Graph {

protected: //do not change this

//the set of adjacent vertices for each vertex, do not overwrite it //you should make sure that the adj data structure is maintained correctly when add/removing vertices/edges //otherwise, it will cause problems with testing other functions. map> adj;

public: void show(); //show the vertices and edges of the graph, this is already implemented for you to print the graph and test. You can overwrite it if needed. It will not take up any score.

bool contains(const T& u); //Returns true if the graph contains the given vertex_id, false otherwise. bool adjacent(const T& u, const T& v); //Returns true if u and v are adjacent, false otherwise.

void add_vertex(const T& u); //add a vertex with ID u (with no edges). void add_edge(const T& u, const T& v); //Add an edge (u,v) to the undirected graph for two existing vertices u and v

void remove_vertex(const T& u); //Removes the given vertex u. Should also clear any incident edges. void remove_edge(const T& u, const T& v); //Removes the edge between the two vertices, if it exists.

int degree(const T& u); //Returns number of incident edges to a vertex. int num_vertices(); //Returns the total number of vertices in the graph. int num_edges(); //Returns the total number of edges in the graph. int largest_degree(); //Returns the largest degree of all vertices in the graph.

vector get_vertices(); //Returns a verctor containing all vertices in the graph vector get_neighbours(const T& u); //Returns a vector containing all the adjacent vertices of a given vertex. The vertex is not considered a neighbour of itself.

vector depth_first(const T& u); //Returns the vertices of the graph in the order they are visited in by a depth-first traversal starting at the given vertex. vector breadth_first(const T& u); //Returns the vertices of the graph in the order they are visisted in by a breadth-first traversal starting at the given vertex.

Graph spanning_tree(const T& u); //Returns a spanning tree starting at the given vertex. };

//this function is already implemented and you can use it directly to print a graph for testing template void Graph::show() { for(const auto &u:adj) { cout << u.first << ":"; for(const auto &v:adj[u.first]) cout << " " << v; cout << endl; } }

// Define all your methods down here (or move them up into the header, but be careful you don't double up). If you want to move this into another file, you can, but you should #include the file here. // Although these are just the same names copied from above, you may find a few more clues in the full method headers. // Note also that C++ is sensitive to the order you declare and define things in - you have to have it available before you use it.

template bool Graph::contains(const T& u) { return adj.find(u) != adj.end(); }

template bool Graph::adjacent(const T& u, const T& v) { }

template void Graph::add_vertex(const T& u) { if(adj.find(u) != adj.end()) return; adj[u] = set(); }

template void Graph::add_edge(const T& u, const T& v) {

}

template void Graph::remove_vertex(const T& u) {

}

template void Graph::remove_edge(const T& u, const T& v) {

}

template int Graph::degree(const T& u) { return 0; }

template int Graph::num_vertices() { return 0; }

template int Graph::num_edges() { return 0; }

template int Graph::largest_degree() { return 0; }

template vector Graph::get_vertices(){ return vector(); }

template vector Graph::get_neighbours(const T& u){ return vector(); }

template vector Graph::depth_first(const T& u) { return vector(); }

template vector Graph::breadth_first(const T& u) { return vector(); }

template Graph Graph::spanning_tree(const T& u) { return Graph(); }

#endif