Using C++ and the C standard library create a template graph class that will implement a graph with nodes of type.

Create both an adjacency list and an adjacency matrix which will be subclasses of the Graph virtual abstract class.

Graph should include:

-bool adjacent(type x, type y): returns bool value is a node exists from x to y

-Vector neighbors(type x): return back the vector containing the nodes that have an edge from the node x to elements in the vector.

- void addNode(type x) : add a new node to the graph

- void deleteNode(type x): Delete the node x from the graph, addressing the removal of any edges from x to any other node.

- void addEdge(type x, type y) : add an edge from x to y if none exists

- void deleteEdge(type x, type y) : delete the edge from x to y if one exists

Test this graph class by writing a C++ program that checks a user specified path for a cycle. The input needs to be in the form node_id: Node_list where node_id is an integer used to identify a particular node and the node_list is a list of integers separated by commas that define the destination of each out-edge from the graph node.

Example data file.

1: 2,4,6,8

2: 4,5

3: 2,5

4: 2