Please write the following code in the Graph.cpp and the WriteGraph.cpp. The List.h is already done.

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

#include #include #include "List.h" #include

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:

//Prints to the console or to an output file given the ostream parameter

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

};

Here is the List header code:

#ifndef LIST_H_ #define LIST_H_

#include #include #include #include using namespace std;

template class List { private: struct Node { listdata data; Node* next; Node* previous;

Node(listdata data) : data(data), next(NULL), previous(NULL) { } };

typedef struct Node* Nodeptr;

Nodeptr first; Nodeptr last; Nodeptr iterator; void reverse(Nodeptr node); bool isSorted(Nodeptr node); int binarySearch(int low, int high, listdata data); int size; public:

/**Constructors and Destructors*/

List(); //Default constructor; initializes and empty list //Postcondition:create a link list.

List(const List &list);

~List(); //Destructor. Frees memory allocated to the list //Postcondition:frees the memory associated with the linked list.

/**Accessors*/

listdata getFirst(); //Returns the first element in the list //Precondition:first should not be empty.

listdata getLast(); //Returns the last element in the list //Precondition:last should not be empty.

bool isEmpty(); //Determines whether a list is empty.

int getSize(); //Returns the size of the list

/**Manipulation Procedures*/

void removeLast(); //Removes the value of the last element in the list //Precondition:list should not be empty. //Postcondition:Remove the last element of the list.

void removeFirst(); //Removes the value of the first element in the list //Precondition:list should not be empty //Postcondition:Remove the last element of the list.

void insertLast(listdata data); //Inserts a new element at the end of the list //If the list is empty, the new element becomes both first and last //Postcondition:insert the new element at the end of the list.

void insertFirst(listdata data); //Inserts a new element at the start of the list //If the list is empty, the new element becomes both first and last //Postcondition:insert the new element at the beginning of the list.

/**Additional List Operations*/

void printList(); //Prints to the console the value of each element in the list sequentially //and separated by a blank space //Prints nothing if the list is empty

void startIterator(); //postcondition: set the beginning of the element equal to iterator.

void removeIterator(); // postcondition: Remove the iterator.

void insertIterator(listdata data); //precondition: list should not be empty. //postcondition: insert the new iterator.

void advanceIterator();

listdata getIterator();

bool offEnd();

bool operator==(const List &list);

void printReverse(); //Wrapper function that calls the reverse helper function to print a list in reverse //prints nothing if the List is empty

bool isSorted(); //Wrapper function that calls the isSorted helper function to determine whether //a list is sorted in ascending order. //We will consider that a list is trivially sorted if it is empty. //Therefore, no precondition is needed for this function

int getIndex(); //Indicates the index of the Node where the iterator is currently pointing //Nodes are numbered from 1 to size of the list //Pre: size != 0 //Pre: !off_end()

void advanceToIndex(int index); //Moves the iterator to the node whose index number is specified in the parameter //Pre: size != 0 //Pre: index <= size

int linearSearch(listdata data); //Searchs the list, element by element, from the start of the List to the end of the List //Returns the index of the element, if it is found in the List //Calls the above indexing functions in its implementation //Returns -1 if the element is not in the List //Pre: size != 0

int binarySearch(listdata data); //Returns the index where data is located in the List //Calls the private helper function binarySearch to perform the search //Pre: size != 0 //Pre: List is sorted (must test on a sorted list) }; template List::List() : first(NULL), last(NULL), iterator(NULL), size(0) { } template List::List(const List &list) : size(list.size) { if (list.first == NULL) { first = last = iterator = NULL; } else { first = new Node(list.first->data); Nodeptr temp = list.first; iterator = first;

while (temp->next != NULL) { temp = temp->next; iterator->next = new Node(temp->data); iterator = iterator->next;

} last = iterator; iterator = NULL; } } template List::~List() { Nodeptr cursor = first; Nodeptr temp; while (cursor != NULL) { temp = cursor->next;

delete cursor;

cursor = temp; } } template void List::reverse(Nodeptr node) { node = last; while (node->previous != NULL) { cout << node->data << " "; node = node->previous; } cout << first->data << endl; } template void List::printList() { Nodeptr temp = first; while (temp != NULL) {

cout << temp->data << " "; temp = temp->next; } cout << endl; } template void List::printReverse() { Nodeptr temp = last; reverse(temp);

} template void List::insertFirst(listdata data) { if (size == 0) { first = new Node(data); last = first; } else { Nodeptr N = new Node(data); N->next = first; first->previous = N; first = N; } size++; } template void List::insertLast(listdata data) { if (size == 0) { Nodeptr N = new Node(data); first = last = N; } else { Nodeptr N = new Node(data); last->next = N; N->previous = last; last = N; } size++; } template void List::removeFirst() { assert(size != 0); if (size == 1) { delete first; first = last = NULL; size = 0; } else { Nodeptr temp = first; first = first->next; delete temp; first->previous = NULL; size--; } } template void List::removeLast() { assert(size != 0); if (size == 1) { delete last; last = first = NULL; size = 0; }

else {

Nodeptr temp = last; last = last->previous; cout << last->data << endl; delete temp; last->next = NULL; size--; } } template void List::insertIterator(listdata data) { assert(size != 0); assert(iterator!= NULL); if (iterator == last) { insertLast(data); } else { Nodeptr N = new Node(data); N->next = iterator->next; N->previous = iterator; iterator->next->previous = N; iterator->next = N; } size++; } template void List::startIterator() { iterator = first; } template void List::advanceIterator() { assert(iterator != NULL); assert(size != 0); iterator = iterator->next; } template void List::removeIterator() { assert(iterator != NULL); assert(size != 0);

if (size == 1) { delete iterator; iterator = first = last = NULL; size = 0; } else if (iterator == first) { removeFirst(); } else if (iterator == last) { removeLast(); } else { iterator->previous->next = iterator->next; iterator->next->previous = iterator->previous; delete iterator; iterator = NULL; size--; } } template void List::advanceToIndex(int index) {

assert(size != 0); assert(index <= size); iterator = first; for (int i = 1; i < index; i++) { iterator = iterator->next; } }

