Question
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
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
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
template
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
while (temp->next != NULL) { temp = temp->next; iterator->next = new Node(temp->data); iterator = iterator->next;
} last = iterator; iterator = NULL; } } template
delete cursor;
cursor = temp; } } template
cout << temp->data << " "; temp = temp->next; } cout << endl; } template
} template
else {
Nodeptr temp = last; last = last->previous; cout << last->data << endl; delete temp; last->next = NULL; size--; } } template
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
assert(size != 0); assert(index <= size); iterator = first; for (int i = 1; i < index; i++) { iterator = iterator->next; } }
template
template
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
#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!
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started