C++ Program

You will need to implement a templated Graph class that implements a graph whose nodes are of T using an adjacency list and adjacency matrix as your private implementation.

This means that you have to implement the Graph as an pure virtual abstract class (if youre using C++). Use different sub-classes of the Graph class for implementing the adjacency list and adjacency matrix representations of a Graph .

1) Implement the following functions:

Graph & generateNewGraph(int numberOfNodes, double edgeProbability);

AdjListGraph & generateNewGraph(int numberOfNodes, double edgeProbability);

AdjMatrixgraph &generateNewGraph(int numberOfNodes, double edgeProability);

2) Use the program you just created to guess the performance of the depth first search of a graph represented

in an adjacency matrix. Generate graphs with sizes of 2, 8, 64, 256, and 1024 nodes, each with a random

number of edges, with edge probability of 0.5. Report how long (in seconds) it takes for your program to

execute the search.

NOTE : This means you have to implement three classes: the abstract base classs and two sub-classes that

implement the different data structures!

The Graph will need to implement provide the following interface:

bool adjacent(T x, T y) : Is there a path from x to y ?

vector neighbors(T x) : Return a vector containing the nodes that have a edge from x to elements

in the vector.

void addEdge(T x, T y) : Add an edge from x to y if none exists. The node x must exist in the graph and

you need to add the node y to the graph if it does not exist.

void deleteEdge(T x, T y) : Delete the edge from x to y if one exists. Your method needs to address the

special case of what happens if deleting the edge disconnects (directly or indirectly) the node y from the rest

of the graph.

void deleteNode(T x) : Delete the node x from the graph. Make certain that you do not leave any dangling

edges from other nodes to the newly deleted node.

void dfs(Graph &g, T &startNode) : Do a depth-first traversal of the graph g , starting from node

startNode . You may either print the contents of each node or implement the extra credit portion of the

assignment.

void bfs(Graph &g, T &startNode) : Do breath-first traversal of the graph g , starting from node

startNode .

- Assume that the base graph type is a directed graph

-Note that you will need to keep a separate vector or list in your data structures to keep track of the

information stored with each node. The adjacency list and adjacency matrix representations will store references to the data in this list.