template int List::getIndex() { assert(size != 0); assert(!offEnd()); Nodeptr n = first; int count = 1; while (n != iterator) { n = n->next; count++; } return count; } template bool List::isEmpty() { return (size == 0); } template int List::getSize() { return size; } template listdata List::getFirst() { assert(first != NULL); return first->data; } template listdata List::getLast() { assert(last != NULL); return last->data; } template bool List::offEnd() { if (iterator == NULL) { return true; } else { return false; } }

template listdata List::getIterator() { assert(iterator!= NULL); return iterator->data; } template bool List::operator==(const List &list) { if (size != list.size) return false; Nodeptr temp1 = first; Nodeptr temp2 = list.first; while (temp1 != NULL) { if (temp1->data != temp2->data) return false; temp1 = temp1->next; temp2 = temp2->next; } return true; } template bool List::isSorted(Nodeptr node) { if(node == last) { return true; } else if((node->data) > (node->next->data)) { return false; } else { return isSorted(node->next); } } template int List::binarySearch(int low, int high, listdata data) { if (high < low) { return -1; } int mid = low + (high - low) / 2;

advanceToIndex(mid);

if (getIterator() == data) { return mid; } else if (getIterator() > data) { return binarySearch(low, mid - 1, data); } else { return binarySearch(mid + 1, high, data); } } template bool List::isSorted() { Nodeptr temp = first; return isSorted(temp); } template int List::linearSearch(listdata data) { assert(size != 0); int count = 0; Nodeptr N = first; while (N != NULL) { count++; if (N->data == data) { cout << count << endl; return count; } N = N->next; } return -1; } template int List::binarySearch(listdata data) { assert(size != 0); assert(isSorted()); return binarySearch(1, size, data); }

#endif /* LIST_H_ */

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. These two files must be named infile.txt and outfile.txt.

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!